 Solution

The accounting method assigns each operation a charge, its amortized cost, that can differ from its actual cost. Cheap operations save the excess charge as credits associated with the data structure or its entries. An expensive operation spends these previously saved credits. The essential invariant is that the credit balance never becomes negative.

If the initial balance is zero, operation $i$ has actual cost $c_i$, charge ${\hat{c}}_i$, and leaves balance $B_i$, thenThus a nonnegative credit balance makes the total charge an upper bound on the total actual cost for every operation sequence. In particular, a constant time charge proves a linear time total. The argument is a deterministic amortized analysis; it requires no probability distribution on the operations. A nonzero initial balance must be included as an additive term in the bound.