Dynamic array and amortised growth
easyMost pushes write one slot; occasionally one reallocates and copies everything. Because the expensive pushes get rarer exactly as fast as they get more expensive, the average stays constant. Set the growth factor to +1 to see it break.
O(1) amortisedWorst O(n)Space O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How dynamic array and amortised growth works
A dynamic array is a plain array wearing a growth policy. Push into spare capacity and it is one write. Push into a full block and it allocates a bigger one, copies every element across, and then writes - that single push costs O(n). The trick is making the expensive pushes rare enough not to matter.
Doubling does exactly that. Growing 1 → 2 → 4 → 8 means reaching size n copies 1 + 2 + 4 + … + n/2 elements - fewer than n in total, a geometric series. Spread over n pushes, the whole growth history costs less than one extra pass over the array, which is what amortised O(1) means: no single push is guaranteed cheap, but the average is.
The policy is the whole game. This visualizer grows by ×2, by ×1.5, or by +1 - and +1 is the trap: every single push reallocates, the copy counter goes quadratic, and a linear fill quietly becomes O(n²). Any factor above 1 keeps the average constant; adding a constant never does.
Step by step
- Start empty with capacity 1. Push 17: it fills the only slot. Size 1, capacity 1, no copies yet.
- Push 42: the block is full, so allocate capacity 2, copy one element across, then write. That push cost O(n).
- Push 8: full again. Allocate capacity 4, copy both elements, write 8. Three copies so far.
- Push 91: capacity 4 still has a spare slot, so this is a single write - the cheap case doubling is buying.
- Push 23: full at 4. Allocate 8, copy four elements, write. Five pushes, seven copies, capacity 8 - three slots of headroom.
- Pop removes 23 but capacity stays 8. Shrinking on every pop would make alternating push and pop cost O(n) each.
Complexity
| Average time | O(1) amortised |
|---|---|
| Worst case time | O(n) |
| Space | O(n) |
Doubling from 1 to n copies fewer than n elements in total - a geometric series.
Reference implementation
Python
class DynamicArray:
def __init__(self):
self._data = [None] * 1
self._size = 0
def push(self, v):
if self._size == len(self._data):
self._grow()
self._data[self._size] = v
self._size += 1
def _grow(self):
bigger = [None] * (len(self._data) * 2) # doubling is the key
for i in range(self._size):
bigger[i] = self._data[i] # O(n) copy
self._data = biggerJavaScript
class DynamicArray {
#data = new Array(1);
#size = 0;
push(v) {
if (this.#size === this.#data.length) this.#grow();
this.#data[this.#size++] = v;
}
#grow() {
const bigger = new Array(this.#data.length * 2); // doubling
for (let i = 0; i < this.#size; i++) bigger[i] = this.#data[i];
this.#data = bigger;
}
}Worth noticing
Amortised O(1), not O(1)
Most pushes write a single slot. Occasionally one triggers a full copy. Because the expensive pushes get rarer as fast as they get more expensive, the total cost of n pushes is O(n) - so the *average* is constant even though no individual push is guaranteed to be.
Why doubling and not +1
Set the growth factor to +1 and push twenty values: the copy counter goes quadratic, because every single push reallocates. Any constant factor greater than 1 gives amortised O(1); adding a constant does not.
Copies total less than the final size
Doubling from 1 to n copies 1 + 2 + 4 + … + n/2 < n elements in total. The whole growth history costs less than one final pass over the array - a geometric series doing the work.
Common pitfalls
- Growing by a constant instead of a factor. Adding one slot at a time reallocates on every push and turns a linear fill into O(n²) - the demo's +1 setting exists to show the copy counter explode.
- Holding a pointer or iterator across a push. Reallocation frees the old block and leaves the reference dangling - exactly why C++ invalidates vector iterators on push_back.
- Treating amortised O(1) as real-time O(1). The occasional push copies everything and shows up as a latency spike; preallocate with reserve when the final size is known.
- Shrinking capacity the moment size drops. Free at half full and a workload oscillating across that boundary pays a full copy in both directions, every time.
- Confusing size with capacity. Size is elements stored; capacity is slots allocated. The gap between them is where the cheap pushes live.
Where it is used
- Python lists, Java's ArrayList, Go slices, C++ vectors and JavaScript arrays all grow this way under the hood.
- String builders amortise concatenation with the same doubling argument, one character type down.
- Hash tables reuse the trick at resize time - double the buckets, rehash everything, stay amortised O(1).
- A standard interview follow-up: why is push amortised O(1), and what breaks with +1 growth?
Frequently asked questions
What is the time complexity of pushing to a dynamic array?
Average O(1) amortised, worst case O(n) for the individual push that triggers a reallocation, and O(n) space. The amortised claim rests on a geometric series: doubling from capacity 1 up to n copies fewer than n elements in total, so n pushes cost O(n) overall - constant each on average.
What does amortised O(1) actually mean?
That the average over any sequence of pushes is constant, even though no single push is guaranteed to be. Most pushes write one slot; a push into a full block copies everything first. The expensive pushes get rarer exactly as fast as they get more expensive, so the total stays linear.
Why do dynamic arrays double instead of growing by a fixed amount?
Any factor above 1 keeps the copy total geometric and the average push constant. A fixed increment does not: with +1 growth every push reallocates, and filling 20 slots costs 190 copies. Set the growth factor to +1 in the visualizer and watch the copy counter go quadratic.
Why do some implementations grow by 1.5 instead of 2?
A gentler factor trades a few extra reallocations for allocator friendliness. Below the golden ratio, the memory freed by earlier growth eventually adds up to enough to hold a later block, so the allocator can reuse it; with doubling, the new block always exceeds everything freed so far. MSVC's vector uses 1.5. Both are amortised O(1).