When do you reject a specialized structure and keep the linear scan over a small collection?

## The decision is not about the asymptote A proposal lands: replace the linear scan over a request's pricing rules with an indexed structure keyed for lookup. The scan is O(n) and the index is O(1) expected, so on paper the change is free improvement. The lead's job is to notice that the paper argument has left out three things the team will actually live with — the size of n, the constants, and the invariant. ## Asymptotics describe growth, not runtime Big-O is an upper bound on how cost *grows*. It says nothing about the cost at a specific size, and at small n the constants dominate completely. Scanning forty entries laid out contiguously is a handful of cache lines walked linearly, which hardware prefetches almost perfectly; the indexed alternative computes a hash, dereferences into a bucket that lives somewhere unrelated in memory, and may chase a pointer or two. It is entirely normal for the "O(1)" version to lose to the "O(n)" version at these sizes, and a lead who cannot say that out loud will approve changes that make things slower while looking faster in review. The same logic is why mainstream sorting implementations switch to insertion sort below a small threshold: asymptotic superiority promises nothing at small n. This is not an argument against good structures — it is an argument for knowing which regime you are in. ## The real cost is the invariant, not the memory When engineers price a second structure they usually price its bytes. The bytes are almost never the problem. The problem is that the index and the primary collection must agree, and agreement is not a property of the structure — it is a property of every code path that mutates the data, now and in perpetuity. Someone adds a bulk-import path next quarter, writes to the collection, does not know the index exists, and the system now returns stale answers that no test covers because the two sources of truth were never asserted equal. That failure mode has three properties that make it expensive: it is a correctness bug rather than a latency bug, it is silent, and it surfaces far from its cause. Compared with it, "this lookup is O(n) over forty items" is a benign, visible, measurable condition. Given the choice between one structure with an acceptable log n and two structures that must be kept consistent, prefer the single structure unless the faster path is measurably on the critical path. ## What bounds n The decisive question is *why* the collection is small. There are two very different answers: - **Bounded by rule.** A tenant may configure at most fifty pricing rules; the API rejects the fifty-first. This is a real bound, enforced somewhere you can point at, and a design may depend on it. - **Bounded by history.** Nobody has yet created more than a few dozen. This is not a bound; it is a coincidence with a deadline. The largest customer signed next year is the counterexample. If the bound is by rule, write it down where it is enforced *and* where it is relied upon. If the bound is by history, either introduce a rule or plan for the structure — deciding to depend on a coincidence is the choice that produces the 3 a.m. page. ## Encode the assumption so it fails loudly Keeping the scan is a legitimate engineering decision, but it should not be an undocumented one. The cheap mechanisms are: a test that constructs the collection at its stated ceiling and asserts the operation stays within budget; an assertion or metric on collection size in production, alerting well below the point where the scan hurts; and a comment at the scan naming the bound and the enforcement point. The goal is that the day the assumption stops holding is a failing build or an early alert rather than a latency investigation months later. ## What would change the decision Approve the structure when: a profile attributes real time to the scan under realistic load; n is unbounded or growing, or a tenfold increase is a plausible near-term event; the access pattern needs an operation a scan cannot provide at any size, such as ordered range queries or predecessor lookups; or the scan sits inside another loop, making the true cost quadratic rather than linear. That last case is the one people miss — an O(n) scan is cheap alone and ruinous nested. And when you do approve it, prefer the version with the fewest invariants: one structure that supports every required operation, even at log n, over two structures whose consistency is somebody's responsibility to remember. ## How to say it in a review "I am not against the index. I am against buying it before we know the scan costs us anything, and I want the ceiling on rule count encoded in a test either way. If a profile shows this on the critical path, or the rule cap goes away, we take the structure — and if we do, it goes in as one structure, not as a second copy of the data we have to keep in sync." That is a decision the team can act on, with the conditions for revisiting it stated up front.