Amortized Cost

Let c_i be the true cost of the ith operation.

Define $\hat{c}_i$ to be the amortized cost.

We insist that

$$c_i \le \hat{c}_i + \Phi(D_{i-1}) - \Phi(D_i).$$

The idea here is that analyzing the true costs will be too difficult, but the amortized costs will be easier to deal with.

The ``slack'' between the two costs is picked up by the potential function.