Menu

Class 40: Introduction to Amortized Analysis & the Multipop Stack


Reading
Section 17.2 of Introduction to Algorithms.

Homework
None.

Data Structures and Algorithms
We have "data structures" courses and "algorithms" courses, which makes it seems like these are separate topics. In fact, they are the same thing. The data structures you use are a crucial part of designing algorithms and, in turn, operations on a data structure are algorithms. When we talk about data structures, we usually analyze the best, worst and average case running times of each operation in isolation - i.e. with no assumptions about previous or subsequent operations on that data structure. When we use data structures, however, we usually perform a long sequence of operations and are always asking ourselves questions like "can I really have n consecutive worst case calls to remove-min?" The next topic, "Amortized Analysis", is all about measuring the cost of sequences of operations on a data structure, as opposed to the cost of a single operation.

Amortization
Suppose you pay $1000 a month in rent, $300 every six months in car insurance, and about $120 a month for food & gas. Assuming these bills are paid at the end of the month, half-year and week respectively, how much would you have to put away in the bank each day to be sure that there'd be enough to cover your bills when they come due? How would you answer that questions? Would you say "Some days, when things line up all wrong, I spend $1420, so I'd better put $1420 in the bank every day"? No! You'd do something like add up your costs for the whole year and divide by 365: If you put (12*1000 + 2*300 + 52*120)/365 = $51.62 in the bank every day, you'd have enough to pay your bills whenever they came due. In the above analysis, we've "amortized" these expenses. Amortization means spreading out a lump-sum payment evenly over the whole period that payment buys you services for. We're going to use the same idea to analyze algorithms.

Multipop Stacks
Consider an augmented stack data structure called a multipop stack, which allows the usual push and pop, plus a new operation called multipop. The multipop operation takes an integer k, and pops off the top k objects on the stack --- stopping when the stack is empty, if it happens that there are fewer than k objects on the stack. The implementation of a multipop stack should be obvious. Suppose I go through a sequence of n operations on a multipop stack. In the worst case, what is the average cost per operation?

The traditional analysis Thus far, when we've analyzed algorithms it's been one operation at a time. So let's consider a single operation in the sequence of n operations. Obviously, the worst case is that we've done n-1 pushes, and then the last thing we do is multipop(n-1). This single operation will then take Θ(n) time. So, we have a series of n operations with O(n) cost, for a total time requirement of O(n^2). Hopefully you rebel at this, saying "Yes, it is O(n^2), but it can't really take that long! You can't have an expensive multipop operation without a whole bunch of inexpensive pushes coming first!"

Amortized analysis Amortized analysis is a bit different. It examines the worst case average cost of an operation in a sequence of n operations. Thus, instead of analyzing each operation in isolation, it analyzes operations in the context of a sequence of operations. This sometimes allows us to get a better idea of the true complexity of a task. In the multipop case we'll analyze the total cost of a sequence of n operations, and then take the average over all n operations to arrive at our amortized time per operation. Obviously, each object on the multistack gets pushed exactly once, and popped no more than once. So we have at most two "steps" for each object that finds its way onto the stack. In a sequence of n operations, clearly at most n objects get pushed onto the stack. Thus, we have at most 2*n "steps" in a sequence of n operations, i.e. n operations take Θ(n) time. Thus, on the average, each operation takes Θ(n)/n = Θ(1) in the worst case! Using amortized analysis we see that multipop operations take constant time ... in the amortized sense.

The Accounting Method
Using the accounting method, we think it terms of "paying" for operations using "computational units". As long as each computational unit corresponds to Θ(1) actual work, the running time of our algorithm will grow like the number of "computational units" we need in order to pay for all the operations we perform.

So, the amount we pay for each operation is fixed, and it is the amortized cost of the operation. The number of computational units actually required for a particular instance of that operation being performed is the actual cost of the operation. For example, the amortized cost of a multipop(k) operation on a stack of n elements is constant (remember last class?), whereas the actual cost varies depending on the values of k and n.

The trick with the accounting method is to fix an amortized cost for each operation, and show that the actual cost of a sequence of M operations does not exceed M times the amortized cost. You overpay for the operations with very small actual cost, and the credit you build up pays for the occasional operation with large actual cost.

Analyzing Multipop Stacks with the Accounting Method
In the following, "CU" will stand for "Computation Unit", the "currency" of our computation finances.
Operation       Actual Cost      Amortized Cost
-----------------------------------------------
push             1 CU               2 CU
pop              1 CU               0 CU
multipop(k)      min(k,s)  ______   0 CU
                       \__| size |
                          | of   |
                          | Stack|
                           ------


We want to prove that the "balance" B in our computational account 
is always greater than or equal to zero, since this means out
amortized payments always suffice to cover our actual costs.  We will
do this by proving that B >= S after every operation, where B is the
balance and S is the size of the stack.

1)  Initially both B and S are 0, so B >= S is true

2)  Assume B >= S and we perform an operation resulting in new balance 
    B' and new stack size S'.  We'll show that regardless of which
    operation is performed, B' >= S'

    operation is a push so S' = S + 1
    ------------------ 
              B >= S
      B + 2 - 1 >= S + 2 - 1
          B + 1 >= S + 1
             B' >= S'

    operation is a pop so S' = S - 1
    ------------------
              B >= S
      B + 0 - 1 >= S + 0 - 1
          B - 1 >= S - 1
             B' >= S'

    operation is a mulitpop(k) so S' = S - min(k,S)
    ------------------
                   B >= S
    B + 0 - min(k,S) >= S + 0 - min(k,S)
        B - min(k,S) >= S - min(k,S)
                  B' >= S'
	    
Where would anyone use a multipop stack?
Take a look at this simple program: parse. It basically just analyzes the tag structure in an html-like tag language ... so the content in between the tags is left out, it just looks at tags. For example:
> ./parse
<html>
<head> <title> </title>
<body>
<img>
<b> <a> </a> </b>
<p>
<hr>
</p>
</body>
</html>
6 matched and 3 unmatched tags
	
Assuming the maximum tag length is a small constant, let's analyse the algorithm in terms of n, the number of tags in the input. Essentially, the running time is dominated by the outer while loop, which loops over each tag, and its body, in which we either push, or loop through a bunch of pops.


Christopher W Brown
Last modified: Mon Apr 17 16:25:02 EDT 2006