Short answer
They are mathematical bounds on a function's growth rate: Big-O is an upper bound, Big-Omega is a lower bound, and Big-Theta is a tight bound (both upper and lower). They are not synonyms for worst and best case; any case can be described with any of the three. For example, QuickSort's worst case is Θ(N^2), and its best case is Θ(N log N).
Explanation
Saying an algorithm is O(N^2) mathematically guarantees that its time use will not grow faster than a constant times N^2 as the input approaches infinity. Big-Omega (Ω) guarantees a lower growth bound, and Big-Theta (Θ) combines both bounds to describe the growth rate precisely. A common confusion is to associate O with worst case and Ω with best case. Instead, first specify the case (for example, the worst case of linear search), then describe its function using any notation: linear search's worst case is Θ(N), and its best case is Θ(1). If best and worst cases have the same growth rate, as in MergeSort, its runtime is Θ(N log N) in all cases. In practice, O is often used imprecisely to mean Θ for the worst case.
Code example
def linear_search(items, target):
for i, x in enumerate(items):
if x == target:
return i # best case: found first → Θ(1)
return -1 # worst case: found last or missing → Θ(n)
# O, Ω and Θ describe the growth of a function — not "worst / best / average case":
# worst case: T(n) = Θ(n) (so also O(n) and Ω(n))
# best case: T(n) = Θ(1) (so also O(1))
# "Linear search is O(n)" is an upper bound that covers every input; it is not the same thing as "worst case".Common mistakes
- Ignoring memory and space complexity and focusing only on time complexity.