Amortized methods

Aggregate analysis bounds the total cost T(n) of any sequence of n operations and divides by n. For a dynamic array that doubles when full, the copies cost 1 + 2 + 4 + … < 2n over n appends, plus n writes, so T(n) < 3n and each append is amortised O(1) (at most 3).

It treats all operations alike, so it is the simplest method.

The accounting method charges each operation an amortised price that may exceed its real cost; the surplus is stored as credits on specific elements and pays for later expensive steps. For a doubling array, charge 3 per append: 1 pays for the write, 2 are saved on the new element. When the array doubles, the elements added since the last doubling carry enough credits to pay for copying all of them and half of the old ones.

The balance of credits must never go negative.

The potential method defines a function Φ of the data structure's state, and amortised cost = actual cost + Φ(after) - Φ(before). With Φ ≥ 0 and Φ(start) = 0, the total amortised cost is an upper bound on the total real cost. For a doubling array use Φ = 2 · size - capacity.

The same potential is used in the animation of the multipop stack, with Φ = number of items on the stack.

1void push(int x) { stack.push(x); }                     // actual cost 1
2void multipop(int k) {
3    while (k-- > 0 && !stack.isEmpty()) stack.pop();   // actual cost = number popped
4}
5// potential Φ = number of items on the stack (always >= 0)
6// amortised cost = actual cost + ΔΦ:  push: 1 + 1 = 2;  multipop: m + (-m) = 0

A dynamic array doubles its capacity when full: allocate 2× the space and copy every element. A single append can cost O(n), but the next n appends cost O(1), so the average is constant. Growing by a fixed amount (for example +10) instead gives O(n) per append on average, O(n²) in total.

Compare the growth policies and watch the total copy cost in the animation.

1int[] data = new int[1]; int size = 0; long copies = 0;
2for (int i = 0; i < 1000; i++) {
3    if (size == data.length) { data = Arrays.copyOf(data, size * 2); copies += size; }
4    data[size++] = i;
5}
6// copies < 2 * 1000: total work < 3n

1void add(int x) {
2    if (size == data.length) {                          // full: allocate a bigger array
3        data = Arrays.copyOf(data, newCapacity(data.length));   // copies `size` elements
4    }
5    data[size++] = x;                                   // the cheap part: 1 write
6}
7// doubling: newCapacity = 2 * capacity;  grow-by-1: capacity + 1;  Java ArrayList: capacity + capacity / 2

A stack with push, pop and multipop(k) (pop up to k items) looks like it could cost O(n) per multipop, so n operations would cost O(n²). But each item can be popped at most once after it was pushed, so the total pops over n operations are at most n. Hence every operation is amortised O(1).

Run the sequence and watch the potential (the stack size) pay for each large multipop.

1static int multipop(Deque<Integer> stack, int k) {
2    int popped = 0;
3    while (!stack.isEmpty() && popped < k) { stack.pop(); popped++; }
4    return popped;   // cost = popped; total over all calls <= total pushes
5}

1void push(int x) { stack.push(x); }                     // actual cost 1
2void multipop(int k) {
3    while (k-- > 0 && !stack.isEmpty()) stack.pop();   // actual cost = number popped
4}
5// potential Φ = number of items on the stack (always >= 0)
6// amortised cost = actual cost + ΔΦ:  push: 1 + 1 = 2;  multipop: m + (-m) = 0

Union-find keeps disjoint sets as trees. With union by rank and path compression, any sequence of m operations on n elements costs O(m · α(n)), where α is the inverse Ackermann function and is at most 4 for any input that fits in the universe. That is amortised, nearly constant time per operation.

Individual find calls can still be slow; the guarantee covers the whole sequence. The full structure is covered in the graph chapters.

1static int find(int[] parent, int x) {
2    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }   // path halving
3    return x;
4}