If an algorithm runs in O(n), then O(n²), O(n³), and even O(n!) are technically valid upper bounds too. So why do people expect the smallest or tightest bound when asking for an algorithm's Big O complexity? Does using the tightest bound change what Big O notation means?
4 Answers
The goal is to understand how the running time grows as the input grows. An O(1) algorithm stays roughly constant, O(n) grows proportionally with the input, and O(n²) grows much faster. Reporting an unnecessarily large upper bound hides that behavior, which is why the tightest bound is normally preferred.
Big O describes an upper bound, so all of those statements can technically be true. But a loose bound is not very useful. Saying an O(n) algorithm is O(n!) is like answering that a $90 grocery bill was less than $100,000—it’s correct, but it tells you almost nothing. In practice, people give the tightest useful asymptotic bound so algorithms can be compared meaningfully.
One terminology detail: Big O itself means an upper bound, not necessarily the exact or tightest one. When people say an algorithm is O(n), they often mean that n is the tightest relevant upper bound; formally, Θ(n) expresses a tight asymptotic bound. So an algorithm can be both O(n) and O(n²), but O(n) is the more informative description.
For example, if the running time is n² + n, it is O(n²), O(n³), and so on. We simplify it to O(n²) because that is the dominant growth rate and the tightest useful bound.
The purpose is comparison, not reporting an exact stopwatch time. If one solution is O(n) and another is O(n²), the difference becomes increasingly important as the input grows. Choosing a deliberately loose bound can make a fast algorithm look worse than it really is and lead to poor design decisions.
Exactly. If every algorithm were described as O(n!), the notation would still be technically correct but would stop helping us distinguish efficient algorithms from inefficient ones.