Amortized Analysis & Dynamic Array Growth

Why Amortized Analysis?

Worst-case analysis is pessimistic by design. It describes the single most expensive operation. But when that expensive operation happens rarely — and cheap operations happen frequently — worst-case can paint a wildly misleading picture of real performance.

Dynamic Array Growth

A dynamic array (Python list, Java ArrayList, C++ std::vector) maintains a contiguous buffer. When the buffer fills up, it allocates a new buffer — typically 2× the current size — and copies all elements over.

                                timeline
                                    title Resize Events for 16 Appends (doubling strategy)
                                    Append 1 : capacity=1, size=1
                                    Append 2 : RESIZE to 2, copy 1 element
                                    Append 3 : RESIZE to 4, copy 2 elements
                                    Append 4 : size=4 (no resize)
                                    Append 5 : RESIZE to 8, copy 4 elements
                                    Append 9 : RESIZE to 16, copy 8 elements
                                    Append 17 : RESIZE to 32, copy 16 elements
                            

Looking only at the resize operations, it seems expensive. But between each resize, there are many cheap O(1) appends. The key observation: resizes happen at sizes 1, 2, 4, 8, 16, ... so they grow geometrically.

Method 1: Aggregate Method

The aggregate method asks: what is the total cost of all n operations? Divide by n to get the amortized cost per operation.

Visualising the Proof

Method 2: Accounting Method

The accounting method assigns each operation a amortized cost that may differ from its actual cost. Operations that are "cheap" pay in advance — depositing credits into a bank. Expensive operations draw from that bank.

Accounting Example: Dynamic Array

Assign amortized cost 3 to each append (even though most cost 1):

When a resize occurs at capacity k, we must copy k elements. Each of the k elements was inserted since the last resize, so each deposited 2 credits. Total credits available = 2k ≥ k (the cost of copying). The bank never goes negative. ✓

Since every append has amortized cost 3, total amortized cost for n appends = 3n = O(n). Amortized cost per append = 3/n × n / n = O(1).

Method 3: Potential Method

The potential method uses a potential function Φ that maps the data structure's state to a non-negative real number. The amortized cost of an operation is:

Potential Proof for Dynamic Array

Define Φ = 2 × (current_size − current_capacity / 2).

This potential is 0 when the array is half-full (right after a resize) and equals the capacity when the array is completely full (just before the next resize).

Both cases give amortized cost 3. Total amortized cost = 3n = O(n). Per operation: O(1) amortized.

Growth Factor Tradeoffs: 2× vs 1.5× vs φ

The doubling factor is a design choice. Different languages make different tradeoffs:

Real-World Growth Implementations

import sys

# Observe CPython list growth
lst = []
prev_size = sys.getsizeof(lst)
print(f"n=0  : {prev_size} bytes")

for i in range(1, 33):
    lst.append(i)
    new_size = sys.getsizeof(lst)
    if new_size != prev_size:
        print(f"n={i:<3}: {new_size} bytes  (resize at n={i})")
        prev_size = new_size

# Manual dynamic array with configurable growth factor
class DynamicArray:
    def __init__(self, growth_factor=2.0):
        self._data = [None]
        self._size = 0
        self._capacity = 1
        self._growth = growth_factor
        self._resize_count = 0
        self._total_copies = 0

    def append(self, val):
        if self._size == self._capacity:
            new_cap = max(int(self._capacity * self._growth), self._capacity + 1)
            new_data = [None] * new_cap
            for i in range(self._size):
                new_data[i] = self._data[i]
            self._data = new_data
            self._total_copies += self._size
            self._resize_count += 1
            self._capacity = new_cap
        self._data[self._size] = val
        self._size += 1

    def stats(self):
        print(f"n={self._size}, capacity={self._capacity}")
        print(f"Resizes: {self._resize_count}, Total copies: {self._total_copies}")
        print(f"Copies per append: {self._total_copies / max(1, self._size):.2f}")

# Compare growth factors
for gf in [2.0, 1.5, 1.25]:
    arr = DynamicArray(growth_factor=gf)
    for i in range(1000):
        arr.append(i)
    print(f"\nGrowth factor {gf}:")
    arr.stats()

Other Amortized Structures

Interview & Practice