15-451 Algorithms 09/16/03 * Amortized analysis mini2 due tonight quiz1 next week ---------------------------------------------------------------------------- So far we have been looking at static problems where you are given an input and the goal is to produce an output with some desired property. For next few lectures, we're going to turn to problems where have a *series* of operations, and goal is to analyze time per operation. E.g., binary search trees, hash tables. Today, talk about a useful kind of analysis, called *amortized analysis* for problems of this sort. Before getting to what this is, motivate with an example. Example #1: implementing a stack as an array -------------------------------------------- Say we want to use an array to implement a stack. We have an array A, with a variable "top" that points to top of stack (so A[top] is the next free cell). -> to do push(x), just need to do A[top] = x; top++; -> to do x=pop(), just need to do top--; x = A[top]; (and first check to see if top==0 of course...) What if the array is full and we need to push a new element on? In that case we can allocate a new larger array, copy the old one over, and then go on from there. This is going to be an expensive operation, so a push that requires us to do this is going to cost a lot. But maybe we can "amortize" the cost over the previous cheap operations that got us to this point. So, on average over the sequence of operations, we're not paying too much. DEFINITION: Amortized cost of n operations is the total cost divided by n. Say our cost model is: push costs 1, pop costs 1, and the cost of resizing the array is the number of elements moved. Q: What if when we resize we just increase the size by 1. Is that a good idea? How much could pushing n elements cost? How much is this on average per operation? Q: What if we decide to double the size of the array? Can analyze like this: if we do n operations, the total cost for pushes and pops is O(n). Total cost for doubling is at worst n + n/2 + n/4 + .... = O(n). So, amortized cost per operation is O(1). Another way of analyzing it: say that every time we perform a push operation, we pay $1 to perform it, and we put $2 into a piggy bank. Any time we need to double the array, from size L to 2L, we must have $L in the piggy bank [why?]. So, we can use the money in the piggy bank to pay the $L that it costs to resize the array. This last one is a really useful way of analyzing problems like this. The "piggy bank" is often called a "potential function", since it's like potential energy that you can use later. The potential function is the amount of money in the bank. In this case, it's 2*(number of elements in the array after the midpoint). Amortized cost = actual cost + change in potential. In the "piggy bank" view, the amortized cost is the out-of-pocket cost per operation. =========================================================================== Motivation of amortized analysis is that a worst-case-per-operation analysis can give overly pessimistic bound if the only way of having an expensive operation is to have a lot of cheap ones before it. NOTE: this is DIFFERENT from our usual notion of "average case analysis" -- we're not making any assumptions about inputs being chosen at random -- we're just averaging over time. ============================================================================== Continuing with the array: what if we don't want to be space hogs. If we do a lot of pops and the stack gets small, then we want to resize the array to make it smaller. Say k = number of elements and L = size of array. Is this a good policy: when pop from k = L/2, then cut the array size in half? Why or why not?? How about cutting in half when pop from k=L/4? Claim: amortized cost is at most 3 per operation. Proof: Consider the interval between successive array resizes. The important point is that after each resize operation, the array is exactly half full. If it's a double, then there must have been at least L/2 pushes since the last resize. This can pay for work. If it's a halving, then there must have been at least L/4 pops, and these can be used to pay for the resize. ============================================================================== Another example: a binary counter --------------------------------- Say we want to store a big binary counter in an array A. All entries start at 0. Cost model: when we increment counter, we pay $1 for every bit we need to flip. A[m] A[m-1] ...... A[3] A[2] A[1] A[0] cost ---------------------------------------- ---- 0 0 0 0 0 0 $1 0 0 0 0 0 1 $2 0 0 0 0 1 0 $1 0 0 0 0 1 1 $3 0 0 0 1 0 0 $1 0 0 0 1 0 1 $2 In a sequence of n increments, worst-case cost per increment is O(log n) since at worst we flip log(n) bits. But, what is our *amortized* cost per increment? Answer: O(1). Proof: how often do we flip A[0]? Answer: every time. how often do we flip A[1]? Answer: every other time. How often do we flip A[2]? Answer: every 4th time. Etc. So, total cost spent on flipping A[0] is n, total cost of A[1] is n/2, total cost on A[2] is n/4, etc. So, total cost total is O(n), which means O(1) amortized per increment. Proof 2: every time you flip 0 --> 1, cost is $1, plus put $1 into piggy bank. (so total spent is $2). Every time flip 1-->0, use money in bank to pay for it. Why are we guaranteed to always have money in the bank to pay for these? So, we just pay $2 (amortized) per increment. In this case, "potential function" is the number of 1's in the current count. ============================================================= What if it costs us $2^k to flip the kth bit? Then in a sequence of n increments, a single increment could cost as much as Omega(n), but claim is total cost is O(n log n), so amortized O(log n) per increment. Probably easiest to see by 1st argument -- A[0] gets flipped every time for cost of $1 each, or $n total. A[1] gets flipped every other time for cost of $2 each, or $n total,... , A[log(n)-1] got flipped once for cost of $n. Neat amortized dictionary data structure: In next class we will look at a balanced tree data structure for storing information with O(log n) cost for search and inserts. Here is a method that's really simple, with O(log^2(n)) search (so, a little worse than others), and O(log n) amortized cost per insert. We'll have a collection of arrays, array i has size 2^i. Each array is either empty or full, and each is in sorted order (but no relationship between different arrays). E.g., if we had 11 numbers, it might look like this A0: [5] A1: [4,8] A2: empty A3: [2, 6, 9, 12, 13, 16, 20, 25] To search, just do binary search in each occupied array. In worst case, takes time O( log(n/2) + log(n/4) + log(n/8) + ... + 1) = O(log^2(n)). What about inserts? We'll do this like mergesort. To insert 10, we first create an array that just has 10 in it. We now see if A0 is empty. If so we make this A0. But it's not, so we merge this with contents of A0 into a new array (which now has [5, 10]). Then we see if A1 is empty. If so, we make this A1. But it's not so we merge this with A1 into another new array. Finally, A2 is empty so we make this be A2. So, now we have: A0: [-] A1: [--,--] A2: [4, 5, 8, 10] A3: [2, 6, 9, 12, 13, 16, 20, 25] If insert again, just put into A0. Claim: O(log n) amortized per insert. Proof: just the same as binary counter with 2^k cost for counter k.