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.