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 c\,g(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 c\,g(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)) \iff 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.