Big-O, Big-Omega, and Big-Theta

Why This Matters

Saying an algorithm is $O(n^2)$ may be true and useless if the real cost is $\Theta(n)$. The notation must say whether you mean an upper bound, lower bound, or tight growth rate.

Core Idea

Worked example: merge sort is $O(n \log n)$ and $\Omega(n \log n)$ in the comparison model, so its running time is $\Theta(n \log n)$.

Common Mistakes

• Using Big-O when Big-Theta is known.
• Saying "at least Big-O." Lower bounds use Big-Omega.
• Treating all upper bounds as tight. $n$ is also $O(n^2)$.

Exercises

• Explain why $3n + 7$ is $\Theta(n)$.
• Give a loose but true Big-O bound for binary search.
• State why comparison sorting has an $\Omega(n \log n)$ lower bound.

Next Topics

• Master theorem
• Sorting

References

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 3.
• Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.).