= 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 $\widehat c_i$, and leaves balance $B_i$, then
$$
B_i=B_{i-1}+\widehat c_i-c_i,\qquad
\sum_{i=1}^n c_i=\sum_{i=1}^n\widehat c_i-B_n\leq\sum_{i=1}^n\widehat c_i.
$$
Thus \b[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.
Back to article page
