Why does total amortized cost need to be an upper bound on total actual cost?

Question

This may seem like a basic question, but I'm having trouble understanding why, when using the accounting method of amortized analysis, the total amortized cost must be an upper bound on the total actual cost.

Why does total amortized cost need to be an upper bound on total actual cost?

I found the following passage in CLRS but I'm not completely sure what they mean: "If you want to use amortized costs to show that in the worst case the average cost per operation is small, you must ensure that the total amortized cost of a sequence of operations provides an upper bound on the total actual cost of the sequence.". My understanding is that the condition prevents us from underestimating the average cost...

Answer 1

The cause of your confusion is that you're asking how to prove something false.

In general total actual cost may exceed total amortized cost. Here is an example. Suppose I want to append to a list. The amortized cost is O(1) - the cost of a resizing can be spread across the O(n) appends between resizings to get an amortized average cost of O(1). But the actual cost can be O(n) if there is a resizing!

And this explains the CLRS comment. Actual costs are not always bounded by amortized. So if you want to use amortized costs to bound actual, then you have to show that they are actually an upper bound. If, for instance, you build a list by appends, then amortized is an upper bound. If you append to an existing list, then it isn't. This is something you have to work out on a case by case basis.