Amortization/Accounting Method

The accounting method is a way of amortizing operations that performs an accounting or balancing method over the time utilized for different operations.

The canonical example is insertions and deletions. When we insert an item into a sorted structure, we pay log(N) cost to insert that item, and therefore pay log(N) cost when we insert it. The accounting method then allows us to account for that cost, adding a "log(N)" coin to our bank account. Then when we remove the item, we have already spent the log(N) cost to insert it, and we can spend that "log(N)" coin to remove the item without an amortized cost.

The challenge here is, N is changing as the structure grows. So we need to do a little bookkeeping, but we can show that when we add an item with log(N*) cost, where N* is the actual cost at the time of insertion, we can spend that coin when we remove an item from the data structure when it has that size N*.