Amortized analysis

From Wikipedia, the free encyclopedia

For other uses of the term "Amortization", see Amortization.

In 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 not involved; amortized analysis guarantees the time per operation over worst-case performance.

The method requires knowledge of which series of operations are possible. This is most commonly the case with data structures, which have state that persists between operations. The basic idea is that a worst case operation can alter the state in such a way that the worst case cannot occur again for a long time, thus "amortizing" its cost.

As a simple example, in a dynamic array, we double the size of the array each time it fills up. Because of this, rarely an insertion will require O(n) time (see big-O notation). However, a sequence of n insertions can always be done in O(n) time, so the amortized time per operation is O(n)/n = O(1).

Notice that average-case analysis and probabilistic analysis are not the same thing as amortized analysis. In average-case analysis, we are averaging over all possible inputs; in probabilistic analysis, we are averaging over all possible random choices; in amortized analysis, we are averaging over a sequence of operations. Amortized analysis assumes worst-case input and typically does not allow random choices.

There are several techniques used in amortized analysis:

• Aggregate analysis determines the upper bound T(n) on the total cost of a sequence of n operations, then calculates the average cost to be T(n)/n.

• Accounting method determines the individual cost of each operation, combining its immediate execution time and its influence on the running time of future operations. Usually, many short-running operations accumulate a "debt" of unfavorable state in small increments, while rare long-running operations decrease it drastically.

• Potential method is like the accounting method, but overcharges operations early to compensate for undercharges later.

[edit] Common Use

• In common usage, an "amortized algorithm" is one that an amortized analysis has shown to perform well.
• Online algorithms commonly use amortized analysis.

[edit] References

• Allan Borodin and Ran El-Yaniv (1998). Online Computation and Competitive Analysis. Cambridge University Press, 20,141. 
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 17: Amortized Analysis, pp.405–430.