Adding to a dynamic array is O(1) amortized even though some inserts trigger an O(n) resize. Explain why, and how you'd justify that bound to a teammate who only sees the occasional slow append.

technical-conceptual · Mid level · software-engineering

What the interviewer is really asking

Assesses whether the candidate understands amortized analysis as a real reasoning tool — that a cost spread over a sequence differs from worst-case-per-op — and can derive the doubling argument rather than just assert O(1).

What to say

• Distinguish amortized from average-case and from worst-case-per-op: amortized is the cost of a single operation averaged over a worst-case sequence of operations, with no probability assumption. One append can be O(n) when it resizes, but a long run of appends averages to O(1) each.
• Give the doubling argument concretely: when the array fills, you allocate a new buffer of double the capacity and copy the n existing elements (the O(n) step). Because capacity doubles, the next resize is twice as far away, so the total copy work across n inserts is n + n/2 + n/4 + ... < 2n — linear total, hence O(1) per insert amortized.
• Name the trade-off in the growth factor: doubling wastes up to ~50% memory right after a resize; a smaller factor (1.5x) wastes less but resizes more often and can prevent reusing freed blocks. Mention that aggregate, accounting (charge each insert 3 units to pre-pay its future copy), and potential methods all reach the same bound.

What to avoid

• Claim every append is O(1) and stop there, ignoring that the resize itself is genuinely O(n) — that misses the whole point of the question.
• Confuse amortized O(1) with average-case O(1): amortized makes no assumption about input distribution, it's a guarantee over any sequence, whereas average-case depends on a probability model.
• Say growing by a fixed increment (add 100 slots each time) is equally fine — that makes appends O(n) amortized, because the copy cost grows linearly while the gap between resizes stays constant.

Example answers

Strong: I'd walk them through the geometric series: doubling means the copy costs are n, n/2, n/4, ... which sum to under 2n total for n inserts, so the per-insert average is constant. The accounting view is cleaner for intuition — charge every push 3 'tokens', one pays for placing the element, the other two bank toward copying it and one already-copied element at the next resize, so the bank never goes negative.

Weak: Appending to a list is just O(1), the language handles it, so I wouldn't worry about the resize.