Aggregate Analysis | Algorithms II

Aggregate analysis is the simplest amortised analysis technique: compute the total cost of a sequence of $n$ operations and divide by $n$ . If some operations are cheap and others expensive, the average may be far lower than the per-operation worst-case bound.

Amortised vs. Worst-Case vs. Average-Case

Worst-case: maximum cost of a single operation over all possible inputs. Pessimistic.
Average-case: expected cost of a single operation, assuming a probability distribution over inputs. Requires assumptions about input distribution.
Amortised: the average cost per operation over a worst-case sequence of operations. Guarantees the total cost of any sequence, not probabilistic.

Amortised analysis is essential when a data structure occasionally does expensive work (resizing, rebalancing, cleanup) that is paid for by many cheap operations.

The Binary Counter

A $k$ -bit binary counter increments from $0$ to $2^k - 1$ . The counter is an array of bits $A[0..k-1]$ , with $A[0]$ the least significant bit.

INCREMENT(A):
    i = 0
    while i < k and A[i] == 1:
        A[i] = 0
        i = i + 1
    if i < k:
        A[i] = 1

A single INCREMENT may flip up to $k$ bits (e.g. $0111 \to 1000$ flips 4 bits). Worst-case cost: $\Theta(k)$ . Starting at 0 and performing $n$ increments, the total number of bit flips is:

$\sum_{i=0}^{k-1} \left\lfloor \frac{n}{2^i} \right\rfloor < n \sum_{i=0}^{\infty} \frac{1}{2^i} = 2n$

Bit $i$ flips every $2^i$ increments. Over $n$ increments, the number of flips of bit $i$ is $\lfloor n / 2^i \rfloor$ .

Total flips $< 2n$ . Amortised cost per INCREMENT: $2n / n = 2 = O(1)$ .

Even though a single INCREMENT may cost $\Theta(k)$ , over many operations the average is constant.

The Dynamic Array (Vector)

A dynamic array grows by doubling its capacity when full. Starting from capacity 1:

Insert #	Capacity	Copies	Notes
1	1	0
2	2	1	Resize 1→2, copy 1 element
3	4	2	Resize 2→4, copy 2 elements
4	4	0
5	8	4	Resize 4→8, copy 4 elements
…	…	…
$n$

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

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

Each copy costs $O(1)$ , so total copying cost is $O(n)$ . Adding the $O(1)$ per-insert cost for the $n$ inserts gives total $O(n)$ . Amortised per insert: $O(1)$ .

This proves a result assumed in Part IA Algorithms I (the stack ADT): push is $O(1)$ amortised.

General Pattern

Aggregate analysis works well when the expensive operations occur at predictable, sparse intervals (powers of 2, Fibonacci numbers, etc.). Sum the geometric or arithmetic series, bound the total, divide by $n$ .

Limitations: the aggregate method gives a single amortised cost per operation averaged across all operation types. It cannot assign different amortised costs to different operations (accounting and potential methods can). For data structures with multiple operation types, the accounting and potential methods are more flexible.

Summary

Method	Approach	When to use
Aggregate	Total cost $/ n$	Simple operations, single type
Accounting	Assign charges, track credit	Multiple op types, credit attribution
Potential	$\Phi$ function on data structure state	Complex interactions, formal proofs

Past Tripos: y2024p1q9, y2023p2q7.