When does a linear scan of 64 contiguous records beat a balanced search tree?
answer
- big-O says nothing about small n
- count the real probes at sixty-four
- six dependent loads versus a straight loop
- who pays to build and maintain the structure
- the crossover is measured, not derived
basics
~20 sAt sixty-four elements the asymptotics barely apply: a scan of fixed-size contiguous records is a tight, predictable loop over cheap comparisons, while a tree pays pointer chasing, per-node overhead, and build and maintenance cost that so few elements never repay.
solid answer
~50 sBig-O discards exactly the constants that decide this case. At `n = 64`, a balanced tree needs about six probes versus sixty-four sequential tests — but each tree probe is a *dependent* load into a separately allocated node, so the hardware cannot run ahead, while the scan streams through adjacent memory with a comparison the branch predictor gets right almost every time. On top of that the tree has costs the scan does not have at all: constructing it, keeping it in sync with every mutation, and the per-node bookkeeping. The argument has real limits and you should name them: it depends on the comparison being cheap and the records being compact and contiguous. Make an expensive comparator, or grow the collection by two orders of magnitude, and the tree wins decisively. The senior move is not "linear is fine" — it is "here is the measurement, here is the size at which I would switch, and here is the alarm that tells me we crossed it".
go deeper
Know that big-O compares growth as inputs get large and says nothing about which is faster at a few dozen elements. Constant factors decide small collections.
Explain why six tree probes can lose to sixty-four sequential tests: dependent loads into scattered nodes versus a predictable streaming loop, plus the build and per-node overhead the scan never pays.
Demonstrate the whole-workload comparison and a measured crossover, and name the conditions that invert it — expensive comparisons or growth. Say how you would guard the size assumption in production.
Own the policy: when a team may keep the simple scan, what evidence justifies the more complex structure, and how the size assumption is enforced so today's correct call does not become tomorrow's silent latency regression.
## The claim being challenged "O(log n) always beats O(n)" is true as a statement about growth and false as a statement about a specific program at a specific size. Asymptotic notation describes what happens *as n grows without bound*; it deliberately discards constant factors and lower-order terms, because those are properties of the machine and the data rather than of the algorithm's shape. At sixty-four elements you are living entirely inside the part that was discarded. ## Counting what actually happens at n = 64 A balanced search tree over 64 keys has height about six, so a lookup is roughly six comparisons. A linear scan is up to 64. Six versus sixty-four looks decisive — until you ask what each of those operations costs. The scan's per-element work is: advance a position by a fixed stride, compare, branch. The next address is known before the current comparison finishes, so memory access is fully predictable and the loop's exit branch is taken the same way on almost every iteration. That is close to the cheapest thing a processor does. The tree's six probes are **dependent loads**: the address of the second node cannot be computed until the first node's contents arrive. Nothing can be prefetched or overlapped, and each node typically lives in separately allocated memory that may be nowhere near its parent. Six serialized, potentially cache-missing loads plus six comparisons plus the per-node overhead can lose to sixty-four streamed, predictable ones. This is why the crossover between a scan and a "better" structure routinely sits in the dozens or low hundreds rather than at n = 2. ## The costs that only one side pays Comparing lookup costs alone is the most common analytical error here. The tree also charges you for: - **Construction.** Building it is O(n log n) work you must repay out of lookup savings. If the collection is scanned a handful of times between rebuilds, it never breaks even. - **Maintenance.** Every insert or delete rebalances. If the data mutates as often as it is queried, the write cost joins the ledger and can dominate. - **Space and indirection.** Per-node keys, child references and balance metadata multiply the memory footprint of what was a compact buffer, which in turn worsens the locality that made the probes expensive in the first place. - **Code you must maintain.** A scan is three lines any reviewer can verify. A hand-rolled balanced structure is a thing your team owns forever. The honest comparison is **total workload cost**: builds plus updates plus lookups, at your real sizes and your real read/write mix. ## Where the argument breaks — say this before the interviewer does The small-n defence rests on two assumptions, and naming their failure is what makes the answer credible rather than contrarian. **If comparisons are expensive, the count wins again.** The entire argument is that sixty-four cheap tests beat six expensive probes. Make the comparison itself costly — comparing long variable-length keys, normalizing text, or anything involving indirection per element — and the arithmetic inverts immediately: six comparisons beat sixty-four. **If n grows, it grows against you linearly.** Sixty-four is fine, six hundred is a judgement call, sixty thousand is not defensible. And collections have a habit of growing quietly. A scan that was correct at design time becomes a p99 problem two years later without a single line of it changing. ## How to defend it professionally A skeptic who demands "something logarithmic" is not wrong to ask; they are asking for evidence. Give them: 1. **A measurement,** not a notation argument. Benchmark both at your record size, your hit rate and your miss rate, including the misses — those are full scans. 2. **A stated crossover.** "Below roughly a few hundred fixed-size records with a cheap key comparison, the scan wins; above that I would switch." A number you can be held to beats a preference. 3. **An enforcement mechanism.** Assert or alarm on the collection's size, so the assumption behind the scan is *checked in production* rather than believed. The failure mode of small-n reasoning is not being wrong today; it is being right today and silently wrong later. 4. **A note on the simpler code.** Where costs are close, the scan wins on reviewability and on having no invariant to break. ## The takeaway Asymptotic superiority is a promise about the limit, not about your program. Constants decide small n — which is exactly why mainstream sorting implementations switch to a quadratic insertion sort on short runs. The same reasoning applies to search: the correct answer is a measured crossover with a guardrail, not a preference for whichever notation looks smaller.
- How would you know when you have crossed the point where the scan stops being fine?Do not rely on remembering. Bound the assumption in code: assert or alarm on the collection's size, and attach the threshold to the benchmark that produced it. Re-measure when the record shape, comparison cost or query mix changes. The risk with small-n reasoning is never that it is wrong today, it is that it stays in place after the data grows.
- Does the same reasoning hold if each element comparison is expensive?No, and this is the cleanest way to invert the argument. The defence assumes a cheap test over compact data, so that sixty-four of them beat six pointer-chasing probes. With a costly comparator — long variable-length keys, normalization, indirection per element — comparison count dominates and six probes beat sixty-four comfortably.
- What changes if the collection is mutated on nearly every request?Mutation cost joins the ledger. A structure that must rebalance or rebuild per write can lose to a plain scan well beyond the read-only crossover, because you pay the maintenance on every request and collect the lookup saving only once. Compare total workload cost — builds plus writes plus reads — not lookup cost alone.
A six-step shortcut across town still loses to walking sixty-four paces when the destination is on the same block — and the shortcut needs building first.
saying these in an interview costs you the question
- Claims logarithmic always beats linear regardless of n
- Ignores construction and rebalancing cost entirely
- Compares lookup cost only, never the whole workload
- Argues from notation instead of measuring
- States a crossover with no guardrail on collection size