Mathwords logoMathwords

Big Theta Notation — Definition, Formula & Examples

Big Theta notation, written Θ(g(n)), means a function grows at the same rate as g(n) for large n — neither significantly faster nor significantly slower. It provides a tight bound, capturing both an upper and a lower limit on growth.

A function f(n) is in Θ(g(n)) if and only if there exist positive constants c1c_1, c2c_2, and n0n_0 such that for all n≥n0n \ge n_0, the inequality c1⋅g(n)≤f(n)≤c2⋅g(n)c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) holds. Equivalently, f(n)∈Θ(g(n))f(n) \in \Theta(g(n)) if and only if f(n)∈O(g(n))f(n) \in O(g(n)) and f(n)∈Ω(g(n))f(n) \in \Omega(g(n)).

Key Formula

c1⋅g(n)  ≤  f(n)  ≤  c2⋅g(n)for all n≥n0c_1 \cdot g(n) \;\le\; f(n) \;\le\; c_2 \cdot g(n) \quad \text{for all } n \ge n_0
Where:
  • f(n)f(n) = The function whose growth rate you are classifying
  • g(n)g(n) = The reference function (e.g., n², n log n)
  • c1,c2c_1, c_2 = Positive constants that bound f(n) from below and above
  • n0n_0 = The threshold beyond which the inequality holds

How It Works

To show that f(n)∈Θ(g(n))f(n) \in \Theta(g(n)), you need to sandwich f(n)f(n) between two constant multiples of g(n)g(n) from some point onward. First, find a constant c2c_2 so that f(n)≤c2⋅g(n)f(n) \le c_2 \cdot g(n) for large nn — this establishes the Big-O upper bound. Then find a constant c1c_1 so that f(n)≥c1⋅g(n)f(n) \ge c_1 \cdot g(n) for large nn — this establishes the Big-Omega lower bound. If both constants exist, the function is Θ(g(n)). A useful shortcut: if lim⁡n→∞f(n)/g(n)\lim_{n \to \infty} f(n)/g(n) exists and equals a positive finite constant, then f(n)∈Θ(g(n))f(n) \in \Theta(g(n)).

Worked Example

Problem: Show that f(n) = 3n² + 5n + 2 is in Θ(n²).
Upper bound: For n ≥ 1, each term is at most 3n² + 5n² + 2n² = 10n². So f(n) ≤ 10n², giving c₂ = 10.
3n2+5n+2  ≤  10n2for n≥13n^2 + 5n + 2 \;\le\; 10n^2 \quad \text{for } n \ge 1
Lower bound: Since 5n + 2 ≥ 0 for n ≥ 1, we have f(n) ≥ 3n². So c₁ = 3.
3n2+5n+2  ≥  3n2for n≥13n^2 + 5n + 2 \;\ge\; 3n^2 \quad \text{for } n \ge 1
Conclusion: With c₁ = 3, c₂ = 10, and n₀ = 1, both bounds hold, so f(n) ∈ Θ(n²).
3n2  ≤  3n2+5n+2  ≤  10n23n^2 \;\le\; 3n^2 + 5n + 2 \;\le\; 10n^2
Answer: f(n) = 3n² + 5n + 2 is Θ(n²).

Why It Matters

In algorithm analysis, Big Theta gives the tightest description of running time. Saying an algorithm is Θ(n log n) — rather than merely O(n log n) — tells you that no clever input can make it run faster than n log n either, which is critical when comparing sorting algorithms or choosing data structures in computer science courses.

Common Mistakes

Mistake: Using Big-O when you mean Big-Theta. Saying "merge sort is O(n log n)" is true but imprecise — it is actually Θ(n log n).
Correction: Use Θ when you can prove both upper and lower bounds. Reserve O for when you only know (or only need) an upper bound.

Related Terms