Why do we usually give the tightest Big O bound?
Asked by
MellowCactus47
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?
Answers
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.
Reply to this answer
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.
Reply to this answer
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.
Reply to this answer
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.
MellowCactus47: So the larger bounds are valid mathematically, but they throw away the information we actually care about when comparing algorithms.
Reply to this answer
Add your answer
Answers are reviewed before publication.
CleverBadger19: Also, O(1) is technically O(n), but calling a constant-time algorithm linear would hide an important performance advantage.