Big O, Big Theta and Big Omega
"This algorithm is O(n²)" is one of the most quoted sentences in programming, and one of the most misunderstood. The letter in front matters. O, Ω (Omega) and Θ (Theta) are three different promises about growth, and mixing them up leads to wrong conclusions about real code.
The rule
O is a ceiling, Ω is a floor, Θ is both at once.
Each notation compares a function f(n), such as the number of steps an algorithm takes, with a simpler function g(n), for all large enough n and ignoring constant factors:
- f is O(g): f grows no faster than g. An upper bound.
- f is Ω(g): f grows no slower than g. A lower bound.
- f is Θ(g): both at once. f grows at the same rate as g. A tight bound.
To simplify a step count, keep only the fastest-growing term and drop its constant factor:
3n² + 5n + 7 → Θ(n²)
100n + 2000 → Θ(n)
4n³ + n² log n → Θ(n³)Because O is only a ceiling, a loose ceiling is still true: n is O(n²), just as "under a week" is a true description of a 5-minute walk. When people say "O(n)" in everyday talk, they usually mean the tight bound Θ(n).
These bounds are separate from best case and worst case. Linear search takes 1 step in its best case and n in its worst case. Its worst case is Θ(n); its best case is Θ(1).
The shortcut
Simplify first (biggest term, no constant), then pick the letter by the promise: at most → O, at least → Ω, exactly this rate → Θ.
Simplify
The n² term wins for large n, and the 2 is dropped: the rate is n².
Drills
Answer fast — trust the rule.
Simplify 5n + 100 to its growth rate.
Is n in O(n²)?
An algorithm's running time is both O(n log n) and Ω(n log n). What else can you say?
What is 4n³ + n² in Θ notation?
Which statement about f(n) = 3n² is false?
Remember
- O is a ceiling, Ω is a floor, Θ is both.
- Simplify first: keep the biggest term, drop its constant.
- The trap: O(n²) can be true of a linear algorithm; best and worst case are a separate question.