Big-O gets taught as a ranking — constant beats logarithmic beats linear, and so on down the list — and that framing survives right up until someone's O(n log n) solution times out against an O(n²) one on the same input. The ranking is not wrong. It is just answering a different question than the one people think it answers.
What the notation actually says
O(f(n)) is a statement about eventual growth: beyond some input size, the running time is bounded above by a constant multiple of f(n). Two things in that sentence do a lot of work. 'Beyond some input size' means small inputs are explicitly excluded. 'A constant multiple' means the constant is deliberately discarded.
So an algorithm that takes 1000·n steps and one that takes 2·n steps are both O(n), and on any real input the second is five hundred times faster. Big-O did not lie. It answered how the cost scales, not how large the cost is.
Comparison sorts are O(n log n) with a real constant attached — cache misses, branch mispredictions, comparison function calls. A counting sort over a small value range is O(n) with a tiny constant. On n = 2·10^5 the gap is enough to be the difference between passing and timing out.
Reading the constraint line backwards
The most practical use of complexity is not analysing your solution afterwards. It is choosing a target before you start. Judges are typically calibrated to something like 10^8 elementary operations per second, and the problem setter picks n to fence off the complexity they do not want.
- →n ≤ 10 — exponential is fine. Think permutations, subsets, brute force search.
- →n ≤ 20 — 2^n with bitmask DP.
- →n ≤ 500 — O(n³) is usually intended. Floyd–Warshall, interval DP.
- →n ≤ 5,000 — O(n²) is intended.
- →n ≤ 10^5 — O(n log n). Sorting, heaps, binary search, balanced structures.
- →n ≤ 10^6 and above — O(n) or O(n log log n). Linear scans, counting, sieves.
That table is worth more than any amount of after-the-fact analysis. If n is 10^5 and your idea is quadratic, you know before writing a line that the idea is wrong, and you have saved twenty minutes.
Amortised is not average
Appending to a dynamic array is amortised O(1): a single append can cost O(n) when the array resizes, but any sequence of n appends costs O(n) in total, so the per-operation average across the sequence is constant. This is a worst-case guarantee about the sequence, not a probabilistic claim.
Average-case is a different animal — it is a claim about the distribution of inputs. Quicksort is average-case O(n log n) and worst-case O(n²), and the worst case is reachable by an adversary who knows your pivot rule. Contest setters have been known to know your pivot rule.
Count the space you forgot
Recursion costs stack space proportional to depth. A recursive solution on a degenerate tree of 10^5 nodes is O(n) space whether or not you allocated anything. String slicing in most languages copies. Building the full traversal to index into it is O(n) space where a counter would have been O(1). Space limits are usually generous enough to hide this, right up until they are not.
The habit worth building
Before you code: read n, pick the target complexity, then design toward it. After you code: state the bound out loud, including space, and check it against the target you picked. If they disagree, you learned something before the judge told you.
Reading about a pattern is not the same as producing it under time pressure. The problems that drill this are in the curriculum, in order.