Amortized Analysis of Dynamic Arrays

A dynamic array stores elements contiguously and grows by allocating a larger block and copying the old contents. The copy is O(n). If a program appends n elements, a naive worst-case reading says the cost is O(n²). That reading is wrong for any implementation that grows geometrically, and the reason is worth understanding precisely, because the same argument recurs in hash tables, splay trees, and union-find.

The cost model

Fix a growth policy: when the buffer is full, allocate capacity 2c for current capacity c and copy c elements. Ignore allocator behaviour and cache effects; count element copies.

Track capacity through a sequence of n appends. Capacity after the k-th reallocation is 2^k starting from an initial capacity of 1. A reallocation happens at sizes 1, 2, 4, 8, … and costs exactly the number of elements moved. Total copy cost after n appends is

$$ 1 + 2 + 4 + \cdots + 2^{m} = 2^{m+1} - 1 < 2n $$

where 2^m ≤ n < 2^{m+1}. The total is bounded by twice the number of appends, so the average cost per append is below 2 copies. Appending n elements costs Θ(n) in total, not Θ(n²).

The bound holds because the work at each reallocation is proportional to the current size, and the sizes at which reallocations occur form a geometric series. A policy that grew by a constant, allocate c + 100 when full, would reallocate every 100 appends and copy the whole array each time, giving Θ(n²) total. The growth factor is what makes the amortized bound work, not the act of copying.

Three ways to prove it

Amortized analysis assigns costs to operations so that the sum of assigned costs bounds the true total. The three standard methods give the same answer by different routes.

Aggregate method

Sum the true costs of a sequence of n operations and divide. Above, the sum is bounded by 2n, so the amortized cost per operation is at most 2. This is the simplest method and requires no credit bookkeeping; it works whenever a full sequence can be bounded directly.

Accounting method

Charge each append 3 units instead of its true cost of 1 when no resize occurs. One unit pays for the append itself; the remaining 2 accumulate in a credit pool attached to the array rather than to any single element. For an array that started empty with capacity 1, the pool holds 2n − c + 1 units when the array has n elements in a buffer of capacity c, so it never goes negative.

A doubling happens only when the buffer is full, that is when n = c, and at that moment the pool holds c + 1 units, which covers the c copies the resize has to make. The charge for that resize contributes 2 − c to the pool, so the pool is exactly 3 units immediately after every doubling and grows by 2 with each append that does not resize; filling the buffer again brings it back to c + 1. The balance is positive throughout, which is the accounting-method statement of the same geometric series the aggregate method summed.

Potential method

Define a potential function over data structure states. For a dynamic array with n elements and capacity c, one suitable choice is

$$ \Phi = 2n - c $$

with the convention that capacity is at least n. The amortized cost of an operation is its true cost plus the change in potential, c_i + Φ_i − Φ_{i−1}.

An append with spare capacity has true cost 1, increments n, and leaves c unchanged, so ΔΦ = 2 and the amortized cost is 3. An append that triggers a resize from c to 2c has true cost 1 + c (one write plus c copies). Here n goes from c to c + 1, and capacity goes from c to 2c, so Φ goes from 2c − c = c to 2(c+1) − 2c = 2. Then ΔΦ = 2 − c, and the amortized cost is (1 + c) + (2 − c) = 3.

Every operation has amortized cost 3, so any sequence of n appends costs at most 3n. The potential is bounded above by n, because Φ = 2n − c ≤ n whenever c ≥ n, and it is non-negative once the buffer has been grown, because c ≤ 2n after a resize; only the initial state of a buffer that has never been grown has Φ = −1, and only the change in potential enters the sum.

What amortized bounds do and do not promise

An amortized bound is a statement about sequences. It does not bound any single operation. One append in the sequence still costs Θ(n). This distinction matters in practice:

• Latency-sensitive code. A growable array is a poor fit for a loop with a hard deadline on each iteration, because the append that triggers a reallocation copies the whole buffer while the appends around it do not.
• Persistent or concurrent structures. If an operation can be observed individually and the observer can be delayed arbitrarily, amortized credit accumulated by earlier operations may not be available when needed.
• Interleaved structures. An amortized bound proved for a sequence of operations on one structure does not automatically hold when operations on several structures are interleaved, unless the potential function accounts for all of them.

Two standard mitigations exist. The first is incremental resizing: allocate the new buffer but move a fixed number of elements per subsequent operation, spreading the copy across many operations so no single one is expensive. The second is deallocation deferral: keep the old buffer alive until the incremental copy completes, so concurrent readers can still access it.

Growth factors and their consequences

The choice of growth factor is a trade-off between wasted space and copy volume.

Growth factor	Total copies for n appends	Unused share of the buffer just after a resize
1.25	≈ 5n	≤ 20%
1.5	≈ 3n	≤ 33%
2.0	< 2n	≤ 50%

Smaller factors reduce peak memory overhead but increase total copying, because more reallocations occur. Larger factors reduce copying but leave up to half of the buffer unused just after a resize.

There is a second, subtler consideration: memory reuse. When a buffer of size c is freed and a buffer of size 2c is requested, the allocator must find a new region. Some allocators can extend a mapping in place if the adjacent virtual address range is free; otherwise the old pages are released and new ones faulted in. With a growth factor of 2, the freed block is exactly half the size of the requested block and cannot satisfy the new request on its own. Factors below 2 leave a freed region large enough to serve some later allocation, which is the reason several implementations use 1.5.

This is why the C++ standard specifies capacity() semantics without fixing a growth factor, and why implementations differ. libstdc++ grows by doubling, while several other standard libraries grow by a factor of 1.5. Both satisfy the amortized bound; neither is required by the language.

Implementation sketch

The essential invariant: capacity is a power of two times the initial capacity, and the buffer is replaced only when full. A minimal implementation in TypeScript:

class DynArray<T> {
  private buf: (T | undefined)[];
  private len = 0;

  constructor(initial = 4) {
    this.buf = new Array(initial);
  }

  get length() {
    return this.len;
  }

  get capacity() {
    return this.buf.length;
  }

  push(value: T): void {
    if (this.len === this.buf.length) {
      const next = new Array<T | undefined>(this.buf.length * 2);
      for (let i = 0; i < this.len; i++) next[i] = this.buf[i];
      this.buf = next;
    }
    this.buf[this.len++] = value;
  }

  get(index: number): T {
    if (index < 0 || index >= this.len) throw new RangeError('index out of bounds');
    return this.buf[index] as T;
  }
}

Two details deserve attention. The copy loop is a linear scan, which is the operation the amortized analysis counts. And this.buf.length doubles exactly, so the capacity sequence is geometric. Replacing the copy loop with a bulk operation (copyWithin, System.arraycopy, memcpy) does not change the asymptotics but lowers the constant, because the loop copies element by element while the bulk primitive moves whole memory ranges.

In a garbage-collected runtime the old buffer becomes unreachable after the assignment and is reclaimed later; peak memory during the copy is therefore 3c elements’ worth (old c, new 2c) until collection. In a manually managed runtime the old buffer must be freed explicitly, and the timing of that free affects peak memory the same way.

Where the same argument appears

The doubling argument is a template. The same structure, occasional expensive work paid for by many cheap operations, underlies:

• Hash table resizing. Rehashing all entries when the load factor exceeds a threshold costs Θ(n), but geometric table growth makes the amortized cost per insertion constant.
• Union-find with path compression and union by rank. The near-constant amortized bound follows from a potential argument over tree structure, not from a simple geometric series, but the shape of the claim is identical.
• Splay trees. Each access can be Θ(n) in the worst case; the amortized cost is O(log n) by a potential function over tree shape.
• Binary counters. Incrementing a binary counter flips a variable number of bits, but the amortized number of flips per increment is 2, by the same aggregate argument.

In each case, the analysis is a proof about sequences, and the practical question is always whether the caller’s workload is a sequence in the required sense.

When the bound does not apply

Three conditions are easy to violate without noticing.

Adversarial interleaving. If an adversary can force a resize at a moment of its choosing and then observe the cost, the amortized bound still holds over the full sequence but says nothing about the observed operation. Systems that must bound individual operation latency need incremental resizing.

Persistent data structures. A purely functional array that copies on write cannot use in-place credit; each version must remain valid, and the stranded credit that results is the subject of amortized bounds under persistence. Persistent vectors use tree structures (such as a radix-balanced trie) whose bounds are derived differently, typically O(log₃₂ n) per update with structural sharing.

Multiple structures, one potential. If two dynamic arrays share an allocator and their resizes compete for memory, an analysis of each in isolation ignores the interaction. The potential function must cover the combined state, or the bound must be re-derived.