Amortized Complexity

When one operation is occasionally expensive

Sometimes the cost of the same operation varies significantly from one call to another. Most calls are cheap, but occasionally more expensive work is required. Looking only at that rare expensive case can give an overly pessimistic view of the cost of a long sequence of operations.

Amortized analysis spreads rare expensive actions across many cheap ones. It answers the question: how much do we effectively pay per operation when many of them are performed in sequence?

Example with a resizable array

Imagine a simplified structure that stores elements in an internal array. While free space remains, an addition writes the new element into the next cell. But when the array is full, a larger array must be created and the old elements copied into it.

if (size == elements.length) {
    elements = Arrays.copyOf(elements, elements.length * 2);
}

elements[size++] = value;

A normal addition requires constant work. A resize is much more expensive because the elements accumulated so far must be copied. However, after the capacity doubles, there are many free cells again, so expensive copying does not happen on every addition.

Why this gives amortized O(1)

If the capacity doubles, resizes happen roughly at sizes 1, 2, 4, 8, 16, and so on. Across a sequence of n additions, the total number of copied elements remains on the order of n. If this work is spread across all n operations, the amortized cost of an addition is constant — O(1).

This does not mean that every addition runs in O(1). A particular resize operation can cost O(n), but such operations are rare enough for a long sequence of additions to remain linear overall.