Amortized Analysis

Task: Watch what eight insertions really cost

def append(value):    if size == capacity:        capacity = capacity * 2        bigger = [0] * capacity         for i in range(size):            bigger[i] = data[i]         data = bigger     data[size] = value    size = size + 1

What you are watching

Eight values inserted one at a time into a dynamic array whose capacity starts at one and doubles whenever it is full. Most insertions simply drop the value into a spare slot and cost one unit of work. Three of them, at insertions two, three and five, find the array full and must allocate a larger buffer and copy everything already there, costing two, three and five units. A bar under each insertion shows its cost, so the three spikes are visible and so is the fact that they get further apart as the array grows. The total is fifteen units for eight insertions, and the running average never rises above two and a half, which is what it means to say insertion is O(1) amortized even though a single insertion can be O(n).