Amortized analysis is an analysis technique that provides tight bounds on the worst-case running time of an algorithm that involves a sequence of possibly different operations. For example, suppose an algorithm used operations A, B, and C and applied...

In computer science, especially analysis of algorithms, amortized analysis refers to finding the average running time per operation over a worst-case sequence of operations. Amortized analysis differs from average-case performance in that probability is...