amortized analysis
Amortized analysis measures the average cost per operation across a whole sequence of operations, when an occasional expensive step is paid for by many cheap ones. The everyday image is a subscription. A magazine costs you a single yearly payment, but it feels like a small monthly cost because you spread — amortize — that one big charge over twelve months. Some operations in computing work the same way: now and then one of them does a lot of work, but if you average that burst over all the operations around it, the per-operation cost stays small and predictable.
The classic example is a dynamic array (like C++ std::vector). Adding an element to the end is usually O(1) — just drop it in the next slot. But occasionally the array is full, so it allocates a bigger block and copies everything over, an O(n) step. That sounds alarming, until you notice the doubling pattern: a copy of size n only happens after about n cheap appends since the last copy, so the copies, summed over a long run, add up to a total proportional to the number of appends. Spread out, each append costs O(1) amortized — a guarantee about the average, even though individual ones spike.
Why have a separate name for this? Because worst-case-per-operation can be misleadingly pessimistic. If you reported a vector's append as 'O(n) worst case' you would wrongly conclude that building a list of a million items is O(n^2); amortized analysis shows it is actually O(n) overall. Note the careful distinction from average-case analysis: average-case averages over random inputs and can fail on a bad one, while amortized cost is a guarantee over the sequence for any input. It is the honest way to price operations whose costs come in rare, payable bursts.
void push_back(int x) {
if (size == cap) { // rare: array is full
cap = (cap == 0) ? 1 : cap*2; // double the capacity
data = grow_and_copy(data, cap); // O(n) this time only
}
data[size++] = x; // usually O(1)
}Doubling on overflow makes most pushes O(1); the rare O(n) copy is paid for by the cheap ones before it.
Amortized (a guarantee over the whole sequence) is NOT the same as average-case (an average over random inputs). A dynamic-array append is O(1) amortized even though a single one can be O(n).