Dynamic Arrays: How Resizing Works

The Problem with Fixed Size

In the real world, you rarely know in advance how many items you will store. You need a structure that grows on demand. This is what Dynamic Arrays provide — Python's list, Java's ArrayList, and C++'s std::vector are all dynamic arrays under the hood.

The Resizing Algorithm

The mechanism is straightforward but has important performance implications:

1. Creation: Allocate a small backing array (e.g., capacity 4).
2. Fill: Add items normally until the array is full.
3. Overflow detected: You attempt to add a 5th item to a capacity-4 array.
4. Double: Allocate a new array of double the capacity (capacity 8).
5. Copy: Copy all existing elements into the new array — this is O(N).
6. Add: Write the new item into the next available slot.
7. Discard: The old array is freed.

Why Double? The Amortized Analysis

Doubling (rather than growing by 1 each time) is the key insight. If you grew by 1 each time, every single insertion would trigger a copy, making every insert O(N). By doubling, you ensure that by the time you need to resize again, you have done at least N cheap O(1) insertions since the last resize.

Formally: if you perform N insertions total, the total copy work across all resizes is 1 + 2 + 4 + 8 + ... + N = 2N. Spread across N insertions, that is O(1) amortized per insertion.

Insertions 1–4:   O(1) each, no resize
Insertion 5:      O(4) copy + O(1) insert → resize to capacity 8
Insertions 6–8:   O(1) each
Insertion 9:      O(8) copy + O(1) insert → resize to capacity 16
...

The expensive operations happen less and less frequently as the array grows. This is the definition of amortized O(1): not every operation is O(1), but the average cost per operation over a long sequence is O(1).

Key Point: The amortized analysis only holds for appending to the end. Inserting at the beginning or middle of a dynamic array is still O(N) because of the element-shifting cost, regardless of resizing. This is a common interview trap — candidates assume "dynamic array = O(1) insert" without specifying where the insert occurs.