After stating an O(n^2) baseline, how do you answer the follow-up 'what gap are you trying to close'?

## What the question is really asking When an interviewer hears your baseline and asks "what gap are you trying to close?", they are not asking you to produce the optimized algorithm. They are testing whether you can reason about *how much room there is* before you go looking for it. The gap is the distance between a stated baseline and a defensible target, and a good answer names both ends plus a reason the target is plausible. Take a leaderboard: rank players by score, and the baseline compares every player's score record against every other, O(n^2) time. ## Where the floor comes from There are two grounded arguments a candidate can make out loud, and they are both cheap. **The input-reading bound.** Any correct answer must at minimum look at every record — if you skip one, an adversary puts the top score there. So Ω(n) is a hard floor on time for this problem. That single sentence kills the most common bad answer, "I will get it to O(log n)", which promises to rank players without reading all their scores. **The output-shape bound.** If the required output is a full ordering of all n players, and the only thing you may do with two scores is compare them, then you are sorting, and comparison sorting has an Ω(n log n) lower bound. So the realistic floor is n log n for a full ranking, and the gap from the baseline is n^2 down to n log n — a factor of about n / log n, which at a million records is a five-order-of-magnitude difference rather than a tidy-up. Both bounds move with the *requirement*, which is why stating them makes you sound like you understand the problem rather than the algorithm. If the requirement is only the top few players rather than a full ranking, the output no longer has n items, the sorting argument no longer applies, and the floor drops back toward linear. If scores are small bounded integers rather than opaque values you can only compare, the comparison lower bound does not bind either — counting-style approaches escape Ω(n log n) precisely because they never compare two scores. Saying "n log n *if I rank by comparison*" is the precise version; saying "n log n, always" overstates a real theorem. ## The third part: does the gap matter? This is the half that separates a candidate who recites bounds from one who has shipped something. A gap is only worth closing if the input reaches the size where it hurts. Spell out the arithmetic aloud. Two hundred players, all-pairs comparison: about twenty thousand comparisons, microseconds, refreshed hourly. Closing that gap buys nothing and costs you a more complex implementation to maintain. Five million score events per minute: the quadratic pass is on the order of 10^13 comparisons and simply does not finish. Same asymptotic gap, opposite decisions. So the strong answer ends with a question back: "How many players, and how often does the ranking refresh?" Interviewers usually have those numbers ready, and asking shows you know that asymptotics alone do not decide anything. If they say the input is small, the correct engineering answer may genuinely be "then the baseline is my solution" — though in an interview you should still be ready to show the improvement if asked, because they may be probing the technique regardless of the constraint. ## Common failure modes **Naming a target with no justification.** "I think we can do it in O(n)" invites an immediate "how?" and if you have nothing, you have spent credibility. Better: "the floor is linear because we must read everything; whether linear is reachable depends on whether a full ordering is required." **Claiming a target below the input-reading bound.** Sub-linear answers require not reading the whole input, which for a full ranking is impossible. This is the single most detectable error in the answer. **Assuming every gap must be closed.** Interviewers do ask questions where the honest answer is that the baseline is adequate, and they are watching to see whether you notice. **Confusing the gap with the technique.** The gap is a pair of numbers and a reason. Which structure or precomputation actually closes it is a separate step, and answering the gap question by jumping straight into an implementation sketch skips the part being assessed. ## The shape of a complete answer One sentence naming the floor and why it holds. One sentence naming the gap as a ratio, so the size of the prize is explicit. One sentence tying it to the real input bounds, ideally ending in a question about them. Thirty seconds, and you have shown you can size an optimization before attempting it — which is exactly the skill that stops engineers from spending a week making something asymptotically elegant and operationally identical.