15-451 Algorithms 09/21/04 * Amortized analysis mini2 due tonight quiz1 next week (30 min) ---------------------------------------------------------------------------- So far we have been looking at static problems where you are given an input (like an array of n objects) and the goal is to produce an output with some desired property (e.g., the same objects, but sorted). For next few lectures, we're going to turn to problems where we have a *series* of operations, and goal is to analyze time per operation. E.g., binary search trees, hash tables. Today, we'll talk about a useful kind of analysis, called *amortized analysis* for problems of this sort. Before getting to what this is, let's motivate it with a simple 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: inserting into array costs 1, taking element out of array costs 1, and the cost of resizing the array is the number of elements moved. (could make it 2x this) 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 inserting/removing is <= n. Total cost for doubling is at worst n + n/2 + n/4 + .... <= 2n. So, amortized cost per operation is <= 3. 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. So amortized cost <=3. 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). Def: Potential function: a function of the state, generally should be non-negative and start at 0, used to smooth out analysis. Amortized cost = actual cost + change in potential. In the "piggy bank" view, the amortized cost is the out-of-pocket cost per operation. E.g., in our case, the amortized cost of a push was $3, even if you resize (since resizing was paid for fully out of the bank-account/potential-function), and the amortized cost of a pop was $-1. =========================================================================== 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. ============================================================================== 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: <= 2. Proof 1: 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. On a given increment, how many 0 --> 1 flips do we make? So, we just pay $2 (amortized) per increment. In this case, "potential function" is the number of 1's in the current count. Proof 2: 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 at most 2n. ============================================================= 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 $n, but claim is amortized cost is just 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. So, total is O(n log n), which is O(log n) amortized per increment. 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 the number 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.