Amortized analysis

In theoretical computer science, the amortized running time analysis looks at the average cost of operations in consequences. In contrast to the general term analysis, not only the maximum costs of the individual steps are considered, but it is the worst case analysis of all operations in a number of passes of the algorithm. This can - for example with Fibonacci heaps - lead to a better upper bound, since there are often operations that can be expensive, but this "expensive" case occurs only in one or a few sequences of the algorithm, and all other cases are relatively low. So ultimate goal is the "average" upper bound in the worst case to determine, and the upper bound, which applies in the most unfavorable case possible throughput in the worst - and may be higher - of which, however, remains unaffected.

In a general runtime analysis one must assume from the most expensive case, since this can not be excluded altogether, but if the case is rare, so that the calculated transit time with multiple passes is worse than the actual assumable.

The amortized running time analysis, there are basically three different methods:

• The aggregate method
• (also known as bank account paradigm ) the Account Method
• The potential function method