Asymptotic Notation

March 2026 · 22 min read

In the introduction, we saw Big-O informally. Now we'll define all five asymptotic notations precisely, prove their properties, and understand when to use each.

Big-O: Upper Bound

Definition: $f(n) = O(g(n))$ if $\exists\; c > 0,\; n_0 \geq 0$ such that $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$.

Big-O gives an upper bound on growth. "$f$ grows no faster than $g$."

Limit characterization

If $\lim_{n \to \infty} \frac{f(n)}{g(n)} = L$ where $0 \leq L < \infty$, then $f(n) = O(g(n))$.

Proof: If $L$ is finite, then for any $\epsilon > 0$, $\frac{f(n)}{g(n)} < L + \epsilon$ for all sufficiently large $n$. Choose $c = L + 1$ and the definition is satisfied. ✔

Example: $5n^2 + 3n \log n = O(n^2)$

$$\lim_{n \to \infty} \frac{5n^2 + 3n\log n}{n^2} = 5 + 3\lim_{n \to \infty}\frac{\log n}{n} = 5 + 0 = 5$$

The limit is finite, so $5n^2 + 3n \log n = O(n^2)$. ✔

Big-Ω: Lower Bound

Definition: $f(n) = \Omega(g(n))$ if $\exists\; c > 0,\; n_0 \geq 0$ such that $f(n) \geq c \cdot g(n)$ for all $n \geq n_0$.

Big-Ω gives a lower bound. "$f$ grows at least as fast as $g$."

Limit characterization

If $\lim_{n \to \infty} \frac{f(n)}{g(n)} = L$ where $0 < L \leq \infty$, then $f(n) = \Omega(g(n))$.

Relationship to Big-O

$f(n) = O(g(n))$ if and only if $g(n) = \Omega(f(n))$. They are mirror images.

Big-Θ: Tight Bound

Definition: $f(n) = \Theta(g(n))$ if $\exists\; c_1, c_2 > 0,\; n_0 \geq 0$ such that $c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$ for all $n \geq n_0$.

Equivalently: $f(n) = \Theta(g(n))$ iff $f(n) = O(g(n))$ AND $f(n) = \Omega(g(n))$.

Big-Θ means "$f$ grows at exactly the same rate as $g$, up to constant factors."

Limit characterization

If $\lim_{n \to \infty} \frac{f(n)}{g(n)} = L$ where $0 < L < \infty$, then $f(n) = \Theta(g(n))$.

Example: $\frac{n(n-1)}{2} = \Theta(n^2)$

$$\lim_{n \to \infty} \frac{n(n-1)/2}{n^2} = \lim_{n \to \infty} \frac{n-1}{2n} = \frac{1}{2}$$

Since $0 < \frac{1}{2} < \infty$, we have $\frac{n(n-1)}{2} = \Theta(n^2)$. ✔

Little-$o$: Strictly Smaller

Definition: $f(n) = o(g(n))$ if for every $c > 0$, $\exists\; n_0$ such that $f(n) < c \cdot g(n)$ for all $n \geq n_0$.

Equivalently: $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$.

Little-$o$ means "$f$ grows strictly slower than $g$." It's like $<$ compared to Big-O's $\leq$.

Example: $n = o(n^2)$

$$\lim_{n \to \infty} \frac{n}{n^2} = \lim_{n \to \infty} \frac{1}{n} = 0 \quad \checkmark$$

Non-example: $n^2 \neq o(n^2)$

$$\lim_{n \to \infty} \frac{n^2}{n^2} = 1 \neq 0$$

Little-$\omega$: Strictly Larger

Definition: $f(n) = \omega(g(n))$ if for every $c > 0$, $\exists\; n_0$ such that $f(n) > c \cdot g(n)$ for all $n \geq n_0$.

Equivalently: $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$.

$f(n) = o(g(n))$ iff $g(n) = \omega(f(n))$.

Comparison of All Five Notations

Notation	Intuition	Analogy	Limit
$f = O(g)$	$f$ grows no faster than $g$	$f \leq g$	$\lim \frac{f}{g} < \infty$
$f = \Omega(g)$	$f$ grows no slower than $g$	$f \geq g$	$\lim \frac{f}{g} > 0$
$f = \Theta(g)$	$f$ and $g$ grow at the same rate	$f = g$	$0 < \lim \frac{f}{g} < \infty$
$f = o(g)$	$f$ grows strictly slower than $g$	$f < g$	$\lim \frac{f}{g} = 0$
$f = \omega(g)$	$f$ grows strictly faster than $g$	$f > g$	$\lim \frac{f}{g} = \infty$

Properties of Asymptotic Notation

Transitivity

If $f = O(g)$ and $g = O(h)$, then $f = O(h)$. Same for $\Omega$, $\Theta$, $o$, $\omega$.

Reflexivity

$f = O(f)$, $f = \Omega(f)$, $f = \Theta(f)$. But NOT $f = o(f)$ or $f = \omega(f)$.

Symmetry

$f = \Theta(g)$ iff $g = \Theta(f)$. Big-Θ is the only symmetric one.

Transpose symmetry

$f = O(g)$ iff $g = \Omega(f)$. And $f = o(g)$ iff $g = \omega(f)$.

Sum and product

$O(f) + O(g) = O(\max(f, g))$ (sum rule)
$O(f) \cdot O(g) = O(f \cdot g)$ (product rule)
$O(c \cdot f) = O(f)$ for any constant $c > 0$

The Growth Hierarchy

These functions are ordered by growth rate (each is $o$ of the next):

$$1 \prec \log \log n \prec \log n \prec \sqrt{n} \prec n \prec n \log n \prec n^2 \prec n^3 \prec 2^n \prec n! \prec n^n$$

Where $f \prec g$ means $f = o(g)$. Each function grows infinitely faster than the one to its left.

Proof: $n^k = o(2^n)$ for any constant $k$

$$\lim_{n \to \infty} \frac{n^k}{2^n}$$

Apply L'Hôpital's rule $k$ times:

$$= \lim_{n \to \infty} \frac{k!}{(\ln 2)^k \cdot 2^n} = 0$$

So any polynomial is $o$ of any exponential. ✔

Proof: $\log n = o(n^\epsilon)$ for any $\epsilon > 0$

Let $m = \log n$, so $n = 2^m$:

$$\frac{\log n}{n^\epsilon} = \frac{m}{2^{m\epsilon}} \to 0 \text{ as } m \to \infty$$

So logarithms grow slower than any polynomial, even $n^{0.001}$. ✔

Summary

There are five asymptotic notations: $O$ (upper), $\Omega$ (lower), $\Theta$ (tight), $o$ (strict upper), $\omega$ (strict lower).
Use the limit test to quickly determine which notation applies.
$\Theta$ is the strongest statement, it means the function matches the bound exactly (up to constants).
The growth hierarchy from constants through polynomials to exponentials to factorials is fundamental.
All log bases are equivalent in Big-O because they differ by a constant factor.