With bookings capped at 50, how do you justify shipping the O(n^2) check over the O(n log n) one?

## Start with the numbers, because they settle half the argument At n = 50: - `n^2` = 2,500 operations - `n log n` ≈ 50 × 5.6 ≈ 280 operations - the difference ≈ 2,200 operations, which at any plausible constant is well under a microsecond A function call, a log line, or a single small allocation on the same code path costs more than the entire gap. Any argument for the asymptotically better algorithm that appeals to speed is, at this size, an argument about a quantity nobody can measure. State that first — it converts the discussion from "which is faster" to "which costs less to own", which is the real question. ## The costs that are actually being traded Once runtime drops out, the remaining ledger is unglamorous and decisive: - **Correctness risk.** A short doubly nested loop is verified by reading it. A version built on an ordered structure has boundary conditions — ties, empty input, equal keys, an element removed at the exact moment it is examined — each of which is a place to be subtly wrong. Bugs found in production cost far more than 2,200 operations. - **Review and onboarding cost.** Every future reader must decide whether the clever version is correct before they may change the code near it. That toll is paid repeatedly, by people who were not in this conversation. - **Test surface.** The simple version can be exhaustively tested at this size — you can literally enumerate small inputs. The complex one needs tests aimed at its internal invariants, which is more work and easier to under-do. - **Time to ship.** Real, though the weakest of the four, and the one candidates over-weight in interviews. Against that, the fast version buys headroom you do not need and cannot currently use. ## The move that makes this a senior-plus answer: interrogate the bound The decision is not really about 50 versus the algorithms. It is about **what kind of fact 50 is**: - *An enforced invariant* — the API rejects the fifty-first booking, the schema constrains it, a validation layer caps it. Then the quadratic choice is sound and stays sound. - *A product policy* — a plan limit that a pricing decision could raise next quarter, with no code change required. Then the bound may move without anyone thinking about your algorithm. - *An observation* — "we looked and the biggest tenant has 43". This is the dangerous one, because it is not a bound at all. It is a measurement, and measurements grow. If the cap is an observation, the defect to fix is the missing enforcement, not the complexity class. Adding a validated limit, or an alert at some fraction of it, is usually cheaper than the rewrite and protects you against every future quadratic on the same data, not just this one. ## What must ship alongside the decision A deliberate choice to be asymptotically worse is only defensible if it is legible later: 1. **An enforced cap**, ideally rejecting oversized input rather than merely logging it. 2. **A written revisit threshold** — "this is quadratic; it is fine to about a few thousand and unusable near 10^5; revisit if the cap rises past 1,000." That number is the whole handover. 3. **A test that asserts the cap**, so removing the limit fails a build rather than degrading a service quietly. 4. **Monitoring on the input size**, so growth is visible before it is painful. Without these, "n is small" is a comment that ages badly. With them, it is an engineering decision with a stated expiry. ## Where the answer flips Be explicit about the conditions that would change your mind, because a judgment call with no stated boundary is not a judgment: - The cap is not enforceable, or is set by someone outside your control. - The operation runs inside another loop — a quadratic pass over 50 items, repeated per request across a million requests, is 2.5 × 10^9 operations, and the smallness of 50 is irrelevant. - The team already owns the faster structure elsewhere, so the marginal complexity is near zero. - The bound sits on a growth path with a known trajectory — "50 today, 5,000 after the migration" — in which case you are choosing to do the work twice. That last one is the genuinely hard case, and it has no universally right answer: doing it twice may still be cheaper than getting it wrong once, especially when the requirements around the fast version are still moving. ## Saying it in the room Always name the asymptotic solution first, so the interviewer knows you have it: "The general form of this is an n log n pass; at a cap of 50 I would ship the quadratic instead, because 2,500 operations is free and the simple version is a third of the code and far easier to prove right. I would enforce the cap in validation and write down that we revisit past about a thousand." That sequence — I know the fast one, here is why I am not using it, here is what protects the decision — is the answer. Reaching straight for the sophisticated structure to look strong reads as weaker judgment, not stronger.