Chris Okasaki

“Amortization allows for occasional operations to have actual costs that exceed their amortized costs. Such operations are called expensive. Operations whose actual costs are less than their amortized costs are called cheap. Expensive operations decrease the accumulated savings and cheap operations increase it. The key to proving amortized bounds is to show that expensive operations occur only when the accumulated savings are sufficient to cover the remaining cost.”
― Chris Okasaki, Purely Functional Data Structures

“The notion of amortization arises from the following observation. Given a sequence of operations, we may wish to know the running time of the entire sequence, but not care about the running time of any individual operation. For instance, given a sequence of n operations, we may wish to bound the total running time of the sequence by O(n) without insisting that every individual operation run in O(1) time. We might be satisfied if a few operations run in O(log n) or even O(n) time, provided the total cost of the sequence is only O(n). This freedom opens up a wide design space of possible solutions, and often yields new solutions that are simpler and faster than worst-case solutions with equivalent bounds.”
― Chris Okasaki, Purely Functional Data Structures