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:

1. Aggregate analysis - determines upper bound T(n) on total cost of sequence of n operations, then calculates average cost to be T(n)/n
2. Accounting method - determines the individual cost of each operation.
3. Potential method - like Accounting method, but the method overcharges operations early to compensate for undercharges later.