Dynamic Arrays: Amortized Analysis

Dynamic arrays (Python lists, Java ArrayLists, C++ vectors) provide $O(1)$ amortised append by doubling capacity when full. All three amortised analysis methods confirm this bound.

The Data Structure

A dynamic array stores elements in an underlying static array. When the array fills up ($\text{size} = \text{capacity}$), a new array of double the capacity is allocated, all elements are copied, and the old array is freed.

• append: write element at position size, then size++. If size == capacity before the write, resize first.
• Actual cost: $O(1)$ normally, $O(k)$ when copying $k$ elements during resize.

Aggregate Analysis

Starting from capacity 1, resizes occur at sizes $1, 2, 4, 8, \ldots, 2^{\lfloor \log n \rfloor}$. Total element copies over $n$ appends:

$\sum_{i=0}^{\lfloor \log n \rfloor} 2^i = 2^{\lfloor \log n \rfloor + 1} - 1 < 2n$

Plus $n$ writes for the appends themselves. Total cost: $< 3n$. Amortised per append: $< 3 = O(1)$.

Accounting Method

Charge $\hat{c} = 3$ per append:

• 1 unit pays for writing the element
• 2 units are stored as credit on the inserted element

When resizing from capacity $k$ to $2k$, the $k$ elements in the array have accumulated $2k$ total credit. Copying them costs $k$, consuming $k$ credits. The remaining $k$ credits are “lost” with the old array, but this is acceptable because elements in the new array will accumulate fresh credits.

Crucial insight: the credit on each element only needs to last until the next resize. At any point, at most half the elements (those in the first half of the array) need to have accumulated their 2 credits, because the resize only copies the first half’s worth of elements once. The inequality holds: total credit stored $\ge$ total copying cost over any sequence.

Potential Method

Define the potential function:

$\Phi = 2 \cdot \text{size} - \text{capacity}$

This is always non-negative (since $\text{capacity} \ge \text{size}$, and $\text{capacity} \le 2 \cdot \text{size}$ — the array doubles only when full, so capacity is at most twice the size at all times except right after a resize).

$\Phi(\text{empty}) = 0$ (size = 0, capacity = 1: $2 \cdot 0 - 1 = -1$ — this is not $\ge 0$!). Fix: start with capacity 0, or define $\Phi = \max(0, 2 \cdot \text{size} - \text{capacity})$. With capacity 0 initially, $\Phi = 0$.

Append without resize (size $s$, capacity $c$, $s < c$):

• Actual cost: $c = 1$ (one write)
• $\Delta\Phi = [2(s+1) - c] - [2s - c] = 2$
• $\hat{c} = 1 + 2 = 3$

Append with resize (size $s = c$, old capacity $k$, new capacity $2k$):

• Actual cost: $c = 1 + k$ (one write plus $k$ copies)
• Before: $\Phi_{\text{before}} = 2k - k = k$, After: $\Phi_{\text{after}} = 2(k+1) - 2k = 2$
• $\Delta\Phi = 2 - k$
• $\hat{c} = (k+1) + (2-k) = 3$

Amortised cost per append: $O(1)$ consistently.

Deletion and Shrinking

To maintain $O(1)$ amortised for both append and delete (pop), shrink the array when the load factor drops below $1/4$. When deleting causes $\text{size} < \text{capacity}/4$, halve the capacity. This prevents thrashing (alternating append/delete triggering resize every time).

Potential function for both operations: $\Phi = |2 \cdot \text{size} - \text{capacity}|$, or the textbook variant $\Phi = 2 \cdot \text{size} - \text{capacity}$ for append-heavy and a symmetric form for delete-heavy.

Summary

Method	Result	Key detail
Aggregate	$O(1)$ amortised	Sum of copies $< 2n$
Accounting	$O(1)$ amortised	Charge 3, store 2 credits per element
Potential	$O(1)$ amortised	$\Phi = 2 \cdot \text{size} - \text{capacity}$
Shrink threshold	$1/4$ load factor	Prevents thrashing

Past Tripos: y2024p1q9, y2023p2q7.