Growing One Slot at a Time

Our grow doubles the capacity. The factor of two probably looked arbitrary when we wrote it. It is not arbitrary. This section and the next show why.

To see why, imagine grow added a fixed number of slots instead. Then the array would fill up again sooner, so the expensive adds would come more often, so there would be fewer cheap adds to spread each expensive one across. The amortized cost would go up. Let’s compute by how much, using the simplest such strategy: growing by one slot at a time.

Suppose we start with an empty DynamicArray that has internally allocated a fixed-size array of size $1$ . Let’s calculate the amortized cost of add over a sequence of one million insertions, where grow only adds one slot each time the array fills.

Starting from capacity $1$ , the array is full as soon as we add the first element. From then on, every add finds the array full and must grow it by one slot, copying everything already stored:

One arrow per copied element:

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

This continues until the millionth add copies $999, 999$ elements (capacity $999, 999 \to 1, 000, 000$ ).

Most of the work in each add is this copying. Summing the copies across all the grows:

1 + 2 + \dots + 999, 999 = 499, 999, 500, 000 \approx 500 billion

The amortized cost of add is then

\frac{500 billion}{1 million} = 500, 000

That is half a million copies per add, on average.

Now let’s do the same thing in general, for $n$ adds instead of one million. The total number of copies is $1 + 2 + \dots + (n - 1)$ , an arithmetic series, and that sums to $n (n - 1) /2$ . So the total work over $n$ adds is $O (n^{2})$ , and the amortized cost per add is

\frac{O ( n ^{2} )}{n} = O (n)

We could have reached the same result without the math by reasoning about the number of grow calls. Growing by one slot means every single add calls grow, so the number of grow calls is $n$ , which grows linearly with the number of adds. Each of those calls costs up to $O (n)$ , because it copies the whole array. Multiply the two and you get $O (n^{2})$ for $n$ adds.

Growing by ten slots at a time, or by any fixed number $c$ , does not change this result. It only calls grow on every $c$ -th add rather than every add, so the number of grow calls is $n / c$ . Big-Oh drops the constant factor $1/ c$ , so the number of grow calls is still linear in $n$ , each grow still costs up to $O (n)$ , and the total is still $O (n^{2})$ . The amortized cost is still $O (n)$ .

So if we grow by a fixed number of slots, grow gets called too often. There are not enough cheap adds between two grows to pay for the next grow. What we need is a grow that gets called less and less often as the array gets larger.