Why this is O(n)
Why O(n + k). k is the value range (hi). Counting is O(n), the output build is O(n + k). If k is bounded (e.g. byte values, k = 256), this is *linear in n*. With unbounded k, it's O(n + k).
Why it beats comparison sort. Comparison-based sorts have an Ω(n log n) lower bound. Counting sort sidesteps the bound by *not comparing* — it indexes. Trade-off: only works for integer-like keys.
How to recognize linear complexity in the wild
O(n) is one pass over the input. The strongest signal is a single for-loop that touches every element exactly once, or a recursion whose depth equals the input size with constant work per level.
The eight rungs of the ladder
Big-O classifies the asymptotic growth of a function, not the wall-clock time. The ladder Bugdle uses has eight rungs ordered from cheapest to most ruinous: O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!). The puzzle's answer sits at rung 3 of 8. The four-guess budget plus higher/lower hints means the puzzle is solvable in at most ⌈log₂(8)⌉ = 3 perfectly-read guesses; the fourth attempt absorbs misreads of the snippet.
Common confusables
Nested loops aren't automatically quadratic — the inner loop has to range over n, not a constant. A loop that always runs ten iterations is still O(1) work per outer iteration. Similarly, a recursive function isn't automatically exponential just because it calls itself twice — if the recursion has overlapping subproblems and you memoise, you collapse back to polynomial. Always ask: what does n really mean here, and how many distinct subproblems are there?
External reference: Big O notation — Wikipedia.