When is a divide-and-conquer rewrite worth it over a working quadratic scan of a few thousand points?
answer
- Big-O describes growth, not milliseconds
- What is n today, and next year?
- Measure the tail before rewriting
- Who maintains the subtle merge logic?
- Write down the trigger to revisit
basics
~20 sWhen measured headroom, not asymptotics, says so. A quadratic scan over a few thousand points is a few million tight comparisons and often fits the budget; the decision turns on projected growth, tail latency today, and maintenance risk.
solid answer
~50 sBig-O describes growth, not milliseconds, so I start from measurement: what is `n` today, what does the current p99 cost, and how much headroom is left in the budget? A few thousand points is a few million comparisons in a tight loop, often single-digit milliseconds. Then I price the other side: the linearithmic version needs an initial ordering and a boundary argument that is easy to get subtly wrong, and a wrong answer here is silent rather than a crash. So the call is about growth — triple `n` and quadratic work grows ninefold against roughly 3.6x — and if headroom is smaller than that, the rewrite stops being optional. Keeping the simple version means writing down the trigger that reopens the decision; shipping the clever one means keeping the simple one as a differential-testing oracle.
go deeper
Take away that a better big-O does not automatically mean a faster program at a fixed input size, and that measuring the current code comes before replacing it.
Be ready to compare growth concretely: tripling the input multiplies quadratic work about ninefold and linearithmic work about 3.6-fold, and that ratio against measured headroom is the argument.
Show how you would validate the replacement — the simple version retained as a test oracle, adversarial inputs, side-by-side comparison on real traffic before the switch.
Own the decision and its expiry: pick a side, record the threshold on input size or tail latency that reopens it, name the owner of that signal, and weigh the silent-wrong-answer risk against the growth risk explicitly.
## Why this is a judgment call and not a lookup Asymptotic notation is an *upper bound on growth*, and it deliberately discards the constants. At a fixed, known input size those constants are the entire story. A quadratic all-pairs scan over 2,000 points is about two million comparisons of a simple arithmetic expression over contiguous data — a workload that hardware executes extremely well. The linearithmic alternative does far fewer comparisons but pays for an initial ordering, recursion, band construction and bookkeeping, all with worse memory access patterns. There is a crossover, and it is frequently much further out than people assume. So the decision is not "which has the better bound" but "which bound do I need, at the sizes I will actually see, given what each version costs me to own". ## The four inputs to the decision **1. What `n` is, and what it will be.** Today's distribution matters less than its tail and its trend. The worst request you serve, not the median, decides whether you fit the budget. And growth is asymmetric between the two designs: multiply `n` by 3 and quadratic work goes up 9x while linearithmic work goes up about 3.6x. Multiply by 10 and it is 100x against roughly 13x. If your input size is a business quantity that grows with adoption, the quadratic version has a cliff with your name on it. **2. Measured headroom.** Not an estimate — a measurement, at the tail, on production-shaped inputs. If the current implementation costs 4 ms of a 200 ms budget, you can absorb an order of magnitude of growth and the rewrite is premature. If it costs 90 ms, you are already one busy quarter from an incident. **3. The cost of being wrong.** The recursive version's failure mode is not a crash — it is a *silently wrong answer* from a mishandled boundary case: an odd count, duplicate coordinates, all points collinear, everything crammed into one side of the split. That class of bug survives casual testing and shows up as an inexplicable business result months later. Price that risk honestly, including who on the team can review the merge argument and who will debug it at 2 a.m. **4. Whether a cheaper fix exists.** Between "quadratic loop" and "full recursive rewrite" there is usually a middle: pruning that skips pairs once one coordinate difference already exceeds the best distance so far, capping candidate sets, or bucketing points so only nearby buckets are compared. These often deliver most of the headroom for a fraction of the risk, and they are the option a strong candidate raises unprompted. ## How to decide, out loud A defensible answer sounds like this. Measure the tail cost at today's sizes and project it at the sizes forecast for the next planning horizon. If the projection stays inside the budget with real headroom, keep the simple version — *and record the decision with a trigger*, such as "revisit when per-request points exceed 5,000 or when p99 for this stage exceeds 40 ms". A trigger converts a one-off argument into a monitored condition, which is what stops the team relitigating it every quarter and also stops it being forgotten until it breaks. If the projection does not fit, do the rewrite, but de-risk it: keep the brute-force version as an executable oracle, run both over randomized and deliberately adversarial inputs (duplicates, collinear runs, tight clusters, all points on one side of the median) and assert identical results, then run them side by side on real traffic before switching. The simple implementation's real long-term value is often as a test oracle rather than as the shipped path. ## The failure modes on both sides The junior failure is rewriting for the better bound with no measurement at all — replacing understood code with subtle code to fix a problem nobody demonstrated. The senior failure is the mirror image: refusing the rewrite forever because "it's fast enough now", with no threshold written down and no owner watching the number, until the growth arrives and the fix has to happen under incident pressure by whoever is on call. A principal-level answer names both, picks one, and attaches the condition under which the choice flips.
- Your input size triples over a year. How does that change the calculus?Quadratic work grows about ninefold while the linearithmic version grows roughly 3.6x. If measured headroom is less than nine times the current cost, the quadratic version leaves the budget within the year. That is the moment to set the trigger on both `n` and measured p99 rather than waiting for the incident.
- How do you de-risk shipping the more complex algorithm?Keep the simple version as an oracle. Run both over randomized and adversarial inputs — duplicate coordinates, collinear runs, tight clusters, everything on one side of the split — and assert identical answers. Then run them side by side on real traffic and compare before switching the served path.
- What if a cheaper optimisation gets you most of the headroom?Prefer it. Pruning that abandons a pair as soon as one coordinate difference exceeds the current best, or restricting comparisons to nearby buckets, often buys an order of magnitude while keeping the code reviewable. Asymptotically it is still quadratic in the worst case, which is exactly why the trigger stays written down.
saying these in an interview costs you the question
- Rewrites for the better asymptotic bound without measuring anything
- Assumes the lower big-O is always faster at real input sizes
- Ignores who will maintain and debug the subtler merge logic
- Treats the crossover point as an irrelevant detail
- Ships the clever version with no differential testing against the simple one