With n = 100 million readings and k = 100, what does a size-k heap actually save over sorting?
answer
- Compare the two log factors first
- log2 of a hundred against log2 of a hundred million
- Ask what has to be in memory at once
- One forward pass versus the whole dataset
- The guard skips most values entirely
basics
~20 sRoughly a fourfold smaller log factor: log2(100) is about 6.6 against about 26.6 for 100 million. The real saving is elsewhere — 100 resident values instead of 100 million, in a single forward pass over data of unknown length.
solid answer
~50 sAsymptotically it is `O(n log k)` against `O(n log n)`, and with these numbers the log factor drops from about 26.6 to about 6.6 — a constant-factor win of roughly four, not a change of complexity class. The saving people actually care about is space and passes: the heap keeps `O(k)` resident, here 100 entries, while any sort needs all 100 million values available somewhere and addressable. That is what makes the heap viable on a stream of unknown length and on a machine that cannot hold the data. The early-exit guard sharpens it further: a value that does not beat the root costs one comparison and no heap work, so on randomly ordered input real heap updates are rare. What you give up is everything else — a full ranking answers any k afterwards and yields percentiles; the heap hands you 100 values and forgets the rest.
code
pseudocode · 11 lines// keep the k largest values of a one-pass stream
h = empty min-heap // holds the k best seen so far
for x in stream:
if size(h) < k:
insert(h, x) // still filling: O(log k)
else if x > peek_min(h):
extract_min(h) // evict the current bar: O(log k)
insert(h, x)
// else: x cannot beat the bar, discard it, one comparison
...
// h holds the k largest; peek_min(h) is the kth largestgo deeper
Know the two shapes: keeping only k values costs O(n log k) time and O(k) space, while ranking everything costs O(n log n) time and needs all n values available at once.
Do the arithmetic out loud — about 6.6 against about 26.6, so the log factor shrinks roughly fourfold. Name that as a constant-factor win rather than claiming a better complexity class.
Point at the win that matters in production: a single forward pass, bounded resident state, and a guard that reduces the overwhelming majority of values to one comparison and no heap work.
Frame it as feasibility rather than speed. Ranking everything requires the whole dataset to exist somewhere addressable, and that requirement, not the log factor, is usually what decides the design.
## The two costs, side by side | | size-k heap | full sort | |---|---|---| | time | O(n log k) | O(n log n) | | resident state | O(k) | O(n) | | passes over input | one, forward | needs the whole dataset | | stream of unknown length | fine | impossible | | output | the k largest, unordered | everything, ranked | ## Doing the arithmetic instead of waving at it The first thing to say out loud is the number. With n = 10^8, log2(n) is about 26.6. With k = 100, log2(k) is about 6.64. So the log factor shrinks by roughly a factor of four. That is a genuine win, but it is a **constant factor**, not a new complexity class: n log k and n log n are both n-times-a-logarithm, and no interviewer is impressed by "it's much faster asymptotically" when the ratio is four. The honest framing is: if all 100 million values already sit in memory and you have time to sort them, the heap saves you a smallish multiple. If they do not, the heap is not four times better — it is the difference between an answer and no answer. ## Where the real win lives: resident state and passes Sorting is an operation on a *collection*. It requires every value to be available at once and reachable in any order; that is what the algorithm needs to permute them. The size-k heap is an operation on a *sequence*. It consumes each value once, decides in one comparison whether that value can still matter, and never looks back. So: - **Memory.** 100 entries instead of 10^8. If each reading is 16 bytes, that is 1.6 KB against 1.6 GB. - **Length.** The heap does not need to know n. It runs on a feed that has not finished, and it has a correct answer for "everything so far" after every single element. - **Storage.** If the data does not fit, sorting means spilling to disk and paying the I/O of an external sort; the heap means nothing leaves the processor cache. That is why the honest answer to "what do you save" is *space and the requirement to have the data*, and the log factor is a footnote. ## The guard makes the average case much better than the bound The fragment's `else if x > peek_min(h)` line is doing quiet work. A value that fails the test costs exactly one comparison — no sift, no allocation, no O(log k). Only values that beat the current bar pay for a removal and an insertion. How often does that happen? For randomly ordered input, the i-th value enters the running top-k with probability min(1, k/i), so the expected number of updates over the whole pass is about k + k·ln(n/k). With n = 10^8 and k = 100 that is roughly 100 + 100·ln(10^6) ≈ 1,500 updates across 100 million values. Effectively the whole run is one comparison per value, and the O(n log k) bound is charged to fewer than two thousand of them. The worst case is the mirror image: **strictly ascending input**, where every value beats the root and every step pays the full O(log k). Note the direction — many candidates guess descending input is the bad case because "each value is a new maximum", but descending order is the *best* case: after the first k values the root already holds the kth largest overall and nothing else ever gets in. ## What you are not buying The heap answers exactly one question, the one you asked before the pass started. - The k results come out **unordered**. A heap is partially ordered, so ranking them costs another O(k log k) — trivial for k = 100, but say it rather than let the interviewer catch it. - You cannot change k afterwards. The 101st-largest value has been discarded. - You cannot compute a median, a percentile, or a histogram from what survived; those need the values you threw away. - A sort, by contrast, is a one-time investment that answers all of the above and can be re-sliced for any k later. ## The reasoning to reuse When k is a small constant, log k is essentially a constant, and the pattern behaves like a linear scan with a cheap filter. When k grows toward n the advantage evaporates: at k = n nothing is ever evicted, the heap holds everything, and you have paid O(n log n) for a structure that does not even hand you sorted output. The size-k heap earns its place precisely in the regime k << n, which is where the question is usually asked and where the memory argument, not the log factor, is what decides the design.
- Which input order is worst for this pattern, and which is best?Strictly ascending is worst: every value beats the current root, so all n values pay a removal plus an insertion and you actually hit O(n log k). Strictly descending is best — after the first k values the root is already the kth largest overall, nothing else ever passes the guard, and the whole rest of the pass is one comparison per value.
- On randomly ordered input, how many heap updates do you actually expect?About k + k·ln(n/k), because the i-th value joins the running top-k with probability min(1, k/i). For 100 million values and k = 100 that is roughly 1,500 updates — everything else is a single failed comparison. The asymptotic bound is real but almost never paid.
- Does the heap hand you the k largest in sorted order?No. A heap is only partially ordered, so you get the k values as a set with the smallest of them on top. Producing a ranked list costs an extra O(k log k) — negligible at k = 100, but it is a step candidates routinely forget to mention.
saying these in an interview costs you the question
- Treats n log k and n log n as different complexity classes
- Says the heap saves a factor of k, not log k
- Ignores that sorting needs all n values resident
- Assumes every value causes a heap update
- Forgets the k results are not produced ranked