Algorithms 101

Algorithm cost is not always the worst single call. A structure can have one expensive operation and still be cheap over a long run, and this page is the idea that measures that: amortized analysis, the average performance over time in the worst case.

The note starts by separating two familiar measures before adding the third. Amortization — Amortised analysis in a nutshell: worst-case vs average-case, and then where amortized is the average performance (over time) of each operation in the worst case.