Amortized Analysis

In an amortized analysis, the time required to perform a sequence of data structure operations is average over all operation performed. Amortized analysis can be used to show that average cost of an operation is small, if one average over a sequence of operations, even though a single operation might be expensive. Unlike the average probability distribution function, the amortized analysis guarantees the 'average' performance of each operation in the worst case.

CLR covers the three most common techniques used in amortized analysis. The main difference is the way the cost is assign.

  1. Aggregate Method
  2. Accounting Method
  3. Potential Method