Little-o and Little-ω

Little-o: Strictly Slower Growth

$f(n) = o(g(n))$ if for every positive constant $c$, there exists $n_0$ such that for all $n \ge n_0$:

$0 \le f(n) < c \cdot g(n)$

Equivalently, the limit ratio is zero:

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

In words: $f$ grows strictly slower than $g$. No matter how small a constant factor you pick, $f$ eventually falls below $c \cdot g$.

Little-$\omega$: Strictly Faster Growth

$f(n) = \omega(g(n))$ if for every positive constant $c$, there exists $n_0$ such that for all $n \ge n_0$:

$0 \le c \cdot g(n) < f(n)$

Equivalently:

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

In words: $f$ grows strictly faster than $g$.

Relationship to Big-O / Big-$\Omega$

Big	Little	Meaning
$f = O(g)$	May be tight or loose; $3n^2 = O(n^2)$ and $3n^2 = O(n^3)$ are both true
$f = o(g)$	Always non-tight; $3n^2 = o(n^3)$ is true, but $3n^2 = o(n^2)$ is false
$f = \Omega(g)$	May be tight or loose; $3n^2 = \Omega(n^2)$ and $3n^2 = \Omega(n)$ are both true
$f = \omega(g)$	Always non-tight; $3n^2 = \omega(n)$ is true, but $3n^2 = \omega(n^2)$ is false

Concrete Examples

Expression	$O$	$\Omega$	$\Theta$	$o$	$\omega$
$3n^2$ vs $n^2$	✓	✓	✓	✗	✗
$3n^2$ vs $n^3$	✓	✗	✗	✓	✗
$3n^2$ vs $n$	✗	✓	✗	✗	✓
$n \log n$ vs $n^2$	✓	✗	✗	✓	✗
$n$ vs $\log n$	✗	✓	✗	✗	✓

The Quantifier Difference

The distinction is in the quantifier for $c$:

• Big-O: $\exists c > 0, \exists n_0: \forall n \ge n_0, f(n) \le c \cdot g(n)$ — some constant works.
• Little-o: $\forall c > 0, \exists n_0: \forall n \ge n_0, f(n) < c \cdot g(n)$ — every constant works.

For $3n^2$ and $n^2$: pick $c = 2$. Then $3n^2 \le 2n^2$ fails for all $n$, so $3n^2 \neq o(n^2)$. But for $3n^2$ and $n^3$: for any $c$, pick $n_0 = 3/c$ and the inequality $3n^2 < c n^3$ holds beyond that, so $3n^2 = o(n^3)$.

Common Pitfalls

1. $O$ is not “grows exactly like”: $n = O(n^2)$ is true; $O$ means “at most.”
2. Little-o requires strictness: $\Theta$ functions are not in $o$ of each other. $3n^2 = \Theta(n^2)$ but $3n^2 \neq o(n^2)$.
3. Lower bounds work symmetrically: $\Omega$ means “at least,” $\omega$ means “strictly greater.”
4. Constants are irrelevant for $o$ and $\omega$: $f(n) = o(c \cdot g(n))$ iff $f(n) = o(g(n))$.
5. The limit test: if $\lim_{n \to \infty} f/g$ is finite and non-zero, then $f = \Theta(g)$ and neither $f = o(g)$ nor $f = \omega(g)$ can hold.

Summary

Notation	Definition	Limit form	Mnemonic
$f = o(g)$	$\forall c > 0, \exists n_0: f(n) < c \cdot g(n)$	$\lim f/g = 0$	”strictly less"
$f = \omega(g)$	$\forall c > 0, \exists n_0: f(n) > c \cdot g(n)$	$\lim f/g = \infty$	"strictly greater"
$f = \Theta(g)$	$\exists c_1, c_2 > 0: c_1 g \le f \le c_2 g$	$\lim f/g \in (0, \infty)$	"exactly”
Key insight	$o$ and $\omega$ exclude asymptotic equality	$3n^2 \neq o(n^2)$