Video 3-2: Resizing Arrays

0:02 In the next section, we'll look at the first more interesting data structure, namely arrays where you can change the size, which uh is an contradiction in itself because indeed arrays uh are the very thing that you cannot change the size of. If you want, you can even see arrays as a kind of an abstract data type with the operations that you can create it with a fixed size that is not changeable and you can read a certain index and you can write a certain index. Now unlike actual um abstract data types, there's only one sensible implementation for an array which is an array uh a contiguous chunk of memory. So a starting index and then the offsets. What we here use as relative indices is just the starting index plus I times the size of one cell. And so um this is baked into any programming language you could think of. And even our word ramps natively support arrays. So um maybe this is more of a question mark but the idea was to get you thinking of what what really is the essence of an array.

1:14 But of course then what I said resizable arrays makes no sense. So what what is meant by that is a way to have these operations in hopefully a fast way but still allow to also append elements at the end beyond the initial n cells that we created.

1:41 Okay. And the simple trick to do that is whenever you run out of space in your array, you double the size of this array, which means you allocate a new array of twice the size and throw away the old one. Uh before you throw away the old one, hopefully you copy the data over, otherwise it would be lost. And precisely that part for sure that second part is costly because you need to copy all the elements. And then if you do it in Java, even the first part is expensive because allocating an array initializes it to zero even if you immediately overwrite it again.

2:19 Uh a concrete trick. I think most of you will have seen some form of this trick before, but uh I want to show you the the ultimate version that also shrinks again and do the analysis a bit more carefully than um in algorithms data structures. Uh the precise way to do this is and I'm I'm still um thinking nominally of a a stack that's why it also says s here. So let's implement a stack on arrays but without a specific capacity limit.

3:03 That's what the analysis is geared towards. So what we maintain is the current capacity of our array and we require that this is always compared to the number of elements in the array well at least as big as I need otherwise I couldn't store them but also not much much uh larger. So there's most a factor four difference between the two. If I can somehow make sure that this is always true, I can always push another element because C happens to grow with this. But how do we do this? What we can do is before a push operation that adds a new element at the at the end to check if we're out of capacity. if that new element would bring us above capital C elements and if so we double our size of the array and thereby also double C and then I have space for the new element and likewise upon a pop if I'm now too empty in my array if I'm less than a quarter filled then I also allocate a new array of size 2 * n the number of current elements and um throw away the big array Okay, then my C has shrunk by a factor two and I'm again in the good range. That's what usually people mean uh with saying resizing arrays or doubling arrays or dynamic arrays or any of these slightly u misleading terms.

4:32 The exact factor is whether this is a factor four or not. You can play with these constants and you get slightly different trade-offs. But let me stick with these constants. Uh nothing magic about them. I asked you um to fill out this question already. I'll just head over.

4:53 What does that precisely mean? If I'm using this idea as I now sketched it and um I occasionally have to double or shrink my array, uh what does that really mean for such a data structure in terms of its performance? And this question is a bit of a read every sentence very carefully question.

5:16 Let's see if you've done that. Anyone still typing at this point? Then let me show the votes. And you might be annoyed to hear that only this is really right if you are very careful. Uh so the first one the elements are stored in an array of size exactly 2 n. No uh n is the number of current elements and I don't always change the size of the array. So this is only true right after this um growing or shrinking.

6:04 Adding an element at the end takes constant time. If I write this without any qualifier, it must be true in the worst case for all operations. And that's false because I might be at the end and then have to double then it's linear time.

6:22 C is correct. Let me come to that last. Um why is D not correct? inserting and deleting any element takes constant amortized time. We haven't spoken about amortized yet much, but that's not the point. The problem is the any. If I delete from the middle of the array, I still have to shift everything over to make it an array again. So, what's the uh precise question here for this um n plus m? Uh we're looking at a sequence of m insertions or deletions. They can be mixed in any way and uh at the end um right that that's sorry the parenthesization is insertions deletions only at the end of the array push or pop then the total time is linear in the number of elements I started with and the number of operations I've done that's what we mean with this statement constant amortized time. Uh but the the more intuitive precise version may be this which is a bit a bit more um explicit in what we actually show.

7:42 So this uh the concept of amortized analysis um again assuming you've seen before uh the concept here is is simply an individual operation could be expensive but the way we've set things up is that any such expensive operation must be followed by a lot of cheap operations. So we can make all of these cheap operations chip in a little bit to pay for this one extens expensive operation. And indeed, if we're clever enough with the data structure, we can make sure that we never pay u several expensive operations in a row. To analyze this, um here's a bit of of notation that is very standard for for such analysis. You'll see the same most of the time. There's an actual cost of the operation that is the thing that is very jagged. It could be large for some operations and small for others. Then we'll define some mystical um quantity. The potential by the way this is uh not the potential from termination proofs.

8:50 It's just the same name uh but is a is a different thing if you want. And based on these two we define an amortized cost of an operation which is how much does it really cost but then how much does the potential change and the idea is that somehow uh expensive operations are canceled out by a change in potential and cheap operations are paying a bit more to bump up the potential so that then later expensive operations can profit from it.

9:22 The goal in all of amortized analysis is that you try to show this that no matter what operation you have, there's an upper bound on this on this fake amortized cost. You cannot bound the real cost in all cases. It might be expensive sometimes, but you can try to find a potential that makes the amortized cost bounded say by some some constant a in this case. If you can do that, then you can do the following rewriting trick. You start with summing up all the amortized costs using this. If you've proven this inequality, that means this sum is at most m times this capital a because I'm doing m operations here in total. But I can also insert the definition of ai and then I get this telescoping sum. I always have uh fi i here negatively and then that's positively positively in in this iteration. But then for the next value of I I have it negatively. So they all cancel except for the the first and last.

10:33 And with that you can take the quantity we actually care about namely the total cost of all operations. That was the statement in the question as well. The total cost of all operations is then upper bounded. I'm rearranging.

10:48 I'm putting this to the other side and I'm leaving the m* a here. So if if this a is something small and these potential functions can be somehow proven not to be uh too large in absolute terms then this is giving me an upper bound that is is linear in m which in our case is what we would want and the linear term the n term will come from this. Let's briefly look at this in our concrete example.

11:31 Um the potential we'll look at here you could think of as the safety distance from when you have to act on the array. This is your array. There's a capacity here and then there's a quarter capac C divided 4. Your number of elements should always be in this in this range here.

11:59 Then you're allowed to keep your current array. If you have so many elements that um so this is all filled. Let me let me draw this differently. Say your array currently contains that many elements.

12:17 Then what this potential charges you is these two distances. How far are you from the upper bound which means if you hit that you have to double the array and you have to pay. And how far are you from the lower bound where also you have to change you have to half the size of the array. That's the minimum of these two gives you the the closer end point. That's your safety distance. How many operations you for sure have to still profit from past work before you have to pay again. And with that potential you can show that all the operations have bounded amortized cost. Namely um the lucky cases when push or pop don't have to change the size. Then you have one array access for modifying that one element and you may lose one of these potential uh units because you're closer now to the boundary.

13:17 And here what we'll have to do is multiply the potential change by a certain uh unit conversion. Uh so in total one array access and one unit of potential works out to five.

13:50 you can play with these constants but um it only affects the overall um the overall cost by some other constant. The interesting operations are the push and pop operations where we have to copy. If we're out of space and we have to double the array. So the expensive push has array completely filled and afterwards it's twice as long. So I'm sitting now here actually one element more. Right? And here is my c / 4. This is my new n primes. Then how much did I did I have to pay? I had to copy all these elements down here and one extra access for putting the new element there. I'm counting that as 2 n + one because I have to read from this array and write to this array. 2 n plus the one extra element for writing this here. That's the actual cost. That's my ci. But I also previously was right here. So my distance my my fi was zero whereas now my phi is this distance the smaller of the two and you can see from the picture it's going to be the smaller to the left and what is that well roughly it's c over 4 and because c was chosen as 2n 2 n /4 is n /2 two and this plus one is because I'm actually moving away from the boundary.

15:33 And if you multiply this by four, you see that the the term with n cancels. And so again, it works out to cost you at most five units in amortized cost. And a similar analysis for pop shows the same thing there. Um you're uh even creating a bit less. So here you're always exactly at this five. But in all cases the operations no matter what happens once you um include the change in this potential they cost only five units of amvertised cost which means if you insert that here you get what is written here. The total cost of all operations is five times m the number of operations over this plus what you get from the initial and final potential. So that uh we're using this upper and lower bound. The potential here by definition is a distance. So it can't be less than zero. And it can also be you can work out that's the the largest it can get no matter where in the array you are. It can't be more than 0.6 six precisely times n. And so the worst is that you have this four times this upper bound as one of the extreal points.

16:55 But that's good enough to prove our theta of m plus n. So if you start with n elements and you have uh m overall operations, your cost will be linear in m plus n.