Ask Which Bound You Mean

This demo note exists to validate ordered notes across more than one course.

The symbols $O$, $\Omega$, and $\Theta$ answer different questions about growth. Instead of memorizing “worst, best, exact,” it is safer to ask whether the claim gives an asymptotic upper bound, lower bound, or both.

For example, $3n + 8$ is in all of $O(n^2)$, $\Omega(n)$, and $\Theta(n)$. The last statement is the tight one, but the other two are still mathematically valid.