Landau Sets (Big-O, Θ, Ω)

Landau sets (named after Edmund Landau) are classes of functions that
capture asymptotic growth. Three flavours:

Big-O $O(g)$ — the upper bound:

Big-Ω $\Omega(g)$ — the lower bound:

Big-Θ $\Theta(g)$ — both bounds:

The constants $c$ and $n_0$ absorb multiplicative and finite-input noise —
we only care about behavior "in the limit".

Examples:
- $3n + 5 \in O(n)$: take $c = 4, n_0 = 5$. For $n \geq 5$, $3n+5 \leq 4n$.
- $5n^2 + 100n \in \Theta(n^2)$: bounded above and below by $cn^2$.
- $n^3 \notin O(n^2)$: any $cn^2$ is eventually beaten by $n^3$.
- $\sin(n) \in O(1)$: bounded by $1$.

The notation $f(n) = O(g(n))$ (with $=$) is abuse but extremely common. Strictly
$f(n) \in O(g(n))$ — but everyone writes "$=$".

Some Landau-set inclusions are proved by induction on a natural number. The classic: $\forall a \in \mathbb{N}.\, n^a \in O(2^n)$.

Theorem. For every $a \geq 0$, $n^a \leq c \cdot 2^n$ for all sufficiently large $n$ (i.e. $n^a \in O(2^n)$).

Proof by induction on $a$.
- Base $a = 0$: $n^0 = 1 \leq 2^n$ for all $n \geq 0$. So $c = 1$ works. ✓
- Base $a = 1$: $n^1 = n$. We need $n \leq c \cdot 2^n$ for large $n$. For $n \geq 1$, $2^n \geq n$, so $c = 1$ works. ✓
- Step $a + 1$ (with $a \geq 1$): Assume $n^a \leq c \cdot 2^n$ for large $n$ (IH). Then $n^{a+1} = n \cdot n^a \leq n \cdot c \cdot 2^n$. We need $n \cdot 2^n \leq c' \cdot 2^n$, i.e. $n \leq c'$. For $n \geq c'$, this holds. So $c' = c \cdot c$ works (or just $n$ is bounded by some constant past the threshold).

Wait — that's not quite right. Let me redo more carefully:

$n^{a+1} = n \cdot n^a \leq n \cdot (c \cdot 2^n)$ by IH.

For $n \geq 2$: $n \leq 2^n$ (since $2^n$ grows faster than $n$). So $n^{a+1} \leq 2^n \cdot c \cdot 2^n = c \cdot 2^{n+1} = 2c \cdot 2^n$.

So $n^{a+1} \leq (2c) \cdot 2^n$ for $n \geq \max(c, 2)$. This is in $O(2^n)$. ✓

Reading. The trick: use $n \leq 2^n$ as a separate bound, then combine. This is a general technique: when proving polynomial vs exponential, isolate the 'extra' polynomial factor and bound it by another exponential.

Generalisation. The same proof technique shows $n^a \in O(b^n)$ for any $b > 1$.