Insert into a growing hash table is amortized O(1) — what does that promise, and what does it not?
answer
- a promise about a sequence
- what does doubling buy you
- one plus two plus four plus ...
- amortized is not average-case
- one insert may re-place everything
basics
~20 sAmortized O(1) promises any sequence of n inserts costs O(n) in total, so the per-insert average is constant. It does not promise a single insert is cheap: the one crossing the growth threshold re-places every entry in linear time.
solid answer
~50 sIt is a promise about a **sequence**, not about one call. Growing by a constant factor means the re-placement work across `n` inserts forms a geometric series — roughly `1 + 2 + 4 + ... + n < 2n` — so `n` inserts cost `O(n)` in total and the average per insert is constant. What it does not promise is any individual insert: the call that crosses the threshold does `Theta(n)` work re-placing every live entry, so a per-operation deadline sees that cost in full. It is also **not** average-case. Amortized bounds the worst-case sequence with no probability involved at all; average-case assumes a distribution over inputs; expected averages over how keys scatter into buckets. A hash insert carries two of these at once — expected amortized O(1) — and mixing up the words is what interviewers are listening for.
code
pseudocode · 10 linesinsert(T, key, value):
if (T.count + 1) > T.capacity * MAX_LOAD:
bigger = allocate(2 * T.capacity) // constant-factor growth
for i in 0..T.capacity-1:
if occupied(T.slot[i]):
place(bigger, T.slot[i]) // Theta(n) re-placement
T.slot = bigger
T.capacity = 2 * T.capacity
place(T, key, value) // expected O(1)
T.count = T.count + 1go deeper
Know that inserts are cheap on average but that one occasional insert has to rebuild the table, and that the word amortized is what covers this. Do not let it slip out as plain O(1).
Derive the bound out loud: doubling makes the re-placement costs a geometric series that sums to linear across n inserts. Then say plainly what it does not promise about any single call.
Separate the three qualifiers cleanly and know the two ways the bound is lost — constant-increment growth and shrinking at the same threshold you grow at — since both are real bugs in hand-rolled containers.
Own the distinction between a throughput guarantee and a latency guarantee. A structure that is amortized constant can still be the wrong choice where a single operation carries a deadline, and that argument should be made before the structure is chosen, not after.
## Three words that are not synonyms **Amortized** is a bound on the total cost of a worst-case *sequence* of operations, divided by the number of operations. No randomness, no distribution over inputs: an adversary picks the whole sequence, and you still guarantee the total. **Average-case** is a bound obtained by assuming a probability distribution over *inputs* and averaging the cost over it; change the distribution and the bound changes. **Expected** is the average over some internal randomness or modelling assumption — for hash tables, over how keys scatter into buckets. Candidates who say "amortized just means average" have flattened three different guarantees into one, and the interviewer usually follows up immediately to see whether they can separate them again. ## Where the amortized insert bound comes from A table that grows when the entry count crosses a load-factor threshold must, at that instant, allocate a larger slot array and re-place every live entry into it — each entry's index depends on the capacity, so the old positions are meaningless. That call does `Theta(n)` work. Now count the total across `n` inserts. With growth by doubling, re-placement happens at capacities roughly `1, 2, 4, 8, ..., n`, and the work is proportional to the size at the time. Summing the geometric series gives `1 + 2 + 4 + ... + n < 2n`, so the *total* re-placement work over `n` inserts is `Theta(n)` — linear overall, constant per insert on average. Add the constant expected work of placing each key and you get amortized O(1) per insert. Two standard framings make this rigorous. The **aggregate** method is the sum above. The **accounting** method charges each cheap insert a constant number of extra tokens; by the time growth fires, the inserts since the previous growth have banked exactly enough tokens to pay for re-placing everything. Either way the conclusion is the same, and neither claims anything about a single call. ## The two ways the bound is destroyed **Growth by a constant increment instead of a constant factor.** Suppose the table grows by a fixed 16 slots each time it fills. Then re-placement happens about `n/16` times, at average size `n/2`, for a total of `Theta(n^2)` — amortized `Theta(n)` per insert. The bound comes from *multiplicative* growth, not from resizing being rare. **Shrinking at the same threshold you grow at.** If the table doubles at some occupancy and halves the moment it drops back below it, an adversary alternating an insert and a delete at that boundary forces a full re-placement on every single operation: `Theta(n)` amortized. The standard repair is hysteresis — grow at one threshold, shrink at a distinctly lower one, so a resize is always followed by many operations before the opposite resize can fire. ## Reading the fragment In the pseudocode above, everything outside the `if` is constant expected work: compute an index, place one entry, bump a counter. Everything inside the `if` is linear and fires on a vanishing fraction of calls. The amortized claim is precisely the statement that the second column, summed, is linear in the number of calls in the first column. It is not the statement that the second column is cheap, and it is not the statement that it is rare enough to ignore when a single call has a deadline. ## Saying it correctly The precise sentence for an insert into a growing hash table is: *expected amortized O(1)* — expected because placement assumes keys scatter across buckets, amortized because growth spreads a linear re-placement over the inserts that preceded it — with a worst-case single insert of `Theta(n)` for the growth, and `O(n)` for placement itself if the keys have degenerated into one bucket. Two qualifiers, two different reasons, and a worst case that is genuinely linear. That is the level of precision the question is testing for; "insert is O(1)" is the answer it is designed to catch.
- Spell out the difference between amortized, average-case and expected.Amortized bounds the total cost of a worst-case sequence divided by its length — no probability at all. Average-case assumes a distribution over inputs and averages the per-operation cost over it. Expected averages over internal randomness or a modelling assumption, which for hash tables is how keys scatter into buckets. A hash insert carries two of them simultaneously: it is expected amortized O(1).
- What happens to the bound if the table grows by a fixed number of slots instead of doubling?It collapses. Growing by a constant increment c means re-placement fires about n/c times at an average size of n/2, for Theta(n^2 / c) total work across n inserts — amortized Theta(n) each. The constant-factor growth is what makes the re-placement costs a geometric series that sums to linear; rarity alone is not enough.
- Does shrinking the table on delete break the amortized bound?It does if you shrink at the same occupancy where you grow. An alternating insert/delete sequence then straddles the boundary and forces a full re-placement on every operation. The fix is hysteresis: grow at one threshold and shrink at a distinctly lower one, so that after any resize many operations must occur before the opposite resize can fire.
saying these in an interview costs you the question
- Amortized just means average-case over random inputs
- Amortized O(1) means every insert is constant time
- Amortized O(1) means the table never copies everything
- Growing by a fixed number of slots gives the same bound
- Amortized and expected are interchangeable qualifiers