Big Theta notation

Big Theta notation ($\Theta$) gives an asymptotic tight bound on a function’s growth. Writing $f(n)=\Theta (g(n))$ means that $f$ grows at the same rate as $g$ — bounded both above and below by constant multiples of $g$ for large $n$.

Formally:

$f(n)=\Theta (g(n))⟺\exists c_1,c_2>0,n_0>0:\forall n\ge n_0,c_1\cdot g(n)\le f(n)\le c_2\cdot g(n).$

Two constants — a lower constant $c_1$ and an upper constant $c_2$ — sandwich $f$ between $c_{1}g$ and $c_{2}g$ from some threshold $n_0$ onwards.

Equivalently: $f(n)=\Theta (g(n))$ if and only if $f(n)=O(g(n))$ AND $f(n)=\Omega (g(n))$. Big Theta is exactly the conjunction of Big O (upper bound) and Big Omega (lower bound).

When to use Big Theta vs Big O

When people informally say “this algorithm is $O(n\log n)$,” they usually mean it’s tightly $\Theta (n\log n)$ — both $O(n\log n)$ and $\Omega (n\log n)$. Big O has become the colloquial default, with Theta reserved for situations where the tightness needs to be made explicit.

The distinction matters in formal writing:

• $O(n^2)$ says “no worse than quadratic.” A linear algorithm satisfies this trivially.
• $\Theta (n^2)$ says “exactly quadratic.” Linear algorithms do not satisfy this.

For a textbook claim like “merge sort runs in $\Theta (n\log n)$ in all cases (best, average, worst),” Theta is the precise statement: the number of comparisons grows exactly proportionally to $n\log n$, never less, never more.

Worked example

Show that $f(n)=8n^2+3n+5$ is $\Theta (n^2)$.

Need $c_1,c_2>0$ and $n_0>0$ such that $c_1{n}^2\le 8n^2+3n+5\le c_2{n}^2$ for all $n\ge n_0$.

Upper bound ($c_2$). Pick $c_2=16$. Need $8n^2+3n+5\le 16n^2$, i.e. $0\le 8n^2-3n-5$. The roots of $8n^2-3n-5=0$ are $n=1$ and $n=-5/8$, so the inequality holds for $n\ge 1$.

Lower bound ($c_1$). Pick $c_1=8$. Need $8n^2\le 8n^2+3n+5$, i.e. $0\le 3n+5$, holds for all $n\ge 0$.

So $c_1=8,c_2=16,n_0=1$ work. Therefore $f(n)=\Theta (n^2)$.

When you can’t use Theta

Some functions don’t have a Theta classification because they oscillate between growth rates. The classic example:

$f(n)=\{\begin{array}{ll}{n}^2& \text{if }n\text{ is even}\\ n& \text{if }n\text{ is odd}\end{array}$

This $f$ is $O(n^2)$ (true upper bound, achieved on even $n$) and $\Omega (n)$ (true lower bound, achieved on odd $n$). But $f\ne \Theta (n^2)$ because there’s no $c_1>0$ such that $f(n)\ge c_1{n}^2$ for all large $n$ — odd inputs violate this. Similarly $f\ne \Theta (n)$.

So $f$ has a Big O bound and a Big Omega bound, but no tight Big Theta bound. Real algorithms rarely behave this way, but the example shows why all three notations exist.

Properties

• Reflexive: $f(n)=\Theta (f(n))$ always.
• Symmetric: $f=\Theta (g)$ iff $g=\Theta (f)$. Same growth rate is a symmetric relation.
• Transitive: $f=\Theta (g)$ and $g=\Theta (h)$ implies $f=\Theta (h)$.
• Polynomial leading term: $a_k{n}^k+\dots +a_0=\Theta (n^k)$ when $a_k>0$. Drop all but the leading term.

These properties make $\Theta$ an equivalence relation on functions — it partitions them into classes that grow at the same rate.

Common asymptotic classes via Theta

Class	Examples
$\Theta (1)$	Hash table lookup, array indexing
$\Theta (\log n)$	Binary search, balanced BST operations
$\Theta (n)$	Linear search, single array traversal
$\Theta (n\log n)$	Merge sort, heap sort
$\Theta (n^2)$	Bubble sort, naïve all-pairs operations
$\Theta (n^3)$	Naïve matrix multiplication
$\Theta (2^n)$	Brute-force subset enumeration

These are the “natural complexity classes” — algorithms typically land in one of these, and the practical implications jump dramatically between adjacent classes.

In context

Big Theta is the third of the asymptotic-bound notations:

• Big O notation ($O$) — upper bound. Default in casual discussion.
• Big Omega notation ($\Omega$) — lower bound. Used for problem-complexity arguments.
• Big Theta ($\Theta$) — tight bound. The precise statement when both upper and lower bounds match.

For the running-time-of-specific-algorithm analysis context, see Algorithm analysis.