Amortised Analysis

Expensive sometimes, cheap on average

Some operations are usually cheap but occasionally expensive. Amortised analysis bounds the average cost per operation over any sequence of operations, which is a worst-case guarantee for the sequence, not an average over random inputs. The classic example is the dynamic array. Appending is O(1) until the array is full; then it allocates double the capacity and copies all elements, costing O(k) for k elements. Over n appends starting from capacity 1, the copies cost 1 + 2 + 4 + … + n/2 < n element moves in total, plus n writes for the appends themselves, so the total is less than 2n, which is amortised O(1) per append. Three techniques exist: the aggregate method (total cost ÷ number of operations), the accounting method (charge each cheap operation a little extra "credit" that pays for future expensive ones) and the potential method (a function of the data structure's state stores prepaid work). Other examples include hash table resizing, union-find with path compression and two-stack queues.

Rare spikes, low average

Most appends cost one step; occasional resizes cost more, but the average stays constant.

Counting the work of n appends with doubling

Total copies stay below n, so the average per append is constant.

def total_append_work(n):
    capacity, size, work = 1, 0, 0
    for _ in range(n):
        if size == capacity:
            work += size          # copy every existing element to the new array
            capacity *= 2
        work += 1                 # write the new element
        size += 1
    return work

# for n = 1024: copies = 1 + 2 + 4 + ... + 512 = 1023, writes = 1024
# total = 2047 < 2n  ->  amortised O(1) per append
# growing by a constant amount (e.g. +10) instead of doubling gives O(n^2) total

Growth must be geometric

If an array grows by a fixed number of slots each time, the copies add up to O(n²) for n appends. The amortised O(1) guarantee depends on multiplying capacity, by 2 or by another factor greater than 1.

Quick check: Why is appending to a doubling dynamic array amortised O(1) even though some appends cost O(n)?

• The total copying cost over n appends is less than about n, so the average per append is constant
• Resizes never happen
• Copying is free in modern hardware
• Amortised means best case