Amortized Analysis

Last week we took a look at implementing a queue with two stacks, and one of the things we noted about the efficiency of this particular algorithm is that well, most of the time it’s pretty fast It’s pretty constant time, but at certain points of time, things suddenly get very slow This sort of behavior actually comes up from time to time in computer science when you’re working with certain data structures, so of course the question is – Is there a better way to actually think about the time complexity of such algorithms? In this episode, that’s exactly what we’re gonna do! We’re gonna take a look at a technique called Amortized Analysis that actually gives us a better measurement of this quantity! More on this after after the break! Hello and welcome back to another random wednesday episode! Now, first and foremost I do have to let you know that this particular episode covers a slightly more advanced concept in time complexity analysis, so if you’re not very familiar with things like the Big O Notation then you should check out an earlier series that I’ve made – It more or less covers all these concepts in terms of asymptotic notations – In fact that’s what it’s called So yeah, if you want a more complete picture, do check out that playlist Basically today, we’re going to be talking about Amortized Analysis, and one of the most important things you need to know about this technique is that it’s only applicable in certain cases, namely when you’re working with an algorithm or data structure that basically has multiple operations Some of these operations are fast, some of them are slow, and the idea is we want to look at a whole bunch of operations at once, and basically see what all these operations together, tell us about a general “average” operation on this data structure There are actually three different ways to perform amortized analysis, and today what we’re gonna do is we’re gonna scrape the surface of each So we’re going to briefly look at each, all in the context of the same example, and hopefully we’ll paint a rough picture of how these techniques actually work So yeah, without further ado, let’s jump in first to the example, and then to actually applying Amortized Analysis One of the classic examples used to demonstrate amortized time complexity is the dynamic array data structure Here’s how this works – Imagine we have a small array and the idea is that we want to insert an unknown of items into this array Of course, eventually the array gets full and the strategy used by this algorithm is that we are to create a new array that is double the size and to actually move everything across This of course, as you can imagine is a slow process, which is why this is such a good candidate for discussing amortized time complexity Of course, this doesn’t just happen once.When we next fill up the array, we’re gonna have to do this same thing again This step of course is also very expensive because we’re copying even more items across now Here’s the deal – At face value, analysing the time complexity of this gives us wildly inconclusive results When I’m actually inserting an item that doesn’t trigger an array expansion, well that’s basically instantaneous That is a definite O(1) operation However, when I actually do trigger an array expansion, we’re moving n items from one array to another, making this step an O(n) step So what really is the time complexity of a general operation on this data structure? That is the question that amortized time complexity tries to answer for us Now, let’s sorta actually step back and take a look at when these expansions happen What that means is, for each one of these little gray boxes, we’re doing one unit of work However, when we encounter one of these red boxes, well, we’re doing quite a lot of extra work, on top of the normal insertion We can also observe that every time this happens, it happens half as often, but it does twice as much work And perhaps intuitively you can kinda get the idea that these two things sorta cancel out and is somehow constant in effect By using amortized analysis, we can actually make this more concrete This table is just a different way of showing you what we’ve just seen, which is of course the number of operations required for each step Basically what you’re seeing here lends itself to one of the simplest ways of actually performing

amortized analysis and that is the aggregate method Really, the aggregate method is just an average And that of course is the simplest way of actually getting a good idea of how much work is happening per step You want to get the total cost of a set of operations, and actually divide it by how many operations you’ve done in that set And that gives you a good idea of what the “average” time is required per operation So let’s actually work on both these values here Going back to our table we can actually calculate the total cost of however many operations In fact, we’re not gonna define that, we’re just gonna say it in terms of n So basically the total cost is the sum of n operations To make this simpler for us to understand, let’s actually separate this into cheap operations, versus expensive operations Cheap operations of course being those insertions that don’t actually require array expansions, and expensive operations are those that do The cheap operations are easy – There are nearly n of those if we insert n items, and since each one of these items are O(1) operations, we can say that in total, the cheap operations add up to O(n) It’s a little bit more challenging to actually consider the expensive operation, so let’s work through this together What we’re gonna do is we’re gonna pretend we started with an array of size 1 and we’re triggering expansions from there So we’ve basically inflated the number a little bit here, and what you of course notice is that these are just powers of two – 1,2,4,8,16,32 and so on Now, what do we get when we try to sum all these numbers up? When we’ve inserted one item, the total cost of the expensive operations is one When there are two items, the cost is now three As we move on, we are actually piling up this number, and this actually shows us a very interesting pattern This number is approximately double of this number In other words, the cost is actually approximately double the number of items there are So yeah we can put it like this – The total cost of the expensive operations is just slightly less than 2 times the number of operations there have been In other words, it’s slightly less than 2n, and under the big O notation, it is simply O(n) Going back to our computation for the total cost, we just have to add both of these things together At the end of the day this simply gives us O(n) We know that we’re basically performing O(n) worth of work by doing n insertions Doing our averaging, we get O(1) And therefore, using the aggregate method, we now know that the amortized time of doing operations on this data structure is simply O(1) This of course fits the intuition we’ve seen earlier – As we’ve mentioned, the work becomes twice as difficult but comes half as often, and we concluded intuitively that it’s going to be constant time, and aggregate analysis has actually proven that to us So aggregate analysis is one method – Let’s now take a look at another method called the accounting method This method takes a slightly different approach to the problem – Essentially, instead of looking at things in general, we want to jump in to look at every single operation In fact, we assign every operation a cost Normally to go along with the accounting theme, we’ll actually express the cost in dollars If you have any surplus it goes into a bank The reason why we’re doing this is well, when we’re doing simpler operations, we’re actually overcharging – We’ll actually give a bit more money than it’s supposed to use, and the idea is we want to build up savings – Enough to afford a more expensive operation later And of course, again, to align ourselves with the accounting theme, the bank balance must always be 0 or greater We don’t want to be in debt, that’s the whole idea So, let’s actually go back to our dynamic array – The solution for the dynamic array is to actually charge 3 units or $3 per operation So we’re gonna visualize it like this – We’re going to start off with a bank of $0 Every time we insert an item, we’re gonna charge 3 units Now, one unit is used immediately for the insertion, so we have 2 units of surplus sitting around So yeah, we now have some healthy savings, but unfortunately, the array is now full and we have to perform an expansion All we have to do is to actually use up the money we have saved up to move the items to the new array So in fact, the expansion step costs nothing!

We’ve not assigned any money to this because we just have to tap upon our savings So yeah, that the existing state – We actually still have $1 left for these first four items, but I want you to sorta pretend they don’t exist This surplus money that’s sitting here never gets used again This is an outlier for the first four items – As we continue to add items you’ll realize that this no longer happens Let’s just continue seeing this in action As we insert more items, we are of course building up our bank once again, until well, the array gets full This is where the interesting part happens When we create our new array, of course, items number 5 through 8 have the savings to actually transfer themselves What’s even more cool is they each still have a dollar left, and what this means is we can actually use the surplus we have left over, to transfer items 1 through 4 I can use the leftover dollar from item 5 to transfer item 1 I can use the leftover dollar from item 6 to transfer item 2 So on and so forth and by actually exhausting well, the remaining surplus from these four items, I complete the whole movement operation, without incurring any extra cost Now, let’s see this again when we actually have items 9 through to 16 Again, we’ll actually $2 to spare for each one of these items When we actually perform an array expansion, we can of course afford moving well, the items themselves but we also have enough money to move the items that no longer have any cost associated with them This brings our bank balance back down, and in fact this goes on, no matter how large the array is, this logic will continue to hold As long as each operation is actually charged 3 units or $3, we’ll be able to sustain this continuously no matter how big the array actually gets Since we now know that every operation has a constant cost of 3, the amortized time resolves itself to O(1), or constant time per operation So yeah, that is how the accounting method works Let’s move on to our last method, namely the potential method Conceptually this is exactly the same as the accounting method, for each operation we want to give a little bit more, this results in a stored surplus, and this surplus can be used to pay for the more expensive operations later on The difference is this method is more like physics, and we think of things as stored potentials which is sorta analagous to the bank in the accounting method We are also bounded by the same limitation, and that is we should never end up with a negative potential The key difference between this method and the accounting method is that the bank balance is no longer state-dependent For the accounting method, to know how much money is left in the bank at any point, we’ll have to actually start from the very beginning and work our way towards that particular point The potential method actually makes use of a function, in other words a little equation, and we can actually use that to derive the potential of any state Let’s see how this works Essentially we’re using the symbol phi to represent the potential of state h So h actually refers to a particular state in the data structure So of course the difficult part is to actually find that potential function that can represent the amount of potential at any state In the case of the dynamic array, this is the actual function n is the number of items we have inserted so file, and size refers to the actual size of the array, including the actual elements in the array that haven’t been filled yet On the examples up till this point, we’ve actually started with an array of size 4, but this actually assumes we start from size 1 instead, so yeah let’s actually work with things this way instead of starting from size 4. it’s not going to be hugely different – When there is one item, we will have to expand to size 2, therefore our potential of 2xn – size gives us 0 That’s great, that’s fine, that’s not a problem – Again when we have two items, the array would have resized itself to size four Our formula again gives us zero When we have three items, we do actually bit of spare potential.However, when we add yet another item, well the size is increased, and we get a potential of zero again So yeah, by just taking double the number of items in the array minus the actual size of the array, we’ll get a potential that is zero or greater at all times

As mentioned of course the cool thing about this is that we can actually check the potential at any point For example if we’re now at item number 384, well no problem, we can simply insert that into this formula, 2×384 minus the size, which of course we know that the closest larger power of 2 is 512, this tells us that there is this much potential left Now, in order to actually calculate the amortized time of the ith operation, in other words h_i, we’ll actually do something that looks like this Now I know this is a little bit complicated but essentially what you have here is a potential difference The potential of the current step minus the potential of the previous step That is of course how we get the difference any two values really To get the amortized time of operation i, is to actually add the cost of that operation to that potential difference I know this is a little confusing but once we put it in action it will be okay Of course we know that our potential function is 2n – size, so of course we can simply use this to calculate the general case amortized time Now here’s the deal – We need to know that our potential function actually behaves in two different ways – There is the normal case as well as the array expansion case So what we’re gonna do is we’re gonna look at them separately So let’s assume we’re talking about a normal case here – No array expansion Let’s actually insert all these numbers and see what it works out to So we start by actually substituting the potential function of the current step and the potential function of the previous step Don’t be too intimidated by this, this just comes from the potential function, and we’ve of course substituted i-1 for the previous step Now since this is a normal case, the cost of this operation is simply one We’ve just inserted one item, so no big deal Let’s do a little bit of algebra Let’s go ahead and expand this stuff inside here, multiply in the negative sign, get rid of all the brackets and what we notice is that nearly everything cancels out! The size cancels out since it’s the same value, 2i cancels out, and what we’re left with is 1+2, or 3! So this in fact is giving us the exact same result as when we actually used the accounting method Of course, we’re not quite done yet, this is the normal case Let’s actually look at the expansion case The cost is not just 1 – We’re going to have to do i+1 operation because an insertion requires 1 operation, and moving everything requires i operations, since there are i items in the actual array Substituting the actual potential function is a little bit tricky since of course, the value of “size” is now different Luckily, since we know we’re at the array expansion case, we know that i is essentially the size Before we perform the expansion, the size of the array is i After we’ve performed the expansion, the size of the array is 2i So yeah! All that’s left to do since everything is in terms of i and constants, well we’re just gonna get rid of all the brackets, put everything together and guess what? All the coefficients of i cancel each other out We end up again with just 3! So yeah! Since there are only two cases – The expansion case and the non-expansion case, and they both give us 3 operations in amortized time, well, it’s O(1)! We can just conclude that per the potential method, any operation incurs an O(1) amortized time So yeah! Wow, we’ve actually gone through a lot of content today, so let’s very quickly summarize First of all we have an aggregate method which is like taking an average Simply put, this method is taking a total cost divided by the number of operations that ended up incurring this cost So yeah, in fact this is one of the simpler ways If you actually want to move on to more complex ways, you can use the potential or accounting methods Conceptually they’re the same You want to assign a cost to each operation Cheaper operations are overcharged which gives us a surplus, and expensive operations are paid for using that surplus The difference between the accounting and potential methods is that the accounting method is actually operation dependent whereas the potential method actually defines a formula that tells you the potential at any point of time, so you can think of this as the slightly more rigorous way of doing the same thing While we end up with the same results, this method is more robust because it is operation independent As a drawback, it is of course more mathematical

So there you go! That was amortized analysis We’ve just taken a look at three different ways to perform amortized analysis, and we applied it to the most classic example which is the dynamically resizing array As mentioned we’ve just scraped the surface today Applying amortized analysis on real hardcore data structures may be a lot more difficult There may be a lot of sorta staring at it and just waiting for the intuition to jump out at you, but the fundamentals remain the same and hopefully what I’ve done for you today is I’ve painted a rough picture of all these fundamentals Anyway that’s all there is for this particular episode I hope I’ve been a help! Thank you very much for watching and until next time, you’re watching 0612 TV!