Guarantees & Pitfalls

## What the plain claim hides "Hash lookups are O(1)" is the most repeated sentence in interview prep and the most incomplete. Big-O is a bound on a cost function, but it says nothing on its own about *which* cost function: the cost of one operation on the worst possible input, the cost averaged over some distribution, or the cost of a whole sequence divided by its length. A hash table needs all three answers, because it gives a different one to each question. ## Expected O(1): what "expected" averages over The standard analysis assumes *simple uniform hashing*: each stored key is equally likely to hash to any of the `m` buckets, independently of the others. Let `n` be the number of entries and `alpha = n/m` the load factor. Under that assumption the expected number of entries sharing a bucket with your key is `alpha`, so a chained lookup costs `Theta(1 + alpha)` expected — hash once, then walk a chain whose expected length is a constant as long as the table keeps `alpha` bounded (which is exactly what growing on a load-factor threshold buys). That is where the O(1) comes from: not from magic, but from a bounded load factor plus an assumption about how keys scatter. Note what "expected" does *not* say. It does not say your next lookup is fast — expectation is an average over the key-to-bucket distribution, and any individual lookup may probe a long chain. It also does not say collisions are absent. Collisions are expected and routine; by the birthday effect a table with only a few dozen keys in a few hundred buckets already has them. Constant time survives collisions precisely because the *number* of collisions per bucket stays small on average. ## Worst case O(n): the degenerate table If every stored key hashes to the same bucket, chaining leaves you with one list of `n` entries and lookup becomes a linear scan: O(n). Open addressing degrades the same way — with all keys clustered, probing walks a long occupied run. Nothing about the data structure prevents this; it is prevented by the hash function scattering the particular keys you store. So the worst case is real, it is O(n), and the correct thing to say in an interview is that it is *unlikely under a well-mixing hash on ordinary keys*, not that it cannot happen. The direction of the claim matters. O(n) is an upper bound on the bad case, not a prediction; a table with a decent hash essentially never exhibits it. Equally, expected O(1) is an average, not a per-operation guarantee. Candidates who collapse either direction — "so it is really O(n)" or "so it is really O(1)" — get pushed on. ## Amortized O(1): the insert that pays for everyone A table that grows when the load factor crosses a threshold must, at that moment, allocate a bigger array and re-place every live entry: `Theta(n)` work in one call. Yet insert is still described as amortized O(1), because with growth by a constant *factor* the total re-placement work across `n` inserts is a geometric series — roughly `1 + 2 + 4 + ... + n < 2n` — so `n` inserts cost `O(n)` in total. Amortized is a statement about a worst-case *sequence*, and it is a different qualifier from expected: put together, an insert is expected amortized O(1), with a single insert able to cost `Theta(n)` for the growth and, in the degenerate case, more for a long chain. ## Why interviewers keep asking The question is a proxy for whether you state assumptions. Real runtimes differ on the details underneath the same bound — Java's hash map chains entries per bucket while Python's dict uses open addressing with a perturbed probe sequence — and the asymptotic story above holds for both, which is exactly why the qualifiers, not the implementation trivia, are what the analysis rests on. A good habit for design docs and whiteboards: write the bound with its condition attached. "Lookup expected O(1) with a bounded load factor; O(n) worst case if keys cluster; insert amortized O(1) because growth is by a constant factor." That sentence is reviewable. "O(1)" is not.