Little o and Little Omega — Strictly Slower, Strictly Faster
Big O allows "equal to or less than". Sometimes you need to say something sharper: this algorithm is not just no worse than that one, it is genuinely, eventually better. The little letters say exactly that, and they finish the family of five growth notations.
The rule
Little o: the ratio shrinks to zero. Little ω: the ratio grows forever.
Compare f(n) with g(n) by looking at the ratio f(n) / g(n) as n grows large:
- f is o(g), little o: the ratio heads to zero. f grows strictly slower than g. Example: n is o(n²), because n / n² = 1/n shrinks towards 0.
- f is ω(g), little omega: the ratio grows without limit. f grows strictly faster. Example: n² is ω(n), because n² / n = n keeps growing.
The big letters allow the ratio to settle on a constant; the little letters do not:
| Notation | Ratio f/g as n grows | Reads like |
|---|---|---|
| f = o(g) | goes to 0 | f < g |
| f = O(g) | stays below some constant | f ≤ g |
| f = Θ(g) | stays between two positive constants | f = g |
| f = Ω(g) | stays above some positive constant | f ≥ g |
| f = ω(g) | grows without limit | f > g |
So 3n is O(n) and Θ(n), but not o(n): the ratio 3n / n stays at 3 forever and never shrinks to zero. A function is never o of itself.
The comparisons in "reads like" are about growth rates, not about values: 1000n is o(n²) even though 1000n is bigger than n² for every n below 1000.
The shortcut
Write the ratio, cancel what you can, and ask where it heads: to zero (little o), to a constant (Θ), or off to infinity (little ω).
Write the ratio
(log n) / n.
Drills
Answer fast — trust the rule.
Is n in o(n)?
Which statement is true?
f(n) / g(n) grows without limit as n grows. What do we write?
If f is o(g), which of these must also be true?
Remember
- Little o: f/g shrinks to zero. Little ω: f/g grows without limit.
- Big letters allow a constant ratio; little letters forbid it, so 3n is O(n) but not o(n).
- The trap: these compare growth, not values — 1000n is still o(n²).