Why does radix sort's linear-time claim quietly collapse back toward n log n for n distinct keys?
answer
- d is not a property of the algorithm
- how many digits for n distinct keys?
- you need k to the d at least n
- log_k(n) digits, minimum
- the base survives as a divisor
basics
~20 sGiving n keys distinct digit strings in base k takes at least log_k(n) digits, so d cannot stay constant as the key domain grows. The cost then becomes about n log n divided by log2(k) — a constant-factor win, not an asymptotic one.
solid answer
~50 sRadix sort costs `O(d(n+k))`, and the trap is treating `d` as a constant in every setting. There are two honest regimes. If the key format is **fixed** — identifiers that are always the same width — then `d = ceil(w/b)` is a constant set by the format, and the sort really is linear in `n`; that is the case where it beats an `n log n` sort asymptotically. But if the keys must stay **distinct** as `n` grows, the domain has to hold at least `n` values, so each key needs at least `log_k(n)` digits and `d >= log_k(n)`. Then `d * n` is at least `n log2(n) / log2(k)`, which is `n log n` again with the base as a divisor. That divisor is the real advantage: one pass extracts `log2(k)` bits of ordering per key, while one comparison yields at most one bit.
go deeper
Know the cost is written O(d times (n plus k)) and that d is the number of digits per key, set by the key format rather than by the algorithm. Resist saying flatly that radix sort is linear.
Do the arithmetic out loud: n distinct keys in base k need at least log_k(n) digits, so the product returns to n log n over log2(k). Be able to state both regimes without contradicting yourself.
Turn the analysis into a decision. Say which regime a given workload is in, and quantify the remaining constant-factor advantage in terms of bits per pass and access pattern rather than asymptotics.
Push back on benchmark claims framed asymptotically. Insist that a proposed non-comparison sort states its key-width assumption and what happens when a future key format widens it.
## The claim and the catch Radix sort's cost is `O(d(n + k))`, where `n` is the record count, `d` the number of digits per key, and `k` the base (the number of buckets). Read `d` and `k` as constants and this is `O(n)`, which is where the folklore "radix sort is linear, so it beats every `n log n` sort" comes from. Whether `d` is a constant is a statement about the **key format**, not about the algorithm, and that is where the argument has to be made carefully. ## Regime one: fixed key width Most real uses fall here. The keys are a fixed-width numeric identifier, or a code of a fixed number of characters. Then the key width `w` (in bits, or in symbols) is set by the format and does not move when the dataset grows. With digit width `b` bits, the pass count is `d = ceil(w / b)`, a constant. A 32-bit key at base 256 takes four passes whether `n` is a thousand or a billion. In this regime the linear claim is **true and worth having**: the cost is `Theta(n)` with a modest constant, against `Theta(n log n)` comparisons for a comparison sort, and the gap widens with `n`. Note the honest bookkeeping — in this regime a comparison of two keys is also `O(1)`, so the comparison sort is genuinely `n log n` and radix genuinely linear. Nothing is being hidden. There is a natural ceiling, though: a fixed width `w` admits only `2^w` distinct values, so once `n` exceeds that, keys must repeat. ## Regime two: keys must stay distinct Now suppose the interviewer pushes: "take `n` to infinity with all keys distinct." To have `n` distinct digit strings of length `d` in base `k`, you need `k^d >= n`, hence `d >= log_k(n) = log2(n) / log2(k)`. Substituting into `d(n + k)` gives a cost of at least `n * log2(n) / log2(k)`. That is `Theta(n log n)` with `log2(k)` in the denominator. The asymptotic separation from comparison sorts disappears; what remains is a constant factor of roughly `log2(k)`. This is not a defect — it is exactly the right answer to "why is radix sort fast". Each pass reads `log2(k)` bits of key per record; each comparison yields at most one bit. At base 256, one pass does what about eight comparison levels would do, and does it with a sequential scan instead of a branchy `log n`-deep search. That is a real, large, measurable win, and it is a **constant-factor** win in the distinct-keys regime. ## Two numbers that make the point | Setting | `d` | Cost shape | | --- | --- | --- | | Fixed 32-bit keys, base 256 | 4, always | `Theta(n)` | | Fixed 12-symbol codes, one symbol per pass | 12, always | `Theta(n)` | | Distinct keys, `n` growing, base 256 | at least `log2(n)/8` | `Theta(n log n / 8)` | At `n = 100` million, `log2(n)` is about 27, so the distinct-keys floor is about 4 passes — which happens to match the fixed 32-bit case, because 27 bits is what you need to enumerate 100 million values. The two regimes agree at the boundary, which is a good sanity check that the analysis is right. ## The other half of the trap There is a symmetric error on the comparison side. When keys grow with `n`, a comparison of two `w`-bit keys is no longer a unit-cost operation either — it may inspect `w/8` symbols. So the fair statement is not "radix loses its advantage"; it is "both models must count the cost of touching wide keys, and radix touches each key's digits a bounded number of times while a comparison sort may touch the same key's leading digits `log n` times." ## The `k` term is not free either `O(d(n + k))` also carries `k` per pass — a bucket structure of `k` entries that must be cleared and scanned every pass. Pushing the base up shrinks `d` but inflates that additive term, so the bound itself tells you the base cannot be increased without limit. Choosing it is a separate engineering decision. ## How to say this in an interview Do not answer "radix sort is `O(n)`" flatly, and do not swing to "radix sort is secretly `n log n`" either. Say: the cost is `O(d(n+k))`; `d` is a constant exactly when the key width is fixed by the format, which is the common real case and where the linear claim holds; if keys must stay distinct as `n` grows, `d` is at least `log_k(n)` and the bound returns to `n log n` over `log2(k)`. Then name the remaining advantage — bits extracted per pass, sequential access — because that is what actually makes it fast on real data.
- So for fixed 32-bit keys, is radix sort genuinely O(n)?Yes. The width is fixed by the format, so at base 256 it is four passes regardless of whether n is a thousand or a billion, and the cost is Theta(n) against Theta(n log n) comparisons. The only fine print is that a fixed 32-bit domain holds at most about four billion distinct values, so past that point keys necessarily repeat — which does not change the pass count at all.
- Does heavy duplication in the keys let radix sort do less work?Not for LSD. The pass count is fixed by the key width, so it makes the same d passes no matter how many keys repeat. MSD can quit early when a bucket holds a single record, but heavy duplication produces one enormous bucket rather than many singletons, so it gets no early exit either — it just recurses to the full key depth on that bucket. Duplicates help distribution-sensitive sorts, not radix.
- Where exactly does the advantage over comparison sorts come from, if it is only a constant factor?Each pass extracts log2(k) bits of ordering information per record, while a comparison yields at most one bit — so base 256 does roughly eight comparison levels of work per pass. On top of that, a pass is a sequential scan with predictable control flow, whereas a comparison sort does branchy, cache-unfriendly work log n levels deep. Both effects are constant factors, and both are large.
saying these in an interview costs you the question
- States radix sort is O(n) with no conditions attached
- Treats d as a property of the algorithm rather than the key format
- Concludes radix sort is therefore never worth using
- Ignores the additive k term when raising the base
- Assumes comparing wide keys stays unit cost as keys grow