The idea: spare room, and double it when it runs out

A dynamic array (Java ArrayList, C++ std::vector, Python list) is an ordinary fixed-size array plus two numbers: the capacity (how many cells the array has) and the size (how many hold values). A push writes the new value at index size and adds 1 to size. While there is a spare cell, that is one write: O(1).

Six arrays of capacity 1, 2, 4, 8, 16 and 32 drawn as rows of cells. In each, the first half (orange) was copied from the previous array: push 2 copies 1, push 3 copies 2, push 5 copies 4, push 9 copies 8, push 17 copies 16. After 32 pushes the copies add up to 31
Each new array is twice the old one, so the copies 1 + 2 + 4 + 8 + 16 = 31 never catch up with the number of pushes.

What a push into a full array does

When size == capacity there is no cell for the new value, and an array cannot get longer in place. The push has to:

  1. allocate a new array of the next capacity (2 × the old one when doubling),
  2. copy all size values into it, one write each,
  3. free the old array and use the new one from now on,
  4. write the new value at index size.

That one push costs size + 1 writes: it is O(n). With 16 values in a full array of 16, push 17 makes 17 writes, a tall orange bar on the chart (Demo: the push that copies 16).

void push(int v) {
    if (size == capacity) {
        int[] bigger = new int[capacity * 2];       // allocate
        for (int i = 0; i < size; i++)             // copy: size writes
            bigger[i] = a[i];
        a = bigger;  capacity *= 2;                 // the old array is freed
    }
    a[size++] = v;                                  // 1 write
}

Why the average stays under 3 writes

The expensive pushes get rarer exactly as fast as they get dearer. After a copy of 16, the next 15 pushes are cheap before the array fills again. Add up all the work after n pushes (the aggregate method): the copies are 1 + 2 + 4 + … , each half the next, so they add up to less than n. With the n writes of the values themselves, the total is less than 3n writes, under 3 per push. That is what O(1) amortized means: one push may be slow, but any run of n pushes costs O(n) in total (Demo: doubling, first 9 pushes).

The banker's view says the same thing: charge every push 3 coins. One pays for its own write and two go into a savings account. When an array of capacity C fills, the C/2 values pushed since the last copy have saved C coins, exactly enough to copy all C values. The account never goes negative, so 3 per push always covers the bill. The green line on the chart is that 3; the dark ticks (average so far) jump towards it after each copy and then fall away.

Pushes nCapacityCopiesWritesWrites per push
91615242.67
173231482.82
323231631.97

Other growth rules

Growing by a constant instead of a factor breaks the argument. With +1 every push after the first finds the array full and copies everything: 1 + 2 + … + (n−1) = n(n−1)/2 copies, O(n) per push on average and O(n²) in total (Demo: grow by one copies every time). Growing by +100 only divides that by 100; it is still quadratic.

Any constant factor above 1 keeps O(1) amortized. Java's ArrayList grows to old + (old >> 1), about ×1.5: it leaves less unused room (at most a third of the array instead of half) and copies a little more, about 4 writes per push at worst (Demo: ×1.5 like Java ArrayList).

Line chart of total writes against pushes n from 0 to 32. Grow by one curves up to 528 writes; times 1.5 climbs in steps to 117; times 2 climbs in steps to 63, under the dashed 3n line that ends at 96
A growth factor keeps the total writes a straight line in n; growing by one cell makes it a parabola.
Growth ruleCapacity after 32 pushesCopiesWritesWrites per push
×23231631.97
×1.5 (old + (old >> 1))42851173.66
+13249652816.5

In real libraries

  • Java ArrayList: default capacity 10 (allocated on the first add), then ×1.5. ensureCapacity(n) grows once up front.
  • C++ std::vector: ×2 in GCC's libstdc++ and Clang's libc++, ×1.5 in Microsoft's library. reserve(n) allocates once, so n push_backs then copy nothing.
  • Python list: grows by about 1/8 plus a little (still a factor), so appends are amortized O(1).

If you know the final size, reserve it: no copies at all, and no spare room left over. Hash tables use the same trick when they resize: see Java HashMap, which doubles its bucket array. A stack on an array (Stack: Array Implementation) is a dynamic array that only pushes and pops at the end.

See Array vs Linked List for how a growing array compares with a linked list on indexing, inserts and cache misses.

What the page leaves out

Shrinking on pop: a list that halves when it is half empty can thrash at the boundary, so libraries shrink at a quarter full or never. Some allocators can extend a block in place (realloc), skipping the copy. Moving instead of copying objects (C++ move constructors), the memory allocator itself (see Malloc Allocators) and insertions in the middle, which shift elements and are O(n) every time, are not drawn. See Big-O Growth Race for how O(1), O(n) and O(n²) compare.