Why Doubling Works

Growing by a fixed number of slots made add cost $O (n)$ amortized. The problem is that grow gets called just as often no matter how large the array is. Doubling does not have that problem. The bigger the array, the more room a doubling adds, so grow gets called less and less often as the array grows.

Let’s redo the calculation from the previous section with doubling. Start with an empty DynamicArray whose underlying array has capacity $1$ , and do one million adds, where grow doubles the capacity each time the array fills.

A grow happens only when the array is full. One arrow per copied element:

┌────┐
│ 10 │
└────┘
  ↓                                        2nd add copies 1
┌────┬────┐
│ 10 │ 20 │
└────┴────┘
  ↓    ↓                                   3rd add copies 2
┌────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │
└────┴────┴────┴────┘
  ↓    ↓    ↓    ↓                         5th add copies 4
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │ 60 │ 70 │ 80 │
└────┴────┴────┴────┴────┴────┴────┴────┘
  ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓     9th add copies 8
                                           ⋮

The 1st add goes into the capacity- $1$ array and fills it. Nothing is copied. The 2nd add finds the array full, so grow copies $1$ element. The 4th add has room, so we just place the element. The 6th through 8th adds have room too. The adds between grows copy nothing. This continues until the $524, 28 9^{th}$ add finds the array full, so grow copies $524, 288$ elements (capacity $524, 288 \to 1, 048, 576$ ). The $524, 29 0^{th}$ through millionth adds have room.

As before, most of the work is the copying done inside grow. The successive grow calls copy $1$ , then $2$ , then $4$ , then $8$ elements, and so on. Each grow copies twice as many elements as the one before it, because each grow doubles the capacity and the array fills up again before the next grow.

Now let’s do it in general, for $n$ adds. To keep the arithmetic simple, take $n$ to be a power of two. The total copying is

1 + 2 + 4 + 8 + \dots + \frac{n}{2}

Why does the sum stop at $n /2$ ? The largest array we ever copy is the one of capacity $n /2$ . Filling it triggers a grow to capacity $n$ , which copies its $n /2$ elements. The array of capacity $n$ is never grown, because the $n^{th}$ add fills its last slot without overflowing. So $n /2$ is the last term.

Written with exponents, the terms are:

2^{0}, 2^{1}, 2^{2}, \dots, 2^{(l o g n) - 1}

There are $lo g n$ of them. (Recall that $lo g n$ here means $lo g_{2} n$ , and that $2^{l o g n} = n$ , so $2^{(l o g n) - 1} = n /2$ .)

This is a geometric series. The sum of the first $k$ terms of a geometric series with first term $a_{1}$ and common ratio $r$ is

S_{k} = \frac{a _{1} ( r ^{k} - 1 )}{r - 1}

Here $a_{1} = 1$ , $r = 2$ , and $k = lo g n$ . Plugging in:

S_{k} = \frac{1 \cdot ( 2 ^{l o g n} - 1 )}{2 - 1} = 2^{l o g n} - 1 = n - 1

So the total copying over $n$ adds is $n - 1$ , which is $O (n)$ . The amortized cost of add is then

\frac{O ( n )}{n} = O (1)

With a fixed increment, the number of grow calls grows linearly with the number of adds. With doubling, each grow doubles the number of adds we can do before the next grow, so the number of grow calls is only $lo g n$ . That is why the copying sum is geometric rather than arithmetic. A geometric series with ratio $2$ sums to less than twice its last term, and its last term is $n /2$ , so the total is $O (n)$ rather than $O (n^{2})$ .

The factor of $2$ itself is not the point. Growing by a factor of $1.5$ , or $3$ , would work just as well. Any multiplicative factor greater than $1$ makes the number of grow calls logarithmic in the number of adds, and that makes the total copying a geometric series. So the rule to remember is to multiply the capacity, not add to it.