Big-Omega, Big-Theta and Little-o

Bounds from below and both sides

Big-Omega gives an asymptotic lower bound: f(n) = Ω(g(n)) if there exist c > 0 and n₀ with f(n) ≥ c · g(n) for all n ≥ n₀. Big-Theta gives a tight bound: f(n) = Θ(g(n)) if f is both O(g(n)) and Ω(g(n)), meaning f grows at exactly the same rate as g, up to constant factors. So 3n² + 10n is Θ(n²), while it is O(n³) but not Θ(n³). Little-o is a strict upper bound: f(n) = o(g(n)) if f grows strictly slower than g (the ratio f/g tends to 0), for example n = o(n²) but n² is not o(n²). Little-omega is the strict lower bound. In everyday engineering, people say "Big-O" when they mean a tight bound, as in "merge sort is O(n log n)". In exams and theory, use Θ when you mean tight. Lower bounds also describe problems: any comparison-based sorting algorithm needs Ω(n log n) comparisons in the worst case, so merge sort is optimal among comparison sorts.

Bounds for the same function

f(n) = 4n log n + 3n.

f(n) = 4n log n + 3n

O(n log n)    true  (tight upper bound)
O(n^2)        true  (but loose)
Omega(n)      true  (but loose)
Omega(n log n) true
Theta(n log n) true  (both O and Omega of n log n)
Theta(n^2)    false (not Omega(n^2))
o(n^2)       true  (grows strictly slower than n^2)
o(n log n)    false (grows at the same rate)

Speed limits and minimums

Big-O is a speed limit ("never faster than"), Big-Omega is a minimum speed ("never slower than") and Big-Theta says the car always cruises within a band around one speed.

Quick check: What does f(n) = Θ(g(n)) mean?

• f grows strictly slower than g
• f is both O(g(n)) and Ω(g(n)), so it grows at the same rate as g
• f is always smaller than g
• f and g are equal for all n