Asymptotic notation: Θ, O, Ω (and o, ω)

Why we compare growth rates

We judge algorithms by how their cost grows as $n\to \infty$, dropping constant factors and lower-order terms. For large $n$ those details are dominated by the leading term, so the order of growth is what actually distinguishes algorithms — and it is machine-independent.

The three bounds, formally

Each notation is a set of functions, defined by exhibiting constants. To prove membership you only need to find one valid pair (or triple) of constants.

• $O(g)$ — asymptotic upper bound ("no faster than"). $f(n)=O(g(n))$ iff there exist constants $c>0,n_0>0$ with $0\le f(n)\le cg(n)$ for all $n\ge n_0$.
• $\Omega (g)$ — asymptotic lower bound ("at least as fast as"). $f(n)=\Omega (g(n))$ iff there exist $c,n_0>0$ with $0\le cg(n)\le f(n)$ for all $n\ge n_0$.
• $\Theta (g)$ — asymptotically tight bound ("exactly this rate"). $f(n)=\Theta (g(n))$ iff there exist $c_1,c_2,n_0>0$ with $0\le c_{1}g(n)\le f(n)\le c_{2}g(n)$ for all $n\ge n_0$.

The single most useful fact (Theorem 3.1) glues them together:

$$f(n)=\Theta (g(n))⟺f(n)=O(g(n))\text{and}f(n)=\Omega (g(n)).$$

So to prove a tight bound, prove the upper bound and the lower bound separately and cite the theorem — far easier than juggling $c_1$ and $c_2$ at once.

Worked example — prove $3n^2+2n=\Theta (n^2)$ from the definition

Upper ($O$). Want $3n^2+2n\le c{n}^2$. Divide by $n^2$: $3+2/n\le c$. At $n_0=1$ the left side is at most $5$, so $c=5$ works. Hence $3n^2+2n=O(n^2)$.

Lower ($\Omega$). Want $c{n}^2\le 3n^2+2n$. Since $2n>0$, $3n^2\le 3n^2+2n$, so $c=3$ and any $n_0\ge 1$ works. Hence $3n^2+2n=\Omega (n^2)$.

Both bounds hold, so by Theorem 3.1, $3n^2+2n=\Theta (n^2)$ — with $c_1=3$, $c_2=5$, $n_0=1$.

The general technique: to disprove an $O$ bound (e.g. $n^3-100n^2\notin O(n^2)$), assume it holds, divide by the target, and show the required $c$ would have to grow with $n$ — impossible for a fixed constant.

Strict bounds: o and ω

Little-oh and little-omega are the strict versions, where the bound holds for every $c>0$:

• $f=o(g)$ means $f$ grows strictly slower than $g$, i.e. ${\lim }_{n\to \infty }f(n)/g(n)=0$ (e.g. $2n=o(n^2)$).
• $f=\omega (g)$ means $f$ grows strictly faster, i.e. ${\lim }_{n\to \infty }f(n)/g(n)=\infty$.

The number-line analogy: $O\leftrightarrow \le$, $\Omega \leftrightarrow \ge$, $\Theta \leftrightarrow =$, $o\leftrightarrow <$, $\omega \leftrightarrow >$. But beware: trichotomy fails — two functions can be incomparable (neither $O$ nor $\Omega$ of each other), unlike real numbers.

The growth hierarchy you must know cold

$$\Theta (1)\prec \Theta (\lg n)\prec \Theta (n)\prec \Theta (n\lg n)\prec \Theta (n^2)\prec \Theta (n^3)\prec \Theta (2^n)\prec \Theta (n!)$$

The two master rules behind it: any polylog is beaten by any positive polynomial (${\lg }^{b}n=o(n^a)$), and any polynomial is beaten by any exponential ($n^b=o(a^n)$ for $a > 1$). And $\lg (n!)=\Theta (n\lg n)$ — the seed of the comparison-sort lower bound.