Amortized AnalysisAmortised analysis

01Why it exists

Reach for it when you see:Occasionally slow but usually fast, growing a buffer, rehashing, each element handled at most once, total cost divided by the number of operations.

02The core idea

Worst-case analysis asks how slow a single operation can be. Amortised analysis asks what a whole run of operations costs in total, then spreads that across each one. Both are exact guarantees rather than probabilistic averages: amortised O(1) means that any n operations are guaranteed to cost at most c·n in total.

The dynamic array is the standard example. Under a doubling policy, pushes number 1, 2, 4, 8, ..., 2ᵏ trigger a move, copying 1, 2, 4, ..., 2ᵏ⁻¹ elements respectively, and that sum is less than n. Add the n insertions themselves and the total is under 3n, so each push averages fewer than 3 operations. Change the policy to adding a fixed 100 slots each time and the total copying climbs to the order of n²/200, which makes the amortised cost O(n).

There are two standard ways to argue it. The aggregate method adds up the cost of n operations and divides by n. The accounting method has each cheap operation pay a little extra into savings, which the expensive operations then spend. A dynamic array push pays 3 coins: one to store itself, one saved towards moving itself later, and one towards moving an element from the older half — and the account never goes overdrawn.

03The algorithm

1. 1Identify the expensive operation and what triggers it: the buffer filling up, the output stack running empty, the load factor crossing a threshold.
2. 2Work out how often it happens and what each occurrence costs in terms of n. Under a doubling strategy it happens log n times, and the kth one costs 2ᵏ.
3. 3Use the aggregate method to add up the cost of all n operations: n cheap ones plus a handful of expensive ones gives you the total.
4. 4Divide the total by n and you have the amortised cost. For a more intuitive account, switch to the accounting method: how much each cheap operation has to prepay to cover the expensive ones later.
5. 5Check that nothing gets refunded: amortised analysis assumes the sequence starts from an empty structure, so if pops and pushes alternate, make sure the shrinking policy does not make the cost blow up over and over (which is why a buffer usually only shrinks once it is a quarter full).

04Interactive demo

Press push and watch: most of the time the cost is 1, and when the capacity fills up a tall yellow bar appears — but the "average per push" line never rises above 3.

05Code

The Python version hand-writes a dynamic array and counts the elements it moves; the C++ version simply watches std::vector's capacity change.

class DynamicArray:
    """A hand-written list, so you can watch when the growth happens."""

    def __init__(self):
        self.capacity = 1
        self.size = 0
        self.data = [None] * self.capacity
        self.copies = 0            # total number of elements moved

    def push(self, x):
        if self.size == self.capacity:
            self._grow()           # occasionally expensive: O(n)
        self.data[self.size] = x   # usually cheap: O(1)
        self.size += 1

    def _grow(self):
        new_capacity = self.capacity * 2      # the key: double it, do not add a fixed amount
        new_data = [None] * new_capacity
        for i in range(self.size):
            new_data[i] = self.data[i]
            self.copies += 1
        self.data = new_data
        self.capacity = new_capacity


arr = DynamicArray()
for i in range(1_000_000):
    arr.push(i)
print(arr.copies)      # about 1,000,000, nowhere near n²
# Total cost ≈ n insertions + fewer than n moves < 3n, so under 3 per push → O(1) amortised

06Practice

• LeetCode 232Implement Queue using Stacks (amortised O(1))Easy
• LeetCode 155Min StackMedium
• LeetCode 705Design HashSet (think about when to grow)Easy
• LeetCode 146LRU CacheMedium