Big O is one of three notations, and it is an upper bound. Omega is the lower bound, Theta is both at once. The distinction sounds academic until you notice how often people claim something Big O does not say.
The three
| Notation | Reads as | Claims |
|---|---|---|
| O(f) | Big O | grows no faster than f — an upper bound |
| Ω(f) | Omega | grows at least as fast as f — a lower bound |
| Θ(f) | Theta | grows exactly like f — both bounds at once |
The everyday analogy: O is "it will take at most an hour", Ω is "it will take at least twenty minutes", Θ is "it takes about forty minutes, give or take a constant".
The consequence people miss
Because O is only an upper bound, every statement below is technically true of an algorithm that takes exactly n steps:
O(n) true, and tight
O(n log n) true - n really does grow no faster than n log n
O(n^2) true
O(2^n) trueSo "this algorithm is O(n²)" does not mean it is slow. It means it is not slower than n². Saying an O(n) algorithm is O(n²) is like saying you are under 200 years old: correct, unhelpful, and not what your listener will assume you meant.
This is why Θ is the honest notation for describing an algorithm you have analysed. In practice almost everyone writes O and means Θ, and that is fine as long as you know the difference — and can say so when someone asks.
Bounds are not cases
This is the confusion worth killing. Best/average/worst case is a statement about which input you get. O/Ω/Θ is a statement about how you are bounding the growth. They are independent, so you can combine them freely.
Take insertion sort:
| Case | Input | Tight bound |
|---|---|---|
| Best | already sorted | Θ(n) |
| Average | random order | Θ(n²) |
| Worst | reverse sorted | Θ(n²) |
You can also say insertion sort is Ω(n) overall — it can never do better than reading the input — and O(n²) overall. Both are true, both are about the algorithm across all inputs, and neither is "the best case" or "the worst case".
So "the best case of Big O" is a category error, and it comes up constantly. Big O is not a case; it is a bound on a function that you may have chosen for any case you like.
Where Omega genuinely earns its keep
Lower bounds are how you prove a problem cannot be solved faster — a statement about the problem, not about one algorithm.
The famous one: any comparison-based sort is Ω(n log n). The proof is a counting argument. There are n! possible orderings, each comparison has two outcomes so it can at best halve the possibilities, and you need log₂(n!) ≈ n log n comparisons to single out one ordering. No cleverness escapes it.
That single result tells you merge sort and heap sort are optimal, and that looking for an O(n) comparison sort is a waste of an afternoon. It is also why the O(n) sorts — counting sort, radix sort — exist: they do not compare elements, so the bound does not apply to them.
The little-o footnote
Occasionally you will meet o(f) (little-o), meaning strictly slower-growing — n is o(n²) but n is not o(n). Big O allows equality; little-o does not. It rarely comes up outside a textbook, but it explains why the two spellings are not interchangeable.
What to remember
- O = upper bound, Ω = lower bound, Θ = both.
- An O(n) algorithm is also legitimately O(n²) — O alone never means "this is slow".
- Θ is what you mean when you have actually analysed something.
- Bounds and cases are different axes. "Best case Θ(n)" is a complete, sensible statement.
- Ω is for proving a problem's floor: comparison sorting is Ω(n log n), which is why merge sort cannot be beaten by comparing.