I am still working through amortized time… I got a bit more understanding of the frequency of resizing arrays. It hasn’t been easy but I am still missing how the average complexity was calculated. I still need to work on this more. Step by step! Never giving up.
TLDR;
Okay, so here are the highlights of what I did:
- Read through some articles in Wikipedia and some lecture notes on Amortized Analysis. I keep trying to rewrite what I read so that I am questioning what I am reading. That has definitely helped me out a lot.
Notes on Amortized Time
An ArrayList is implemented with an array. When the array hits capacity, the ArrayList class will create a new array with double the capacity and copy all the elements over to the new array. So then how can we describe the runtime of insertion? This is a tricky question.
The array could be full. If the array contains N elements, then inserting a new element will take O(N) time. The reason it will be O(N) time is because you will have to create a new array of size 2N (remember the initial array was full), then copy N elements into the new array, and then finally insert the new element at the end of the 2N array. So literally having to perform the insertion operation on every element in the arrayList. That is why the insertion will take O(N) time.
However, we also know that this doesn’t happen very often. The vast majority of the time insertion will be in O(1) time. Well now let’s ask, why does it not happen very often?
In the case of an Arraylist needing to increase it’s size, we can see that as the size of the Arraylist increases, The number of times we need to increase the size of the Arraylist decreases. This is based on the assumption that the Arraylist starts off at a small size (e.g. a size of 4). As we insert values into that Arraylist it’s size will increase to accommodate the new values. In most cases the size increase is in a doubling action (e.g. The Arraylist will go from a size of 4 to a size of 8).
Well, if the size doubles from 4 -> 8 when we try to insert a fifth element into an ArrayList we will be left with an Arraylist with 5 values and 3 empty slots. So we can have 3 more insertions before we must double again to accommodate a ninth value. Now the doubling with take place again to increase the Arraylist size from 8 -> 16. Just like before we have all the previous values plus the new insertion. The Arraylist now has 9 values and 7 empty slots. So every time the Arraylist doubles, the frequency of the doubling action is decreased by half??? (If the table is doubled in size every time it is needed, then the resizing operation occurs with exponentially decreasing frequency.)
Conclusion
That’s all for today. If you are interested in the MIT course you can check out the video lecture I’m currently going through. The lecture is helpful but isn’t sufficient by itself. Anyways, until next time PEACE!