What lookup guarantee should a hash-based telemetry dedupe service promise in its SLA?

### Two different mistakes hide inside "lookups are O(1)" A dedupe service keeps a hash-based index of identifiers it has already seen and asks it once per incoming telemetry event. Someone drafts the service contract and writes "lookups are O(1)". That sentence fails twice. **It is the wrong case.** A hash lookup is *expected* constant time under a key set that spreads well across the table, and its worst case for a single lookup is `O(n)` in the number of stored keys, because a degenerate distribution makes a lookup examine many stored keys before answering. "O(1), full stop" states a guarantee the structure does not provide; the honest pair is "expected O(1), worst case O(n)". Direction matters here: the expected bound is an average over key placements, not a cap on any individual lookup. **It is the wrong kind of number.** Asymptotic classes deliberately discard constants and lower-order terms, and an SLA is made of exactly those discarded things — milliseconds, at a percentile, at a load. Two implementations can both be expected O(1) and differ by an order of magnitude in wall-clock time. You cannot sign a growth rate. ### What the contract should actually say A signable guarantee has five parts: 1. **A measured percentile with units.** For example: p99 lookup under 200 microseconds, p999 under 2 milliseconds. Percentiles, not the mean — an expected-case bound is a statement about the mean, and the mean is precisely where a rare slow lookup hides. In a path called once per event, "rare" still means thousands of events per hour. 2. **The load and population it holds at.** "At up to 40,000 events per second against a retained window of 50 million identifiers." A latency number without a stated size is not a claim, because the whole point of complexity analysis is that cost is a function of n. 3. **The assumption it rests on.** "Assuming identifiers are well distributed across the index." Writing the assumption down is what converts an expected-case bound from a hand-wave into something reviewable — and it tells the next engineer what to check when the number stops holding. 4. **Monitoring that watches the assumption, not just the symptom.** Sample how many stored keys a lookup has to examine and alert when that distribution's tail grows. Latency alerts tell you the assumption already broke; a distribution metric tells you it is breaking. 5. **Defined behaviour when it breaks.** Shed, spill to a secondary path, or degrade dedupe accuracy on purpose — but say which, in advance. A guarantee with no stated failure mode is a guarantee that fails silently. ### When to buy a worst-case bound instead Sometimes the right answer is not to promise the expected case at all. If the dedupe lookup sits on a hard deadline — a request path with a fixed budget, or a system where a tail spike causes queue collapse upstream — you may prefer a structure whose **worst case** is bounded, accepting a slower typical operation in exchange for a number that holds under any input. That is a real engineering trade, and the shape of the argument is always the same: *how much typical-case throughput am I willing to pay for a bound I can commit to?* On a batch pipeline with slack, expected-case wins easily. On a synchronous critical path with a tight budget and a hostile tail, a predictable bound can be worth a large constant factor. ### Why this comes up as a senior question Because it is where complexity vocabulary meets an actual promise, and the vocabulary errors become expensive. The candidate who says "hash lookups are O(1)" is not wrong in a classroom; they are wrong in a document that another team will plan against. The senior move is to translate: the structure gives me an expected constant-time lookup with a linear worst case; my customers experience a latency distribution; the contract is a percentile at a stated load with the assumption named, the drift monitored, and the degradation defined. ### Distilled Asymptotics describe the shape of the curve. An SLA is a specific point on that curve, with units, at a stated size, under a stated assumption. Quote "expected O(1), worst case O(n)" when someone asks about the data structure; quote a percentile in milliseconds when someone asks what you will promise — and never let the first sentence be mistaken for the second.