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
- amortised analysis — Measuring the average cost per operation over a long sequence of operations, so rare expensive steps are spread across many cheap ones.
- dynamic array — An array that grows on demand by allocating a larger block and copying the existing items across when it runs out of room.
Taught in
- Amortised Analysis: Why Append Is Cheap — Algorithms & Data Structures for Working Engineers