accounting method

A way to prove an amortised bound by charging each cheap operation a little extra "credit" that is saved to pay for later expensive ones.

In more detail

For a doubling array, charge two credits per append: one pays for the write and one is banked. When the array fills and k elements must be copied, k banked credits pay for the copy. Since the bank never goes negative, total cost is at most a constant times the number of appends.

Related terms

Taught in

References