A dynamic array grows by moving to a bigger block whenever the current one fills up. It allocates the new block, copies every element over, and releases the old one. The new block is a constant factor larger, often 1.5 or 2 times. Java's ArrayList grows by half each time, and CPython's list by about an eighth.
That copy costs O(n), so a single resize is not cheap. But resizes get rarer as the array grows. With doubling, going from 8 to 16 to 32 slots means the gaps between resizes keep doubling.
Spread the total copy work across every append, and each one averages out to constant time. That is what amortizedO(1) means. An individual append occasionally spikes, but the long-run cost per append stays flat. Appending a million items in a row stays fast overall.
Rewriting in plainer words…
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
A dynamic array stores its elements in one block. Capacity is how many slots the block has. Length is how many hold an element.
1 / 6← → keys
Each copy moves twice as many elements but makes room for twice as many appends, so the average cost per append stays constant. That is amortized O(1).
Saved in this browser - sign in to keep your review list.
How should your speech become text?
Listening… your words appear above as you speak - tap Stop when you're done.
Recording · cr - tap Stop & transcribe when you're done.
Transcribing with AI…
Voice:
Keep going - a few more words and AI can grade it.
Interview lens
How interviewers actually use this question
Likely follow-ups
Can you show that n appends with doubling do only O(n) total copy work?The copies form a geometric series, 1 + 2 + 4 + ... up to n, which adds up to less than 2n, so the total stays linear.
Why grow by a constant factor instead of adding a fixed number of slots each time?Adding k slots means a copy every k appends. Total copying grows like n squared over k, so each append averages O(n).
An append can still stall on a big resize. When does that matter, and how do you avoid it?Latency-sensitive code feels the O(n) copy. If you know the final size, preallocate the capacity up front so no resize happens.
When a dynamic array fills up, it allocates a bigger block, copies every element over, and frees the old one.
The new block is a constant factor larger, often 1.5 or 2 times, and Java's ArrayList, for example, grows by half each time.
That copy is O(n), so a single resize isn't cheap.
But resizes get rarer as the array grows, so with doubling, going from 8 to 16 to 32 slots, the gap between resizes doubles each time.
Spread the total copy work across every append and each one averages out to constant time, and that's what amortized O(1) means.
The limit is that an individual append can still spike to O(n), so appends are fast over a long run, not every single time.
Weak answers to avoid
Says every append is O(1)Some appends copy the whole array and cost O(n). Say the cost is O(1) averaged over a sequence of appends, and explain where the expensive ones go.
Grows by a fixed number of slotsAdding, say, 10 slots each time makes n appends cost O(n squared). The new capacity has to be a multiple of the current one.
Treats amortized as average caseAmortized holds for every sequence of appends, with no luck about inputs. Average case, as with hash lookups, depends on the input. Keep the two apart.
Says resizes are rare and stops thereRare alone proves nothing. Show the gaps between resizes double, so total copying over n appends stays under 2n and each append costs O(1) on average.
Interview lens
Likely follow-ups, what you can say, and the weak answers to avoid.
