Foundations
Little-o and Little-omega Notations
Difficulty: Advanced
When a paper claims an algorithm runs in O(n^2), that statement leaves a question wide open: does the algorithm actually take quadratic time, or could the bound be loose? Little-o and little-omega are the notations that close that gap....
Little-o and Little-omega Notations
When a paper claims an algorithm runs in O(n^2), that statement leaves a question wide open: does the algorithm actually take quadratic time, or could the bound be loose? Little-o and little-omega are the notations that close that gap. f(n) = o(g(n)) says f grows strictly slower than g, never matching its rate, and f(n) = omega(g(n)) says f grows strictly faster. They are the precision tools of theoretical CS.
This lesson defines both notations using the formal limit-based criterion: f(n) = o(g(n)) iff lim f(n)/g(n) = 0, and f(n) = omega(g(n)) iff lim f(n)/g(n) = infinity. You will prove and disprove o and omega claims for common function pairs (n vs n^2, log n vs n, n vs n log n, 2^n vs n^k), use these notations to rank growth rates strictly, and see how the full five-notation system fits together: O and Omega allow equality, Theta requires it, while o and omega forbid it.
This lesson builds on three earlier asymptotic foundations. From Big-O Notation (Upper Bound) you have non-strict ceilings; from Big-Omega Notation (Lower Bound) you have non-strict floors; and from Big-Theta Notation (Tight Bound) you have the exact-rate case. Little-o and little-omega simply require the inequality to be strict, ruling out the matching case that Big-O and Big-Omega permit.
With all five notations under your belt, you will be ready for Complexity Classes (Conceptual Overview), where these comparisons get used to separate classes like P and NP.
Prerequisites:
Big-O Notation (Upper Bound)Big-Omega Notation (Lower Bound)Big-Theta Notation (Tight Bound)Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Define little-o notation using the formal limit definition and contrast it with Big-O.
Define little-omega notation using the formal limit definition and contrast it with Big-Omega.
Prove or disprove little-o and little-omega relationships for given function pairs using limits.
Apply these notations to classify the relative growth rates of common functions.
Explain the connection between all five asymptotic notations (O, Omega, Theta, o, omega) as a complete system.
Why This Matters
01
Little-o and little-omega let you make stronger claims than Big-O and Big-Omega. Saying f(n) = o(n^2) is more informative than f(n) = O(n^2) because it rules out quadratic growth entirely.
02
These notations appear throughout research papers, advanced textbooks (CLRS, Sipser), and competitive programming editorial analyses -- you need them to read and write precise complexity arguments.
03
Understanding the strict vs. non-strict distinction helps you reason about tight bounds: if f = O(g) but f is NOT o(g), then f and g grow at the same asymptotic rate, which means Theta is appropriate.
04
Many advanced proofs in algorithm design (lower bounds, reductions, approximation ratios) rely on little-o and little-omega to separate complexity classes.
Key Terms
6 terms you'll encounter in this lesson
Little-o (o)
f(n) = o(g(n)) means f grows strictly slower than g. Formally, for every positive constant c > 0, there exists n0 such that f(n) < c * g(n) for all n >= n0. Equivalently, lim(n->inf) f(n)/g(n) = 0.
Little-omega (omega)
f(n) = omega(g(n)) means f grows strictly faster than g. Formally, for every positive constant c > 0, there exists n0 such that f(n) > c * g(n) for all n >= n0. Equivalently, lim(n->inf) f(n)/g(n) = infinity.
Strict bound
A bound that excludes equality. Little-o is a strict upper bound (f grows slower, never at the same rate), while Big-O is a non-strict upper bound (f grows at most as fast, including the same rate).
Limit definition
The limit-based characterization of asymptotic notations. lim f/g = 0 implies o, lim f/g = infinity implies omega, and 0 < lim f/g < infinity implies Theta.
Asymptotic dominance
Function g asymptotically dominates f if f(n) = o(g(n)). This means g eventually outgrows f by an arbitrarily large factor.
Asymptotic equivalence
Two functions f and g are asymptotically equivalent if f(n) = Theta(g(n)), meaning neither is o of the other. Their ratio converges to a positive constant.
Heads Up
Common misconceptions to watch out for
"Little-o is just Big-O with smaller constants"
Little-o is not about constants at all. f(n) = o(g(n)) means f grows strictly slower than g -- no constant factor can close the gap. For example, n = o(n^2) because n/n^2 = 1/n approaches 0, regardless of any constant multiplier.
"If f(n) = O(g(n)), then f(n) = o(g(n))"
Wrong. Big-O allows equality: 2n = O(n) is true, but 2n = o(n) is false because 2n/n = 2, which does not approach 0. Little-o is a strictly stronger statement.
"Little-o and little-omega are rarely used, so I can skip them"
They are standard notation in CLRS, research papers, and graduate-level algorithms courses. You cannot read advanced complexity proofs without them. They also appear in competitive programming editorial analyses.
"f(n) = o(g(n)) and f(n) = omega(g(n)) can both be true simultaneously"
Impossible. If f = o(g), the ratio f/g goes to 0. If f = omega(g), the ratio goes to infinity. These are mutually exclusive -- a limit cannot be both 0 and infinity.