Amortized analysis
In computational complexity theory, amortized analysis is the time per operation averaged over a worst-case sequence of operations. Amortized analysis differs from average-case performance in that probability is not involved; amortized analysis guarantees the time per operation over worst-case performance.
There are several techniques used in amortized analysis:
- Aggregate analysis - determines upper bound T(n) on total cost of sequence of n operations, then calculates average cost to be T(n)/n
- Accounting method - determines the individual cost of each operation.
- Potential method - like accounting method, but the method overcharges operations early to compensate for undercharges later.
