when we're talking about the time complexity of a single loop or a function like Fibonacci or factorial we've only got one thing we're looking at we're looking at that one function call that one loop and we're saying how long did it take when we're looking at data structures that persist over time often this kind of analysis is less useful instead we're required to look at a sequence of operations in order to understand how the data structure is going to perform the tool we're going to use here is amortized analysis what this allows us to do is to look at the cost of a sequence of operations rather than looking simply at one operation in isolation if you've ever used a loyalty card at a retailer you know what this is like I go to Starbucks after nine coffees I get one free it may be more compelling to think of a super loyalty card let's suppose normally I get a $3 coffee at Starbucks and they give me a deal which is that they're gonna say well look you buy one coffee for $27 and then we'll give you nine for free and if you think about it that's a good deal I'm still getting less than I would be paying for 10 coffees at $3 a coffee that would be 30 bucks and I'm getting them for 27 so the amortized analysis I can make as long as I'm going to keep buying coffee that's a good deal we're gonna look at two examples of this kind of amortized analysis the first is resizing arrays and the second is building strings if you remember back when we talked about stacks implemented inside of arrays we had a little issue there which is that the stacks were fixed capacity that's not great and that led us to come up with a linked structure to represent a stack but there is a way to represent a variable-length stack using arrays what we simply need to do is to occasionally throw away the array we have and create a new one of course that's going to incur the cost of copying the contents of the old array in to the new one and we need to take that into account as we analyze the code here's something that does exactly that my stack here is called performance of arrays I have a underlying array a which is going to store my data account which keeps track of how much of the data in the array is significant and I'll initialize those to have just a single element in the array which is not significant and my push method here is going to simply take the item that's being pushed and store that in the array at element in and then of course we increment in that works fine as long as we have space or capacity in a in the array but there's a problem here if we run out of capacity so once n is equal to the length accessing the array at element n would give me an array index out of bounds exception and to avoid that I'm going to call a resize method to throw away that small array and give myself some extra room what does that look like I'm simply going to resize to a given capacity and then copy all of the old elements from the old array into the new array and finally throw the old array away and update the variable a to hold the new array temp which is bigger I've also annotated the code here to do a little bit of printing so we can see stuff and also to record the number of Rights that I'm doing so we can keep track of the complexity of what's going on here so let's start looking at this where we do in pushes for some large N and I'm going to start off where when I run out of room I'm just gonna give myself one extra bit of space so what's that gonna look like how much work do you think I'm gonna do to do in pushes with this kind of strategy so each time I need a little bit more room I'm just gonna create a little bit more room just the amount I need so I'm optimizing space I'm not wasting space here I'm only allocating space that I need that's great but let's think about how much copying I'm going to do and in fact that's what I'm printing out here it's the copying now that copying is not productive all it's doing is copying the old contents into the new array so it's really just wasted effort you can see that push is constant time if you just look at the work that is happening in the method itself the only more complex thing that's happening is in the resize method but analyzing resize is quite difficult because in order to understand how long resize takes well we need to know what n is and that varies so as we increase the size of our stack in is going to increase we'll start with 1 then 2 then 3 then 4 then 5 oh and so now we're for copying that many times we copy once then twice then 3 then 4 then 5 oh how many times are we copying well that's something that's familiar to us it's a triangle look how much we copy we copy once we copy twice we copy 3 times once I've got three things well it's great I have three things in my array but when I need room for a fourth I have to copy all those things over again and all of this copying adds up we've already done this analysis we know that if we're going to be doing a triangular amount of work well that's actually in squared time now note that this is not the time for a single operation so one push is not costing me in the squared time it's instead doing in pushes in pushes taking in squared time now if you look at the time of each individual push then you can sort of take the average if you like and it's it's in or linear and this is borne out experimentally you can look at the wall clock here and for 260,000 elements it's taking 40 seconds to push those 260,000 elements into the array and why is that it's because I'm doing this ridiculous amount of wasted copying effort so the first thing you might think is well why am I just giving myself one space let me give myself more space let me give myself 10 extra spots surely that's gonna be better and it is for a little bit you can see I actually get well ten times better performance in fact for two hundred and sixty thousand elements instead of taking thirty-eight seconds it's taking 3.8 seconds so in fact almost exactly 10 times faster and you can also see that in the sort of output here so instead of getting that big triangle I'm getting a flatter triangle the point is though this is still a triangle and the sum is still unfortunately quadratic and you can see that born out both by the annotated code where I'm counting the number of operations and also by the wall clock so for two hundred and sixty thousand elements it's still taking four seconds it may seem at first that this is sort of like my Starbucks card I I pay for ten pushes upfront and then I get nine for free the problem here is that the cost of that tenth push keeps going up because there's more and more things behind me it's like when I go into Starbucks they don't just charge me for the 10 coffees I'm at about to have but they also charge me for every coffee I ever had before so I I go into Starbucks it's $10 this week and I get 10 coffees next week it's $20 and I get 10 coffees next week it's $30 and I get 10 coffees and that cost is gonna keep piling up behind and drags everything to a grinding halt and it doesn't help to make it a hyung either so you know 100 free coffees sounds great but the thing is if those coffees keep getting more and more expensive eventually the coffee's not gonna be worth it and here indeed I'm doing those 260,000 pretty fast now but still I can't really scale up to larger problem sizes so here 99 constant-time coffees for one that's got a cost that keeps going up I'm still at amortized linear time so each of these coffees is actually costing me proportional to the total number that I ever had so what can I do well we can be sort of informed by our analysis of loops so we noted that the triangular loops had this kind of quadratic performance we got much better performance if we had the flat-pack loop and what a flat-pack loop look like well I double the amount of work each time around but overall I do things fewer times and I can do that in this code by resizing by multiplying by two so if you think what's gonna happen here you know the first time I run out of room I copy one element the second time I copy to the third time instead of copying three elements I copy four after that the fourth time I copy eight v 16 and so on and so forth and what that means is that I do a lot less copying I know that this looks kind of like a triangle this is not a triangle this is a swooped down flat pack in the sense that I can take all of the things here on top of the bottom row and pile them up right on top and I just get something too deep this is not a triangle and that is borne out experimentally as well you can see here for 260,000 elements oh well that's still fast but look how much I can do I can now get up into sixty million elements in still less than half a second and this kind of performance is something I wasn't even getting close to with my additive solution for two million here it's taking me thirty seconds for two million here it's taking me nothing so by doubling the array size each time I save a huge amount of work overall the total time for in operations is about two in and therefore each individual push is amortized constant time this is a huge win and you know if you're winning with two you might think I'll win better with four you know you you can do a little bit better I guess let's see what the absolute numbers look like for 67 million I'm getting half a second well let's see what's like with four well for 67 million I'm getting about half that okay that's nice what if I go up to eight well yeah it's yeah and it seems to bottom down actually I'm not getting that much better in fact it may be slightly worse you know it doesn't matter what the multiplier is what matters is that I'm multiplying and that's what gives me the ability to flat pack these sums so the work is spreading out if you like if you think about it the amount of copying I'm doing is much larger but I get more free things afterwards so here it's like I'm going into Starbucks and it's like the first time the the card is ten dollars I have to go to one dollar copies because again multiplied by three that fast so the first card is ten dollars and I get ten coffees the the second card is 20 dollars but I get 20 coffees then the next time I go and the I have to pay $40 but I get 40 copies it's not it's not really that dreadful so you can see that the amount of free stuff I getting corresponds to the amount of coffees or the amount of copying that I'm doing and this works even if the multiple is less than 21.5 is a common choice for resizing arrays because the arrays don't grow quite as fast you may not waste quite as much space but you still get the rocking performance and and you can see that here I actually do do a little bit more work and this is looking more like a triangle but this is not a triangle this is still a flat-pack the thing is growing you can see that each layer is sort of longer than the one preceding it and that's the important quality and in fact you can see the numbers sort of bear out here in this case the numbers are going up and down and up and down up and down up and down and it can be a little confusing to see what's going on the reason for this is that sometimes we have over-allocated and sometimes we've under allocated and so the cost is sort of varying a bit so what I've done is it just added up all of these multipliers and taking the average and you can see that the average Delta the average change from one to the other is really quite close to two it may be somewhat shocking but in fact it really doesn't matter what this multiplier is as long as it's larger than one so even taking something like 1.1 well you know we've got something looking pretty triangular here for well but note that after a while it starts to lengthen out and that is an important quality it's enough it's enough to get the performance that we need and again if you look at what happens here I'm actually getting excellent performance even multiplying just by one point one the point is that the number of free accesses that I get is sort of scaling as I get larger I get a larger number of free or low-cost accesses for larger sizes the total complexity for in push elements here is is right at linear time you can see in absolute terms that I'm doing about 10 in work to push in elements if you go back you can look at the 1.5 solution you can see I'm doing about three in work here you can see that four eight in it's quite a small factor for four in it's a little bit bigger for two in it's right at two times so two times work for 2 n 3 times work for one and a half in ten times work for 1.1 in and you can work out the math and you in your head if you want but it's not that important the real deal here is that if you look at the ratio of one size to the doubled size it's going to be right at 2 and that means that it's some sort of linear function it really doesn't matter if it's x 2 or x 10 it's a linear function and that's going to dominate everything the particulars it's chosen and implementation is actually a balance of size and space so if we choose a larger constant like 8 well we might be wasting a lot of room in the computer if we choose smaller constants we will waste less room but we do slightly more work so we can decide whether we want to have a little bit more in terms of the operations or a little bit more in terms of wasted space that's the trade-off last time I looked at javis ArrayList class it was tuned to right at 1.5 so this is how a resizing array is used to implement something like a stack if you want to see a more fully fleshed out example you can look at the resizing array stack class in the algs 1:3 package this is a fully fleshed out sort of example where we not only increase the size when pushing but also potentially decrease the size when popping so as to avoid wasting space you can also see a similar implementation with the resizing array q also in the algs 1:3 package where again NQ + DQ may both cause the array underlying the data structure to get resized

in every programming language that I know strings are implemented using arrays and it's sometimes important to understand that underlying implementation in order to avoid common bugs which can cause efficiency problems in your code as the data scales we're going to look at a simple example which is building up a string from in pieces I'm just gonna take an asterisk and I'm going to build a string of length n by appending one asterisk at a time and I'm gonna try doing it two different ways one is the first thing that most people think of which is to use a string variable and to concatenate each time updating the variable the second way is something that you may not be aware of it's the use of a string buffer in Java the string buffer class is something that's used to make strings and it has an append method which allows me to add a star onto the end of the existing string and then I can convert my string buffer to a string by invoking the two string method this is a linear time operation so whatever the length of the current string and the string buffer is it gets copied out as a result let's look at the performance of these two different ways of making a string and in my main method I'm going to just first try a string of 32 and and I want to show you what that looks like so I'm actually going to print out the string that was built as a result of doing that and then I'm just gonna jump in and start building larger and larger strings to see their performance so if you count the asterisks here you'll see there's 32 of them so this is actually building a string of the right line and then if we jump in and just sort of watch how the strings are getting built here I'm counting the number of operations that I think are performed and you can see that that is going up quadratically and just to see that I'm not making it up I've got the experimental wall clock numbers to back that up so that this is actually doing a quadratic amount of work to build a string of length in and that means that each of these concatenation operations that are being performed here is amortized linear time this is not a constant time operation it takes time proportional to the length of the result and this is a real common bug I have seen even professors of this course make which is to take a data structure and try and print it out as a string using this kind of concatenation this is how to print out an array in quadratic time and you will be fired it's just a mistake you don't want to make on the job it's okay to make it in this class this is where we're learning this stuff so how are you supposed to take a array and print it out as a string well Java provides the string buffer class for exactly this purpose and what a string buffer does is uses an underlying array of characters to sort of build up a string strings are immutable in Java just as they are in many languages and that means once you've built a string you're not allowed to change it by adding things therefore the string buffer you can think of as sort of a mutable version of a string what I do here is I create the string buffer I append elements into it and at the end convert it to a string each of these appends takes constant time amortized because there's an underlying array so Java is doubling that array or 1.5 times in that array it's changing the size of the array as needed but it's doing it to give me amortized constant time for each append and therefore I get amortized linear time for this algorithm here to make a string and again you can see that born out experimentally I can create quite large strings here I have a string of almost half a billion characters that I can create in seven seconds with the quadratic algorithm before already for a string of 1 million elements I was taking more than two minutes and so using concatenation to build a string in this way is just a bug and even for relatively small data you know for 65,000 elements it's taking half a second and you don't want that happening on your application for 65,000 elements here we're you know what a nicer number we're down in milliseconds so Java's string buffer class gives us an append operation that works in amortized constant time and thus we can build up these kind of strings of some length in in linear time to see this in action you can look at the resizing array Q or the resizing array stack each of these has a two string method which uses a string builder to build the string representation of the data structure this is the correct way to create a string for a collection of lengths in using a string buffer