# Amortization/Accounting Method

### From charlesreid1

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*.

# Flags

AlgorithmsSeries on Algorithms
Algorithms/Sort Three solid O(n log n) search algorithms: Merge Sort Algorithm Analysis/Merge Sort
Algorithms/Search
Algorithms/Combinatorics
Algorithms/Strings
Algorithm complexity Amortization Algorithm Analysis/Matrix Multiplication
Estimation
Project Euler
· Template:AlgorithmsFlag · e |