Would you replace an O(n^2) step with an O(n log n) one when a contract caps input at 5,000 records?

## Why this is a judgment call and not an arithmetic one Asymptotic classes describe behaviour as input grows. When the input is *bounded*, that entire apparatus stops making the decision for you: at a fixed `n`, both implementations have a fixed cost, and the only question is whether each fits the budget. Answering "the better class, obviously" is the failure mode this question aims at, because it applies a tool outside the range where it says anything. Price both sides first. With `n = 5,000`: | implementation | element operations | rough wall clock at 10^9 ops/s | |---|---|---| | quadratic | 2.5x10^7 | tens of milliseconds | | linearithmic | ~6x10^4 | tens of microseconds | A thousandfold ratio that both sit inside a per-batch budget of, say, 500 ms. On performance alone at the stated cap, there is no case. ## The four things that actually decide it **1. How firm is the cap, and who owns it?** A limit enforced in your own code is a fact. A limit written in a contract with another team is a promise, and promises get renegotiated: an upstream that switches to hourly batching multiplies `n` by 60 without anyone thinking of you. Quantify the exposure rather than arguing about likelihood — at 10x the cap the quadratic step costs 100x, roughly two to three seconds; at 100x it costs 10,000x, about four minutes. Where those numbers land relative to your timeout is the real risk statement. **2. What is the failure mode when the cap breaks?** There is a large difference between "the nightly batch takes twelve minutes instead of one" and "the synchronous request times out, the client retries, and the retries multiply the load on a step that is already quadratic". The first degrades; the second amplifies. Quadratic work behind a retrying caller is a well-known way to turn a modest input surprise into an outage, and that alone can justify the rewrite regardless of today's numbers. **3. What does the complexity cost the team?** If the better-class version is a well-understood standard technique, the maintenance delta is near zero and the choice is easy. If it is a hand-rolled structure with subtle invariants that one person understands, you are trading a bounded performance risk for an unbounded correctness-and-staffing risk. Simplicity has real value and it is legitimate to spend the performance headroom to buy it. **4. What does the cheap option buy?** The choice is rarely binary. A size assertion that rejects or alerts above the assumed bound converts a silent quadratic blow-up into a loud, diagnosable error, and costs an hour. Chunking the input so each chunk stays under the cap preserves the simple code and bounds the cost. Caching or pre-filtering can cut the effective `n` by an order of magnitude, which for quadratic work is a hundredfold saving. Any of these can be the right answer, and they leave the rewrite available later. ## How to frame the decision so it survives you The deliverable of a principal-level answer is not the choice; it is the record that makes the choice reviewable. That means writing down: the assumed bound and where it comes from, the measured cost at that bound and at 10x it, the budget it must fit, the guard that fires when the assumption is violated, and the trigger that reopens the decision. "We keep the quadratic implementation while batches stay under 10,000; the job asserts batch size and pages above 8,000; revisit when the upstream contract changes" is a decision another engineer can audit in a year. "We chose `O(n log n)` because it is better" is not. ## The symmetric mistake There is an over-correction worth naming: concluding that growth classes are irrelevant whenever inputs are small. They are not — they tell you exactly how bad the surprise is when the bound moves, and they are what makes the 10x and 100x rows of the risk table computable at all. The class is the sensitivity analysis. It stops being the *decision* only because the input is pinned; the moment the pin comes out, it is the only thing that matters. A leader keeps both facts in play: the class predicts the shape of the failure, the measurement decides whether it is worth pre-empting today.