Why does an array-list grow by doubling its capacity rather than by adding one slot at a time?

Doubling makes the expensive copies so rare that their total cost is proportional to the number of adds — on average each add costs $O(1)$ (amortised). Growing by a constant amount makes every few adds pay a full copy, giving $O(n^2)$ for $n$ adds.

* The spikes get taller but twice as far apart, so the average never climbs. *

Count the copying work for $n$ adds, starting from capacity 1.

Doubling. Copies happen when the array holds 1, 2, 4, 8, … elements. The total copied is

$$1 + 2 + 4 + \dots + \frac{n}{2} < n$$

so $n$ adds cost fewer than $n$ writes plus fewer than $n$ copies: $O(n)$ in total, $O(1)$ per add on average. Each expensive copy is "paid for" by the many cheap adds since the last one.

Growing by 1 (or by any constant $k$). Every add (or every $k$-th add) copies the whole array, so the copies cost $1 + 2 + 3 + \dots + n$ — Gauss's sum, $O(n^2)$ in total, $O(n)$ per add.

This averaging over a sequence of operations is called amortised analysis. It is not an average over random inputs: it is a guarantee that any sequence of $n$ adds costs $O(n)$, even though one individual add can cost $O(n)$.

Tip: that is why a runtime table may list addLast on an array-list as $O(n)$ (the worst single call) while the Java documentation promises "amortised constant time". Both are true; they answer different questions.

Go deeper:

• Amortized analysis — the aggregate, accounting and potential methods, with the dynamic array as the worked example.
• MIT 6.006 — Data Structures and Dynamic Arrays (Erik Demaine) — full lecture deriving the amortised $O(1)$ append.