Welcome to this lecture on amortized analysis, which is a technique for analyzing the cost of operations in data structures. It's a technique for analyzing the cost of doing operations in data structures. Let me motivate amortized analysis with a simple example. Let us consider an example of a stack where we are able to push or pop everything off the stack. We have three operations push, pop, or popAll. To illustrate what's happening. Suppose here is the current stack. Here is the bottom of the stack, here is the top of the stack. Let's say I push five, then a new element five gets added to the top of the stack. Let's say I pop the stack, then five gets removed and you have seven now on the top of the stack, let's say I pop again, you have four on the top of the stack. Let's say I do popAll. Now, this operation is going to remove all the elements in the stack and result in an empty stack. Now, what about the computational cost? The computational cost of push and pop, are assumed to be one. You're just adding and deleting an element from the stack, but as popAll is going to be as much as the number of elements you pop, in this case, four. That's the basic idea behind this stack. Now, let's look at the complexity of these operations in the stack. Let's look at the complexity of the operations in the stack and we want to study it in the form of amortized analysis. What is amortized analysis? In amortized analysis, we're going to not ask about the complexity of each individual operation in the worst-case, that's easy to answer and you should know how to answer that already. Push is constant cost, pop is constant cost, so you'd say Theta one, Theta one, and popAll is as much as the size of the stack, so Theta the size of the stack. That's the individual complexity of each stack operation in the worst-case. But suppose we are not interested in individual complexity as much as this. We have the following situation. We do n stack operations, and these could be any combination of push, pop, or popAll. The only thing is you can't pop from the stack where you have not pushed anything, so you have to always push something and then pop. That's the combination. We have n stack operations, and the question is, what's the worst-case complexity that can happen? You could say, well, because you have n operations, the stack cannot at any point have more than n elements. Now, the popAll is going to have a complexity that's going to be proportional to the size of the stack. In the worst case, the size of the stack can be n. The worst-case, popAll can have complexity that's proportional to n. You can say, I have n stack operations in the worst case, it can be all pop also which is O_n, which is O to the n squared total. Then dividing it by n, you can say per operation cost is O to the n, worst case. You have to think about this for a second and pause here and think whether this analysis makes sense or do you think it's overly pessimistic. Could we do better? If you have to consider some combination of n stack operations, and you want to know what's the complexity of these n operations together, you can take the individual worst-case for one of these operations and multiply it by n, but that doesn't seem to tell us the whole story. To tell us this whole story is what we do in amortized analysis, which is to look at what's called amortized cost. Let's talk about amortization then. What's the idea then? The idea here is this, if you think about this example in a stack with popAll, one of the things you can see is you can only pop what you push, which almost has this as the flavor of an important saying like, you can only reap what you saw or something like that. You can only pop what you push. Suppose you are pushing a bunch of things into the stack, S_0, S_3, S_4, then when you do a popAll, you can only pop the things that are on the stack so far. The cost of a pop is related to somehow all the pushes that have happened before it. You can't have this idea of sequence of n popAll. You can't have n popAll's in succession because the first one is going to empty the stack, and then the rest of them have zero cost. They're not going to have order n cost. The complexity of an expensive operation might be expensive only because you've done other operations before which have made this one operation expensive. If you look at it cumulatively together, maybe the complexity is no more than the number of push operations times two. That's the message that I'm going to be talking about. Let's talk more about this. Think about a more nuanced approach. In this more nuanced approach, let's think about time the same as money. Time is money. We will say the following. Whenever we push, we will pay $2. We'll pay two dollars in terms of computation time. One dollar is going to take care of the cost of pushing and then we stored the extra dollar as some prepaid cost, okay? This is just a way of thinking about it. Obviously, you'll never do this prepayment. It's not possible to bank time or to bank computation time but suppose you are allowed to do it, here is how you would do it. You would prepay and therefore your stack has the following property. Everything you've pushed, you've paid one dollar to push it but you also have a dollar that's left. You pay forward for each pop operation then we push onto the stack, you paid forward so now when you push you have two dollars. When you pop, your cost is $0 because you are already using the prepaid amount for that. In this example, every pop is free and every push is two dollars. Now what about the pop all? I'm going to claim this and think about it as also free because if I wanted to pop everything off a stack, you can always collect the extra dollar that I have prepaid for every element in the stack and just use that to pay for the pop all. It works for a single pop but it also works for popping everything off the stack. These are all free because I prepaid two dollars for a push. Now think about, if I had n push pop and pop all operations. Now let's do a more nuanced analysis of how much is the worst-case cost of a. Now, the worst-case cost of a is going to be twice the number of push operations plus 0 times the number of pop operations plus 0 times the number of pop all operations. Because you don't pay for it if you've overpaid for push. It's just twice the number of push operations. In the worst case, all n can be pushed so this is just two n. The total cost of n operations is two n in the worst case so the cost per operation is just two. This cost has a name, it's called the amortized cost. It's like an averaged cost considering n operations for some large enough n and considering the worst case for any n combination and dividing it by that. In other words, consider some n combination of operations of one, of n onto the stack and look at the total cost in the worst case as a function of n and divide that number by n and that gives you amortized cost. That's called the amortize cost and in this example, you convince yourself that the amortized cost of every operation is just two. It's not order n, it's exactly two. Its constant. It's amortized cost is constant which means any combination of n operations has cost theta n. This gives us race to a method called the accounting method and to summarize think of computation as money, pay money for future operations that can be just used. For a push operation, pay one unit for computation time and one unit for paid forward which you're going to use when it's being popped. Amortized cost of a push is just two units, for a pop operation pay one unit for computation time and then take away one unit of prepaid cost. Amortized cost is 0 for amortize pop all to pop key elements of the stack, k units of computation time, but I've already prepaid it when I pushed it so k minus k units, amortized cost for a pop all is just 0. Push, pop and pop all, amortized cost is constant. This method is called the accounting method where on some operations you pay forward and then on some operations you can utilize prepaid cost to offset the actual computation cost. To offset the the actual computation cost I can use some prepaid cost to offset it. In some operations you have to pay it forward. Now obviously, this is not rigorous but we can make it quite rigorous and I'll show you in a second how to make it quite rigorous. Let's look at another example before we move forward. In this example, I'm going to be thinking about a binary counter. A sequence of 0 and one bits on your computer and I'm going to be thinking about the operation of incrementing or adding one to the counter. Now, the algorithm for adding one to a counter is well known and let me just summarize or recall this algorithm for you. The idea here is you move from the right or the least significant bit to the left, which is the most significant bit. Therefore every time you see a one, you make it into a 0. As long as you see a one on the right make it into a 0. When you see the very rightmost 0 here, convert that into a one and then stop. If you have 1-0-0-1-0-1-0-0-1-1, this becomes 1-0-0-1. These are all unchanged from before and then the 0-1-1 now became a 1-0-0. This is the algorithm for an increment of a binary counter. You can see in the worst case, suppose I'm asked to increment this number one, 11111 and it's n ones, then I essentially have to go all the way and convert all of these ones to a zero, and let's say there's a zero here then that becomes a one. In the worst case, this is as much time as the number of bits, so Theta n times. A single increment can take Theta n time worst case. Suppose I have a binary counter, let's say I start with 00000 and I do m increment operations. I call increment m times. What's the total time it takes? It's going to be n for the worst case times m which is the number of operations, so you can say it's O n m. For example, if you have 128 bit counter and you're doing 1,000 increments, so then it has to be 128 times 1,000 in the worst case. Is this correct, is this tied? What we can see here is that amortized analysis is going to tell us a slightly different story. Because remember, this worst case is only encountered when every bit to the right is one. When you have a bunch of ones, and then once you have done this, once you have done the worst case, then if you increment once again you get 100001. Increment the very next step even though this step took n bits of update, the very next step just took one bit of update. It's not that the worst case keeps coming. If you are going to do a sequence of operations, it's not like you keep encountering the worst case again and again. You encounter the worst case ones and then it's okay. We can do an amortized analysis to see if that improves things. Let's talk about an amortized analysis. Again, this is the same thing I said in the previous slide, start with 000, perform k increments, so is the worst case O k times n and the answer is no, because what we're going to see is even though the worst case for any single operation is as many as the number of bits, that only happens in this very specific situation where the rightmost bits are all one. If the rightmost bits are all one, in the very next step you get 100. You get 100000, and then incrementing is actually quite cheap, you actually get the best case. If you get the worst case once, the next time you actually get the best case. Obviously, this is not telling us the full story, so what is the full story? Now we'll talk about an accounting method for amortized analysis for the binary counter. The idea is very simple. Every time we change a bit from zero to one, you pay two dollars. Think of dollars as computation time. You pay two dollars, one dollar for the actual computation of changing a zero into a one, and then pay one dollar forward to support a future change from one to zero. Here we go. Every time I change it, I have this extra one dollar which is prepaid, and I will write it here. Suppose I have my counter at 000, I increment it and I get 001. Now, in the very second step, when I change this one to a zero, I'm going to use this prepaid credit. This is what it's going to cost me. Then I change the zero to one, I'm going to pay two dollars here and then use one dollar for the computation cost and keep one dollar prepaid credit associated with this one. Here's the thing. Every time in this analysis I have a counter, then every of these ones has a dollar one prepaid credit with it. There's a prepaid credit of dollar one, so then the next time I increment I'm going to change this one to a zero. I will use this prepaid credit. But if I change the zero to a one, then I put a dollar one prepaid credit. There's going to be some prepaid credit that I'm going to accumulate in the counter that I'm going to use to pay for the future. I hope this idea is clear. Now, with this idea, what happens then is suppose I get in the situation that I have k ones to the right of my counter, then I do an update. Well, what's going to happen is the actual cost of this particular update is k plus 1, because you have to take all these k ones and change them to zero, and then you have to change the zero to a one. But what I'm going to do is I'm I've already prepaid k dollars every time I have these counters. There's already k dollars prepaid, so I'm going to utilize that, so that's going to be prepaid, so this is credit. I'm going to pay an extra $1, and I'm going to be an extra $1 here for this zero will changed to a one. The total amortized cost is k plus 1 minus k plus this extra 1, so that's just $2. No matter how many bits are to the right, because I'm doing Amortized Analysis, the amortized cost is just two. What's happening here is this, in this way of counting informs us that if for each operation, the amortized cost is two, no matter what it is, what the value of the counter is, the amortized cost of each operation is exactly two. If I have k increments, the amortized cost is actually 2k. This accounting method teaches us that the time taken for k operations is exactly 2k. There's different ways of analyzing and arriving at the same result, but this is a very elegant way of looking at it and convincing yourself that, if I did k increments my computation time is not k times n. That's an upper bound, but it's not correct. It's actually more like 2 times k, much, much smaller than k times n. Let me illustrate this accounting method with a last example. Then I'm going to have arrays which allow me to insert elements in reality. We've seen this before, and these are called dynamic arrays. Dynamic arrays, which are arrays where you can have insertions at the end. We saw this at the very first lecture of course one, so you can have 2,1, 3, 4, 7, 8, 10, 12, 18, 25, 32. So now you have unallocated space, and when you insert a new element, you add it to the end, and it takes up one of the unallocated space. But when you are filled up almost to the brim, you are unallocated space. Let's say now you want to insert a new element and there is no unallocated space. What you do is you allocate a new array, which is twice the size of the old array and then you copy each of these elements over, and now you have unallocated space left. This is what we're going to think about. What is the cost of this data structure? We've seen this, we've seen examples of this in hash tables as well, where we do rehashing. When the load factor exceeds some value, they're going to do rehashing. This pattern also happens at HashTable. The analysis that I'm going to do right now is also going to be somewhat important for things like HashTable. I'm going to be talking about that. Now, what's the cost of n insertion operations in a dynamic array? Well, if you have the worst-case reasoning, you will say each insertion can potentially cause a resizing, and cost of the resizing is the current size of the array. The worst size of the array is n, so the worst case of n insertions is order n squared because each insertion can potentially cause you to resize your array and have to copy over every element into the resize, so each insertion can be order n, because you are doing n insertion operations. Therefore worst case complexity is order n square. But unfortunately that's a gross overestimation. Let's perform an amortized analysis, because what we see here is this. When you do a resizing, when you actually do a resizing, there's going to be some unallocated space. Between this and the next resizing, you will have to fill up all this unallocated space before you get to the next resizing. It's not like a resizing is going to happen at every step. This is not correct. Resizing is not happening at every step. This is not happening at every step. Worst-case size of the array is not n because that's only at the very end of n insert operations, it's n. We have to think about this more carefully. Let's think about this using Amortized Analysis. What's the amortized cost of n insertion operations in this dynamic array? Here's how I'm going to be thinking about this. Every time I have this dynamic array. Let's say it's going to be like this. Suppose I have this dynamic array. Now I have the total size of the dynamic array, this is the allocated size. I also have the part that's been filled up. Now, every time I insert an element, I'm going to pay $3 for the insertion why $3? Well, I'm going to pay $1 for the actual cost of putting e in there. Then I'm going to pay $2, for future costs that are going to be associated with resizing. I'm going to pick $2. Why $2? I'll explain in a second. But I'm going to pay $2 here for future costs. Now the idea here is something like this. Let's take an example. Here let's start with a very simple example with an empty array. Let's say we insert an element, let's say we insert a one. We insert an element one. We insert an element 1, and now I carry $2 with me. Then suppose I inserted two, then I have the element. Now I have the array 1, 2. Let's not worry about the cost right now. Let's not forget about one. Let's say now I have $2 here. Now, suppose I inserted three, then I'm going to do something like this. Now, I'm going to allocate size 4 and then I'm going to copy one and I'm going to copy two, and this $2 with two it's going to pay for this copy. Then I'm going to insert three here, and that's now going to have $2. But since I have paid up for the copy here, I'm not going to have any left here, so now three is going to have $2. Let's say if I inserted another element let's say four, that's going to have $2. Now, if I insert a new element, my size is going to grow to eight, and now I have to copy 1, 2, 3, 4. They don't have any money, they are bankrupt, but then I will have to insert four more, 5, 6, 7, 8, and I'll have to pay $2 here for them. Now, these $2, one of the dollars will pay for copying them over, the other dollar will pay for copying one of the original four elements over. Now when I have to reshuffle and resize to an array of size 16, these will pay for all of them. In general, the picture looks like this. I will have size, let's say total size right now is n. I will have n by two elements that were previously copied over, so they have no money left, but as everything that's inserted after that is going to have $2. These n by two when I insert them they will give me $2 each, so the total amount I've accumulated is two times n by two, which is $n. That's the total amount I've accumulated. When I resize this to 2n, I have to do n copies, and so I have the cost already prepaid for a future copy, not just for an element on the right-hand side of the array, I also have prepaid for element on the left hand side. This is how this is going to work. The important part is every time I resize, I copy and elements, but I keep space for n more. This doesn't cost me anything, to allocate space doesn't cost me anything, what cost me is the copy, or you can think of allocating space as costing me a constant, but what is really costing me is the copy operation, which is going to cost me n. I hope this idea is clear, this is important. Then, you see that the latest n by two inserts are paying for the previous n by two, which already paid when I copy this over. It's like the first half cannot pay for it, but then the second half are paying $2 where $1 pays for themselves to be copied over, and then another dollar pays for the previous four. Then when a copy over all of these won't be able to pay, but then the next eight coming in, we'll pay for these eight. That's how it's going to go. Dynamic array, then what's the cost of resizing? Well, the new resize, you have n by two elements which for which you haven't paid, n by two elements for which each of them you have paid $2, so you've already paid n. The cost of resizing and copying is already paid for, and then comes the cost of insert, so that's $2, plus $1 for insert so $3. Even if you resize, the cost of an insert remains $3, or three units for every insertion even if you resize. To summarize in dynamic arrays, the amortized cost is one unit for computation cost and two units paid for future resizing. Then you re-allocate, you have n plus 1 units of actual computation cost, n units for copying, one unit for inserting, but n by two elements, each having two units of prepaid time. Two units of prepaid time cancels the end units of cost you need, so it's still three units of amortized cost. You can see that the amortized analysis, I can show that the complexity of n insertions is 3n amortized complexity. The complexity of each insertion is three units of amortized cost. I will stop here, and then in the next lecture, I will formalize this using something called a potential method that will make this argument quite formal using a potential function. I'll talk about this and I'll rap it up next lecture. Thank you.
