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.