Counting sort runs in O(n+k) — when does the k term make it the wrong choice?
answer
- Two terms in that bound, not one
- What does k actually measure?
- One counter per possible value
- A 32-bit key means billions of slots
- Compare n + k against n log n
basics
~20 sCounting sort zeroes and sweeps one counter per possible key value, so k is the key range, not the element count. A 32-bit key means billions of counters however few records you hold; it wins only while k stays near n.
solid answer
~50 sThe gate is the key **range**, not the element count. Sorting 50 million event records by a 32-bit account identifier needs one counter per possible value: about 4.3 billion of them, tens of gigabytes before a single record is placed, and an O(k) sweep to zero and read them that no amount of input smallness reduces. A comparison sort on the same input does on the order of n log n ≈ 1.3 billion comparisons in a few hundred megabytes. The rule of thumb is that counting sort wins while k is O(n), and is at best defensible while n + k stays comfortably under n log n. Two secondary effects bite before the hard limit: a large counters array falls out of cache, so the scattered increments and reads get slow, and the zeroing cost is paid even for key values that never occur.
go deeper
Remember the bound as O(n + k) with two separate terms, and that k is the span of possible key values. Being able to say "a wide key range rules it out" is enough at this level.
Explain why a sparse range costs as much as a dense one, and do the memory arithmetic out loud for a wide key. Know the k = O(n) precondition rather than quoting linear time unconditionally.
Diagnose it from symptoms — memory and latency insensitive to input size — and confirm by computing the range over real data. Be ready to defend keeping the comparison sort because its cost carries no data precondition.
Frame it as a choice between a bounded, assumption-free cost and a faster one contingent on a property of the data, and say who is responsible for that property staying true.
## Two terms, and either can dominate O(n + k) is often misread as "linear, so it always wins". It is linear in **two independent quantities**: `n`, the number of records, and `k`, the size of the key **range** — `max - min + 1`, the count of possible key values, not the count of distinct values actually present. That distinction is the whole question. An array indexed by key value must have a slot for every value in the range, occupied or not. ## The arithmetic that ends the argument Take 50 million event records to be sorted by a 32-bit account identifier. The range is 2^32 ≈ 4.29 billion values. At four bytes per counter that is roughly 17 GB of counters; at eight bytes (needed if any single key could hold more than 4 billion records, and often the natural width anyway) roughly 34 GB. Before touching a record, the algorithm must allocate that, zero it — an O(k) sweep over billions of entries — and later sweep it again for the prefix sums. With n = 5 × 10^7 and k = 4.29 × 10^9, k is about 86 times n. The linear-time promise has become a term two orders of magnitude larger than the input. Against it: a comparison sort does about n log₂ n ≈ 5 × 10^7 × 26 ≈ 1.3 × 10^9 comparisons, in memory proportional to the records themselves. It is asymptotically "worse" and wins by a mile. This is the cleanest illustration in the whole sorting family that an asymptotic label is a claim about growth, not a promise about a specific input. ## The rule of thumb Counting sort is the right tool while **k = O(n)** — the classic textbook precondition, and in practice while k is at most a small multiple of n. Loosely, the break-even against a comparison sort is around `n + k` versus `n log n`, so k may be as large as roughly `n log n` before the time argument fails outright. But the time argument is rarely what kills it first: **memory does**. The counters are a hard allocation, sized by the range, paid in full whether the input is one record or a billion. The healthy end of the spectrum is the byte-key case: 20 million pixel records keyed by an 8-bit luminance value. k = 256, one kilobyte of counters, resident in cache for the entire run, and three straight sweeps over the records. Nothing based on comparisons comes close, and the margin is not subtle. ## The effects that bite before the hard limit **Cache.** A 256-entry counters array lives in L1 and the histogram pass is essentially free. Push k into the millions and each increment is a scattered write into an array far larger than cache, so the histogram pass turns into a stream of cache misses. The asymptotics do not change; the constant factor degrades badly, and a benchmark on a small synthetic range will not show it. **Sparsity.** The zeroing and prefix passes are O(k) irrespective of occupancy. A range of ten million values holding ten thousand distinct keys still pays for ten million counters, twice. Cost tracks the range, never the population. **Allocation churn.** If the sort sits on a hot path, a large counters array is allocated or cleared on every call, and that cost repeats per call, per concurrent worker. ## Diagnosing it in production The symptom is characteristic: memory usage jumps to a plateau that does not move when the input shrinks, or the sort's time barely responds to halving n. Both point at the k term. The confirmation is arithmetic, not profiling — compute `max - min + 1` over a real sample and compare it to n. If the range came from an identifier, a hash, a timestamp in microseconds or a floating-point measurement, it is almost certainly disqualifying; if it came from an enumerated status, a small band index, a byte, an age or a day-of-year, it is almost certainly fine. ## What to do instead When the range is too wide, the answer is a different algorithm, not a bigger counters array. Widening the counters is the trap: it makes the memory problem worse for no gain, since the range is a property of the data. Two legitimate moves exist — reduce the range so the precondition genuinely holds (sort by a derived small key such as a band or bucket index, then resolve within groups), or accept the comparison sort's n log n, which is bounded, predictable and needs no assumption about the keys at all. The second is usually right, and choosing it is not a failure to optimise: an O(n log n) algorithm with a small constant and no data precondition is a better default than a linear one whose linearity is contingent on a fact nobody is guarding.
- If only ten thousand distinct identifiers appear in the input, does that rescue counting sort?No. The counters array is indexed by key value, so its size is set by the range spanned, not by how many values occur. A range of billions with ten thousand occupants still allocates, zeroes and sweeps billions of slots. Sparsity is exactly the case counting sort handles worst — every absent value costs the same as a present one in both memory and the O(k) passes.
- The counters array fits in memory, but the sort is slower than the comparison sort anyway. What would you look at?Cache behaviour and the fixed O(k) passes. Once the counters exceed cache, every histogram increment is a scattered write into cold memory, and the zeroing plus prefix sweeps run over the whole range whatever the input size. Measure how the time responds to halving n: if it barely moves, the k term and its memory traffic dominate, and no tuning of the record passes will help.
- What symptom in production would make you suspect the k term rather than the data volume?Memory and latency that are insensitive to input size. A plateau in resident memory that does not fall when a batch is half as large, or a sort time that halves far less than the record count did, both say a fixed range-sized cost dominates. Confirm arithmetically — compute max minus min plus one over a real sample and put it next to n — rather than by profiling alone.
saying these in an interview costs you the question
- Says counting sort is O(n) and therefore always fastest
- Thinks k counts the distinct keys actually present
- Reaches for it on identifier, hash or timestamp keys
- Proposes a wider counters array to fix the memory blow-up
- Ignores that zeroing the counters is itself O(k)
- Treats an asymptotic win as a guarantee at any input size