amortized cost

Imagine a gym membership that costs 360 dollars a year. On the day you pay, that one visit feels enormously expensive; on all the other days your visits feel free. But if you spread the 360 dollars across the 120 visits you actually make, each visit costs you 3 dollars. Amortized cost is that spreading-out idea applied to algorithms: instead of asking how expensive the single worst operation can be, we ask how much each operation costs on average when you charge the whole bill across a long sequence of operations.

Precisely: take any sequence of m operations on a data structure, starting from an empty or fixed initial state, and let T(m) be the total actual work for the whole sequence. The amortized cost per operation is just T(m) divided by m — the true total divided by the number of operations. We then look for a bound that holds for EVERY sequence, no matter which adversary chooses the operations. This is still a worst-case guarantee, but it is worst case over whole sequences, not over single operations. For example, appending n items to a dynamic array does at most O(n) total work even though occasional appends copy the whole array, so the amortized cost of one append is O(n)/n = O(1).

Amortized cost matters because many data structures have rare expensive operations that pay for many cheap ones — and counting each operation by its own worst case wildly overstates the real running time of a program. The crucial honesty: amortized O(1) does NOT mean every operation is cheap. One single append can still cost O(n) when it triggers a resize; the claim is only that such spikes are rare enough that the average over the sequence stays O(1). If your application cannot tolerate even one slow operation (say, a real-time system), amortized bounds may not be what you need.