Why is insertion into a growth-doubling hash table amortized O(1) when one insert rehashes everything?

## The claim, stated precisely Insertion into a hash table that grows by a constant factor is **amortized O(1)**: any sequence of n insertions costs O(n) total, so the cost per insertion averaged over the sequence is bounded by a constant. Two words in that sentence do the heavy lifting — *sequence* and *total*. ## Why the total stays linear Suppose the table starts with 16 buckets and doubles whenever the entry count would exceed 0.75 of capacity. Building up to one million distinct keys, it resizes at capacities 16, 32, 64, … , 1,048,576 — seventeen resizes. The number of entries moved at each resize is the entry count at that moment, roughly 0.75 times the capacity being outgrown. Summing: 0.75 x (16 + 32 + … + 1,048,576) ≈ 0.75 x 2,097,136 ≈ **1.57 million entry moves** for one million insertions. The series is geometric, so it sums to a small constant multiple of its largest term — the final resize alone accounts for half the work, and everything before it accounts for the other half combined. Add 1.57 million moves to 1 million O(1) placements and the whole build is Θ(n). Divide by n and you have your constant. The constant factor of growth is load-bearing. If the table instead grew by a **fixed** number of buckets, it would resize Θ(n) times while each resize moved Θ(n) entries, and the build would degrade to Θ(n²) — the same million keys would cost on the order of a trillion moves. Growth *rate*, not growth *amount*, is what makes the series converge. ## Amortized is not average-case This is the single most common misstatement in the whole subject. - **Amortized** is a worst-case statement about a sequence. No probability is involved. Whatever adversarial order you choose, n inserts cost O(n) in re-bucketing work; the bound holds every time you run it. - **Average-case** assumes a probability distribution over inputs and reports an expectation. Change the distribution and the number changes. They happen to coexist here, which is why the confusion survives. Hash-table insertion has *two independent* reasons not to be flatly O(1): 1. **Resizing**, which is amortized away by doubling — a deterministic, distribution-free argument. 2. **Collisions**, which are handled by the *expected* O(1) argument and depend on the hash spreading the actual key set well. Against an adversary who chooses keys that collide, a bucket degenerates into a linear scan and a single lookup or insert becomes O(n) — no amount of resizing fixes that, which is why serious implementations randomise their hashing or use collision-resistant treeing. A candidate who says "insert is O(1) amortized" and stops has answered only half. The honest phrasing is "O(1) expected and amortized; Θ(n) for the insert that triggers a resize, and Θ(n) per operation under adversarial collisions." ## What the bound does not promise Amortized O(1) says nothing about the distribution of cost *within* the sequence, and the distribution here is brutally lopsided. In the million-key example, one insert — the one that crossed 786,432 entries — moved 786,432 entries before it returned. Roughly 999,983 of the inserts touched a single bucket; seventeen of them did essentially all the work. That matters for three real situations: - **Per-operation latency budgets.** A p99 or p999 SLO is a statement about individual operations. The amortized bound is silent about the tail, and the tail is precisely where the resizes live. - **Holding a lock.** If the table is guarded, the resizing thread holds the lock for the whole transfer, so the pause is charged to every waiting caller, not just the unlucky writer. - **Memory spikes.** During the transfer both arrays are live. The amortized *time* bound says nothing about that transient allocation peak, which can be what actually breaks a memory-constrained process. ## How to answer it out loud Run the numbers, then state the limit. "Each resize moves the entries present; doubling makes those move counts a geometric series summing to under twice the final size, so total work over n inserts is linear and per-insert amortized cost is constant. What that does *not* say is that any given insert is constant — the one that crosses the threshold moves every entry in the table, and if I have a tail-latency budget I have to plan for that separately." The second sentence is the one that distinguishes a middle candidate from a junior reciting a phrase.