Choosing a growth factor

A dynamic array that has run out of room allocates a bigger one and copies. How much bigger?

Any factor above 1 gives an amortised constant cost per append, so the complexity class does not decide it. The choice is entirely in the constants, and the constants pull in opposite directions: a larger factor means fewer copies and more memory sitting unused, a smaller factor means the reverse.

Measured, appending twenty thousand elements:

Reading the trade #

The shape is a hyperbola, and the interesting part is how quickly the returns diminish.

Going from ×1.125 to ×2 cuts the amortised cost by a factor of 3.7, from 9.89 to 2.64. Going from ×2 to ×4 cuts it by a further 21%, from 2.64 to 2.09, and costs an extra 30 percentage points of wasted memory. The elbow is somewhere between 1.5 and 2, which is where essentially every implementation lands.

Note that ×3 does not sit neatly between ×2 and ×4 — it measures 2.48 and wastes 66%, worse on the memory axis than ×4 by only three points while giving up most of the time saving. Where the final capacity happens to land relative to $n$ is doing that, which is the next paragraph’s subject.

The waste column deserves care, because it is not monotone and the non-monotonicity is real rather than noise. Growing by ×1.25 leaves only 1% unused at twenty thousand elements, less than ×1.125’s 10%, because where the final capacity falls relative to $n$ depends on the exact sequence of allocations and can land almost exactly on $n$ by luck. The waste figure is a snapshot at one $n$, and the honest quantity is the expected waste over a uniformly random stopping point, which for factor $g$ is about $\frac{g-1}{2g}$ — 25% for doubling, 17% for ×1.5, 10% for ×1.25.

The measured single-$n$ figures are noisier than that formula and bracket it, which is worth knowing before quoting either.

Why the factor does not change the class #

Worth pausing on why every factor above 1 gives the same complexity class, because it is the reason the choice is a pure constant-factor question.

With growth factor $g$, the capacities are $1, g, g^2, \ldots$ and the total copying to reach $n$ elements is

$$1 + g + g^2 + \cdots + g^k = \frac{g^{k+1}-1}{g-1} \approx \frac{g}{g-1}\, n$$

Divided by $n$ appends, that is $\frac{g}{g-1}$ — a constant for any fixed $g > 1$, and one that blows up as $g$ approaches 1. Substituting: $g = 2$ gives 2, $g = 1.5$ gives 3, $g = 1.25$ gives 5, $g = 1.125$ gives 9.

Those are exactly the measured numbers, to within the rounding that ceil introduces at small capacities: 2.64, 3.73, 5.04, 9.89 against predicted 2, 3, 5, 9 plus one unit per append for the writes themselves. The formula and the simulation are two independent routes to the same quantity and they agree, which is the discipline this site applies wherever two routes exist.

The blow-up as $g \to 1$ is the same limit that makes a fixed-step array quadratic. There is no discontinuity: the cost per append is $\frac{g}{g-1}$, which is finite for every $g > 1$ and infinite in the limit, and a fixed step is that limit.

The peak is worse than the waste #

There is a second memory cost that the table above does not show and that decides the question in some systems.

During a resize, both arrays exist at once. Growing a doubling array from capacity $c$ to $2c$ requires $3c$ elements of memory momentarily. The peak footprint is 1.5 times the new capacity, and close to a memory limit, that transient peak is what fails.

Growing by ×1.5 has a peak of $2.5c$ against a new capacity of $1.5c$ — a ratio of 1.67, worse relative to the result but smaller in absolute terms. The comparison depends on which quantity is the binding constraint, which is a familiar refrain on this site: the ranking depends on which count is chosen, and here the two counts are peak memory and steady-state memory.

The allocator argument for 1.5 #

There is a widely repeated argument that growth factors below the golden ratio $\varphi \approx 1.618$ allow an allocator to reuse previously freed blocks, and that this is why several standard libraries use 1.5.

The argument goes: with factor $g$, the sum of all previously freed capacities is $1 + g + g^2 + \cdots + g^{k-1} = \frac{g^k - 1}{g - 1}$. For the next allocation of size $g^{k+1}$ to fit in that freed space requires $\frac{g^k-1}{g-1} \ge g^{k+1}$, which for large $k$ requires $g^2 - g - 1 \le 0$, giving $g \le \varphi$. With doubling, the freed blocks are always one short of what is needed, so the array marches forever upwards through the address space and never reuses anything.

It is a genuinely elegant piece of reasoning and its practical force depends entirely on the allocator. It assumes the freed blocks are contiguous and coalesced, which requires that nothing else allocated in between — an assumption that fails in most real programs. Modern allocators also use size classes, so a request for $1.5c$ and a request for $2c$ may land in the same bucket and behave identically.

So: a real consideration, frequently overstated, and impossible to settle from this site’s measurements because the site models an array and not an allocator. Where an implementation has chosen 1.5 there is usually a benchmark behind it as well as the argument.

Growing by a fixed amount is the mistake #

The failure worth naming is growing by a constant amount rather than a constant factor: capacity increases by 1, or by 16, or by 1,024, each time it fills.

This is quadratic. With a step of $s$, the resizes happen at sizes $s, 2s, 3s, \ldots$ and the total copying is $s(1 + 2 + \cdots + n/s) \approx \frac{n^2}{2s}$. Dividing by $n$ appends gives $\frac{n}{2s}$ per append — which grows with $n$ and is therefore not a constant at all.

It is an easy mistake to make and a hard one to notice, because for small $n$ and a decent step size the cost per append is small and the structure works perfectly. The quadratic nature shows up only when the data gets big, which is usually in production.

The site’s gate asserts that the amortised-constant check refuses a fixed-step array. That is the must-reject discipline applied here: a check that accepted a quadratic append would be certifying nothing, and there would be no other symptom.

The measurement across sizes is how the difference becomes visible. A doubling array’s amortised cost is 2.023 at 1,000 appends and 2.024 at 64,000 — flat to four digits across a factor of 64. A fixed-step array’s would rise by the same factor of 64.

What the standard libraries do #

The published choices, for context rather than as authority:

• C++ std::vector — the standard specifies only amortised constant. GCC’s libstdc++ doubles; MSVC’s implementation uses 1.5.
• Java ArrayList — grows by 50%, i.e. ×1.5.
• Python list — grows by roughly ×1.125 plus a constant, deliberately modest, with the small additive term keeping the tiny cases sane.
• Rust Vec — doubles, with a minimum first allocation depending on element size.
• Go slices — doubled below 256 elements and then grow by a decreasing factor approaching ×1.25, an explicit attempt to get the best of both regimes.

The range is 1.125 to 2, which is exactly the range where the measured curve has its elbow. The disagreement is not carelessness; it is different weightings of a trade-off that has no dominant answer, made by people optimising for different workloads.

Python’s ×1.125 is the outlier and the reasoning is visible in its behaviour: with an amortised cost near 10 units per append it is the most expensive on the table, and CPython’s per-append overhead is dominated by interpreter dispatch rather than by memory copying, so ten units of copying costs proportionally much less than it would in C. The memory saving is real and the time cost is hidden by a larger constant elsewhere — which is a decision that only makes sense once the constants in that context are known.

The shrink question #

A dynamic array that only ever grows is easy. One that also shrinks when elements are removed has a trap in it, and the trap has the same shape as everything else on this page.

The naive rule — halve the capacity when the array is half empty — produces thrashing. Sit exactly at the boundary and alternate one append with one removal: the append triggers a growth and copies everything, the removal triggers a shrink and copies everything back, and every single operation costs $\Theta(n)$. The amortised bound is destroyed by a sequence that does nothing.

The fix is hysteresis: shrink only when the array is a quarter full, halving to half full. Now after a resize the array is far from either boundary, and $\Theta(n)$ operations must happen before another resize can be triggered — which is exactly the condition the amortised argument needs.

This is a good illustration of why amortised bounds are about sequences and cannot be checked one operation at a time. Both rules make every individual operation look identical. Only a sequence distinguishes them, and only an adversarially chosen sequence distinguishes them quickly.

Reserving up front #

There is a way to avoid the whole question, and it is worth naming because it is usually the right answer when it is available.

If the final size is known in advance, reserve it. One allocation, no copies, no waste, no growth factor. The amortised cost falls to exactly one unit per append — the write — and the sawtooth disappears entirely.

Measured against a doubling array’s 2.02 units per append, reserving halves the cost of building a large array, and against ×1.125 it divides it by ten. That is a much larger saving than any choice of growth factor buys, and it is available whenever the size is computable or even roughly estimable — reserving too much wastes memory once and copies nothing.

This is the general shape of the best optimisations on this site: not a better algorithm within the constraints, but a change to the constraints. Counting sort escapes the comparison floor by not comparing; reserving escapes the growth-factor trade by not growing. In both cases the escape needs extra information — a bounded key range, or the final size — and the information is often available for the asking.

What none of this measures #

Two things, both of which could reverse the conclusion for a given system.

Memory locality of the copy. A resize copies a contiguous block, which is the cheapest access pattern hardware offers and the one this site’s cache model charges least for. Counting copies as units of equal cost overstates the price of copying relative to almost any other operation. That biases the whole analysis towards larger factors than it should.

Whether the memory is ever touched. An allocation that is never written may cost nothing at all, because operating systems allocate address space lazily and commit pages on first touch. A doubling array’s 39% unused capacity may be 39% of address space and close to 0% of physical memory — which makes the waste column much less alarming than it looks, on a system with virtual memory and without an overcommit limit.

Both push in the same direction, towards doubling being a better default than the table suggests. Neither is measurable with an array simulator, and saying so is more useful than a number that pretends otherwise.