## 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.

**Aggregate
Method **
- Computes an upper bound T(n) on the total
cost of a sequence of n operations.

**Accounting
Method **
- Overcharge some operations early in the
sequence. This 'overcharge' is used later in the sequence for pay
operation that charges less
than they actually cost.

**Potential
Method**
- Maintain the credit as the potential energy
to pay for future operations.