Amortized Analysis
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 them n times to a given data structure to transform it into a new data structure. For each of the n-applications, the algorithm chooses A, or B, or C. Further suppose that A and B run in constant time, O(1), whereas C is linear, or O(k), where k is some measure of the size of the data structure. A naive analysis of the running time of this algorithm would have to conclude that the running time is O(k*n) since in the worst possible scenario the algorithm would apply a O(k) operation n separate times. However, for many reasons, such a bound would not be tight, because given the workings of the total algorithm it may not make sense, or may not even be possible to apply operation B to the data structure all the time on any given run of the total algorithmic sequence. Amortized analysis provides a body of techniques to improve this naive worst-case analysis.
For the sake of illustration, consider a toy example, taken from Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein. Imagine a stack with three operations, PUSH, POP, and MULTIPOP(k). PUSH and POP are the usual stack operations that add and remove 1 object from the top of the stack. MULTIPOP(k) removes k objects from the top of the stack, or removes all objects if the stack has less than k elements. While PUSH and POP are O(1), MULTIPOP(k) is O(k). Now imagine an algorithm that involves a sequence of n PUSH, POP, and MULTIPOP operations. Naive worst-case analysis shows that this algorithm will run in O(n2) time because in the worst case a MULTIPOP is O(n) and we could run MULTIPOP every time. But in this toy example it is clear that this scenario is impossible and that an aggregate analysis shows that the whole sequence can run in at most O(n).
The accounting method of amortized analysis is able to recover this O(n) run time. In general the accounting method assigns an amortized cost to each possible operation to choose from in a sequence. Some operations may have an amortized cost that is actually greater than its actual cost, or running time. When these operations are run, the difference between the extra amortized cost and actual cost are stored as credits that are associated with elements of the data structure being operated on. Later when other operations whose actual cost exceeds their assigned amortized cost operate on the data structure, they use up the credits to make up the difference. In some sense the "rich" operations with large amortized cost but low actual cost can "pay in advance" for poorer operations that have low amortized cost but high actual cost. The advanced pay is stored as credits associated to the data structure.
The above considerations may seem a bit abstract so lets return to the stack example. We can implement the accounting method by assigning the following amortized costs to the three operations: PUSH gets a cost of 2, whereas POP and MULTIPOP(k) both get costs of zero. Recall that the actual costs put PUSH and POP at 1 and MULTIPOP(k) at k. Thus we see that PUSH is "rich" whereas POP and especially MULTIPOP are poor. Now every time PUSH puts an element on the stack, it uses half its amortized cost of 2 to pay for its actual cost 1 and so has an amortized cost of 1 left over. This credit of 1 is tagged on to the element pushed onto the array. Now suppose POP has to act on the array. It doesn't have enough amortized cost to pay for its actual cost of 1, but instead it borrows the credit of 1 given to the top element of the stack by the PUSH operation that put it there. In essence the rich PUSH operation has already payed for the poor POP operation. Similarly MULTIPOP(k) borrows k amortized credits from the k elements it pops off. The point of using all this amortized cost is that the total actual cost incurred by all the operations in sequence is actually equal to or less than the amortized cost incurred by all the operations. And since there are n PUSH's, and PUSH's are the only operations with amortized cost, we can see that the total run time is proportional to 2*n, or O(n). Thus amortized analysis through this bookkeeping method correctly accounts for the actual cost of a sequence of operations and provides a much tighter bound than the worst case O(n2) analysis.
This is the complete article, containing 798 words
(approx. 3 pages at 300 words per page).
