Why does sort-then-binary-search lose to a single scan for one lookup in a large unsorted file?
answer
- Write both totals down before comparing
- Which term dominates n log n plus log n?
- One pass versus touching every row repeatedly
- Now set q scans against one sort
- Crossover lands near log n queries
basics
~20 sSorting costs O(n log n) before the O(log n) lookup, so the total is dominated by the sort and is strictly worse than one O(n) scan. Ordering only pays once its cost is amortized over enough later queries.
solid answer
~50 sFor a single lookup the honest comparison is `O(n)` for a scan against `O(n log n + log n)` for sorting then searching — the `log n` search term is noise next to the sort, so the scan wins outright and by a wide margin in constants too. Sorting ten million refund rows touches every row repeatedly and typically needs the whole set resident or spilled to disk; the scan reads each row once, stops early on a hit, and needs `O(1)` extra space. Ordering only pays when it is reused: with `q` lookups you compare `q·n` against `n log n + q·log n`, which crosses over at roughly `q ≈ log n` queries — about two dozen for ten million rows, and more once constants are counted. The rule is not "sorting is expensive", it is "sorting is an investment you must amortize".
go deeper
Be able to add the two costs out loud: ordering the data plus the lookup, versus one pass over the data. Know that the lookup's logarithmic term is dwarfed by the ordering cost.
Explain why n log n dominates n log n plus log n, and derive the repeated-query break-even rather than reciting it. Mention the streaming versus resident memory difference between a scan and a sort.
Show the judgment: identify how many queries the workload really issues and how often the data changes, and say when you would maintain order on write instead of ordering before reads.
Frame ordering as an investment with a payback period charged to one team and collected by another. Decide where in the pipeline that cost is paid, and what happens to the argument when query volume grows tenfold.
## The arithmetic, written out Take a ten-million-row refund export with no order to it, and one question: is refund `X` in the file? - **Linear scan.** Look at each row until you find it or run out. Worst case `O(n)` comparisons, expected about `n/2` on a hit, `O(1)` extra space, one sequential pass over the data. - **Sort, then binary search.** Order the file, then halve. `O(n log n)` for the ordering plus `O(log n)` for the lookup. Adding a `log n` term to an `n log n` term changes nothing: the total is `O(n log n)`, which is asymptotically **worse** than `O(n)`. The search you paid for is free next to what you paid to enable it. For `n = 10^7`, `log2 n ≈ 23`, so the sort does on the order of twenty-three times as much comparison work as a scan does — before counting that a scan is a single sequential pass with a very small constant, while a comparison sort moves data repeatedly and, at that size, often cannot hold everything at once and must spill and merge. The candidate answer this question exists to break is "just sort it first, sorting is basically free". It is not free, and it is not even cheap: it is the most expensive step in the whole plan. ## Where the break-even actually is The interesting version is repeated queries. With `q` lookups over the same unchanged data: | Strategy | Total cost | | --- | --- | | Scan every time | `q · n` | | Sort once, then binary search | `n log n + q · log n` | Set them equal: `q·n = n log n + q·log n`, so `q·(n − log n) = n log n`, giving `q = n log n / (n − log n) ≈ log n` for large `n`. **The crossover is around `log n` queries** — roughly two dozen lookups on ten million rows. That is a strikingly small number, and it is why "sort it once" is the right answer far more often than the single-query analysis suggests. Anything that answers questions repeatedly — a service, a report, a join — is on the amortized side of the line. Two honest caveats on that number. First, it ignores constants, and the sort's constant is much larger than the scan's, so the real crossover sits somewhat higher than `log n`. Second, it assumes the data does not change; every mutation either re-pays part of the ordering cost or forces you to maintain order on write instead, which is a different budget line — read cost traded for write cost. ## What the asymptotics hide The `n log n` term assumes a comparison-based sort, and `Ω(n log n)` is a genuine lower bound for comparison sorting — not something cleverness escapes for general keys. But asymptotics are only part of the decision: - **Memory.** A scan is streaming and `O(1)` auxiliary. Ordering a large file needs the data resident or an external, spilling strategy — a qualitatively different operational cost, not just a bigger constant. - **Early exit.** A scan can stop the moment it hits. A sort must finish before the first question can be answered at all, so it has no best case relative to the query. - **You already touched everything.** If you are going to order the file, you have already read every row — a superset of the scan's work. Whatever the scan would have answered, you could have answered on the way past. - **Small `n`.** At a few dozen elements, neither analysis matters much; the scan's locality usually wins outright and the code is simpler. ## How to answer it in an interview State the two totals, point out that `log n` is dominated by `n log n`, conclude the scan wins for one lookup — then immediately volunteer the break-even, because that is where the judgment lives. The strong answer sounds like: "one lookup, scan it; more than roughly `log n` lookups against unchanging data, order it once and amortize; if the data changes constantly, the question becomes whether I maintain order on write rather than whether I sort before reading." That framing shows you understand sorting as an **investment with a payback period**, not as a free prerequisite you sprinkle before every binary search.
- Roughly how many repeated lookups justify sorting the data once?Compare `q·n` for repeated scans against `n log n + q·log n` for sorting once. Solving gives `q ≈ log n`, so about two dozen lookups over ten million rows. Constants push the real crossover a bit higher, since a sort moves data far more than a single sequential pass does. The key point is that the threshold is small — anything queried repeatedly belongs on the sorted side.
- How does the analysis change if the file is appended to between queries?The sort is no longer a one-time cost, so the amortization argument weakens or collapses. You either re-order on every batch, which re-pays a share of `n log n`, or you maintain order on write and trade read cost for write cost. The comparison stops being scan-versus-sort and becomes a read/write budget question about how often the data changes relative to how often it is queried.
- Why does the memory profile matter as much as the time bound here?A scan is a single streaming pass with `O(1)` auxiliary space, so it runs on data far larger than memory. A comparison sort needs the set resident or must spill and merge externally, which is a different operational class — disk traffic, temporary space, and a step that must complete before the first answer. Two plans with similar time bounds can differ sharply in whether they run at all.
Alphabetising a thousand loose invoices to answer one question is slower than flipping through the pile; you alphabetise because you know you will be asked again all week.
saying these in an interview costs you the question
- Says sorting is cheap enough to ignore in the total
- Quotes O(log n) for the plan while omitting the sort term
- Assumes binary search is always the faster option
- Cannot state a break-even in terms of query count
- Ignores that sorting needs the data resident or spilled
- Forgets that ordering the file already touches every row