If an algorithm runs in O(n), then O(n²), O(n³), and even O(n!) are technically valid upper bounds too. So when someone asks for an algorithm's Big O complexity, why is the smallest or tightest useful bound expected? Does choosing O(n) instead of a looser bound change what Big O notation means?
4 Answers
Big O describes an upper bound, so an O(n) algorithm is technically also O(n²) and O(n!). But a loose bound is not useful for comparison. We normally report the tightest bound we can justify because it tells us how the algorithm actually scales as the input grows.
The point is to understand how runtime changes with input size. If doubling the input roughly doubles the work, O(n) communicates that. Saying O(n!) would technically satisfy the upper-bound definition, but it would make a linear algorithm sound dramatically worse than it is and make comparisons nearly meaningless.
When people say an algorithm is O(n²), they usually mean that n² is the tightest asymptotic upper bound being reported, often written Θ(n²) when both the upper and lower bounds are known. Big O itself does not require the tightest bound; convention and usefulness are why we normally give it.
Also, O(1) is technically O(n), but calling a constant-time algorithm linear would hide an important performance advantage.
Be careful not to confuse Big O with a lower bound. Big O is an asymptotic upper bound, while Ω is a lower bound and Θ describes a tight bound. In everyday algorithm discussions, people often use “Big O” informally for the tightest growth class, because that is the most informative answer.
So the larger bounds are valid mathematically, but they throw away the information we actually care about when comparing algorithms.