Dynamic Array¶

A dynamic array is an array that grows. It stores its elements in a fixed-size block of memory and, when that block fills up, allocates a larger one and copies everything across. Python's list, Java's ArrayList and C++'s std::vector are all dynamic arrays.

The guide's implementation is DynamicArray. For the other classic way to store a sequence, and how the two compare, see the singly linked list and the doubly linked list.

How it works¶

The array keeps two numbers: its length, the number of elements in use, and its capacity, the number of slots allocated. Appending writes into the next free slot. When the length reaches the capacity there is no free slot, so the array resizes: it allocates a new block, copies every element into it, and carries on.

A single resize costs O(n), because it copies all n elements. What matters is how often that happens, and that is decided by the growth policy: the rule for choosing the new capacity.

Growth policies¶

Doubling is geometric growth with a factor of 2.

Amortized cost of append¶

With geometric growth, each resize is bigger than the last, but resizes also become rarer at exactly the same rate. Appending n elements copies fewer than 2n elements in total with doubling, so the average cost per append is constant. This is amortized O(1): an individual append is occasionally expensive, but any long run of appends averages out to a constant each.

With additive growth, resizes never become rarer. A step of 16 copies the whole array every 16 appends, forever, which adds up to about n² / 32 copies for n appends. Each append costs O(n) on average.

The two subsections below count the copies exactly. The formulas they lean on are collected in the math cheat sheet.

Counting the copies: additive growth¶

Take an array that grows by a fixed step of \(k\) slots and, to keep the arithmetic clean, starts with a capacity of \(k\). Append \(n\) elements and count every element copied by a resize.

When do resizes happen? The capacity is always a multiple of \(k\), and a resize happens when an append finds the array full. So the resizes happen at lengths

where \(m\) is the number of resizes. The last one happens at the largest multiple of \(k\) that is still below \(n\), so

What does each resize cost? A resize copies every element in the array. The \(i\)-th resize happens at length \(ik\), so it copies \(ik\) elements.

Add them up. The total number of copies \(C(n)\) is the sum over all \(m\) resizes. The step \(k\) is a constant, so it factors out, and what is left is the arithmetic series:

Put it in terms of \(n\). The number of resizes \(m\) is \(n / k\), give or take rounding. Substituting \(m \approx n / k\):

Handling the rounding exactly moves the answer by at most \(n\). For every \(n \ge k\):

The \(n^2\) term dominates both bounds, so

The number of copies grows quadratically with the number of appends: doubling \(n\) quadruples the copying. With a step of \(k = 16\) the leading term is \(n^2 / 32\), the figure quoted above.

Amortize. The amortized cost of one append is the total cost of \(n\) appends divided by \(n\). Each append also does one write of its own, which adds \(n\) to the total:

Each append costs linear time on average. The step \(k\) only appears in the denominator of a constant: a larger step makes the line shallower, but it is still a line.

Counting the copies: doubling¶

Run the same count for an array that starts with a capacity of 1 and doubles. Now the resizes happen at lengths

and the last of them is below \(n\), so \(2^{m-1} < n\). The total is a geometric series:

Fewer than \(2n\) copies for \(n\) appends, so \(C(n) = \Theta(n)\) and the amortized cost of an append is

The difference between the two policies is the difference between the two series. An arithmetic series sums to roughly the square of its number of terms, and additive growth has \(n / k\) terms. A geometric series sums to roughly twice its last term, and the last term here is below \(n\).

Measured¶

The benchmark below appends n integers to an empty array and times the whole run. The first tab divides each time by n, giving the cost of one append: a line that stays flat is constant cost per append, and one that climbs is not. The second tab shows the total time, where the steeper line is the quadratic one. Both axes are logarithmic.

Measured on cs-survival-kit 0.8.0 · CPython 3.13.16 · Linux x86_64 · 2026-10-08. Each time is the best of five runs. The slope is fitted on a log-log scale: about 1 is linear, about 2 is quadratic. Both chart axes are logarithmic, so a power law is a straight line and its steepness is that slope.

Both geometric policies stay flat as n grows by four orders of magnitude, just like the built-in list. The additive column grows in step with n. list is faster throughout because it is implemented in C; what the two share is the shape of the curve.

Choosing a factor¶

Any factor above 1 gives amortized O(1) appends. The factor trades time for memory: a larger one resizes less often, but leaves more of the capacity unused straight after a resize.

Measured on cs-survival-kit 0.8.0 · CPython 3.13.16 · Linux x86_64 · 2026-10-08. Each time is the best of five runs. The slope is fitted on a log-log scale: about 1 is linear, about 2 is quadratic. Both chart axes are logarithmic, so a power law is a straight line and its steepness is that slope.

A larger step does not fix additive growth¶

It is tempting to think a big enough step makes additive growth acceptable. A larger step does start out cheap, but the cost per append still rises with n. It delays the quadratic behaviour without removing it.

Measured on cs-survival-kit 0.8.0 · CPython 3.13.16 · Linux x86_64 · 2026-10-08. Each time is the best of five runs. The slope is fitted on a log-log scale: about 1 is linear, about 2 is quadratic. Both chart axes are logarithmic, so a power law is a straight line and its steepness is that slope.

Complexity¶

These assume a geometric growth policy.