Run-time Analysis allows us to formalize a method of comparing the speed of an algorithm as the size of the input to the algorithm grows. We're going to contrast two different data structures right now. We're getting contrast an array, a sequential chunk of data in memory, and a list which is data linked together through ListNodes. Remembering back to our array, we can access a given index in an array by knowing the size or the width of each piece of data, and then multiplying the width of each piece of data by the index that we want to access. So, it doesn't matter what our index is, our index maybe one million, but since we're only doing the multiplication, we can do this multiplication extremely quickly. It takes exactly one multiplication no matter how much data is in our array. If it's one element, a million elements, or 10 million elements. In a linked list, if we want to access a given index, so, if we want to access index 99, we have to travel through the list 99 times by following next pointers. So, as the size of our data grows, the amount of time it takes to access an average element is going to grow as well. Let's look at a table, we want to access a given element, and we want to access element three. In an array, we can calculate that by simply saying three times whatever the size of our data is, and that's going to take one operation, it's going to take one multiplication. In a linked list, we've got to advance three different link nodes. So, that's going to take three operations to find where our data's at. If we're going to access the 4,285th element, what will then array, we do 40 to 85 times the size. So, this again is one operation. In a linked list, we have to advance 4,285 next pointers. So, we say that's 4,285 operations. If we want to access the one million two hundred and fiftieth thousandth element. Again 1.2 million times the size of, is still only one operation for doing this on a linked list, we're going to be following next pointers for a really long time. This is going to be one million, two hundred and fifty thousand operations. Now, let's think about this in terms of n. If we want to access the nth element, then it still takes n times whatever the size of the data is, so that is still one operation. In a linked list, that is n operations. So, we say that no matter how many elements in the array, we're always going to be able to access nth element in what we're going to call big O of one time. On the other side in a linked list, we're going to take n operation, so we're going to call this big O of n time, and big-O is just a syntax that lets us know that this is how the function grows in time complexity relative to the input. Let's think about a resizing of an array. So, we want to resize an array, one strategy we can do is that every time we need to resize the array, we're going to resize the array enough to put in the next element and store one more element after that, so that we don't have to do this work all of the time. So here, we have an array of six, we need to resize it to eight. So, I'm going to go and copy over this data 2, 3, 5, 7, 11,13, then here into my next prime number 17, and I've left this open space here, so that I don't have to do this process right away again. I've got room for the next piece of data that's coming in. So, I ultimately had to make six copies of our data to our new array, and then I have room for two more pieces of data, one that I use right away. So, this strategy is, that whenever the array is full, we want to add two more to the capacity. So, I'm going to formalize what this takes as our capacity grows to n. Initially, our array is going to start out with a capacity of just two, and this's going to happen in the very first round. Then after the first round, we're going to have to make two copies of our data when we resize this array to be four, and then we're going to have to make four copies when we resize this data to be six, we're going to make six copies, eight copies, 10 copies, and so forth. So, you'll see that we denote the number of copies we have to make at each level until the last level when r is equal to n over two, so, we know that this is going to be n pieces of data, and we're going to have our round of resizing every other piece of data. So, n over two pieces of data which we're going to call r, is going to require two to the r minus one copies. Let's go ahead and actually add up the total number of copies that it takes over the entirety of the algorithm expanding from an initial array of capacity two, all the way down to the when the array is the capacity of two times r. So, here we have two copies, four copies, six copies, eight copies, 10 copies all the way up to two to the r minus one copies where r is equal to n divided by two. Because remember, we're resizing every other time, so n divided by two times. What we want to do is, we want to change this into a syntax, so we can easily add together because two plus four, plus six, plus eight is rough. Instead, in terms of number of resizes, this is going to be two times one, two times two, two times three, and so forth. So here, we have two times one, plus two times two, plus two times three, plus two times four, plus two times five, so the total amount of copies made is going to be the sum of two times k when k is equal to one all the way up to when k becomes r, from k equals one to r, we're going to have two times k, so, this is the total copies. Working out this math a little bit, two times k as you might remember from an introductory calculus class, is going to be two times r, times r is just plus one over two, if we go ahead and cancel out the two's and distribute the r's, we have r squared plus r. So, we have a sum of all of the required copies is going to be r squared plus r copies. So, we know two things, we know that the total number of copies is r squared plus r, and we did this by summation, and we know that the relationship between r and n is, r is equal to n divided by two. So, we can go ahead and substitute r back n for n because we really want to know how much it grows in terms of the number of data or n, we don't really care about how big r is, r doesn't mean anything to our final analysis. So, we're going to go ahead and substitute n for r, and we get n over two squared plus n over two, and the final equation we get is n squared plus 2n divided by four. In Big-O notation, what we want to do is we want to actually just express the largest term without any of the constants. The largest term in this equation is n squared. So, n squared is larger than 2n, its larger than the constant four. We'll drop everything that's not the largest term and Big-O notation is always going to denote the largest term in an equation. So, here we have, that the total amount of time for all of the copies is going to be n squared total time. So, let's see how this differs if we'd use a different strategy. Our other strategy is, let's double the capacity every single time as opposed to just adding two each time. So, if we double the capacity, starting with an array of size two again, the first time we do two copies, the second time we do four copies, the next time we do eight copies, and so forth until we do 16 copies, and eventually we do two to r copies, where r is going to be the logarithm of the total number of elements. So again, doing the summation of all of these things, we have a sum from k equals one to r of to the kth power because this is to the k, to the k, to the cubed, to fourth to the r. We know that this is equal to two times two to the r minus one. Just like before, we have two equations, we have the number of total copies which is two times two to the r minus one, and the relationship between r and n, and now r is equal to logarithm of n. During the same substitutions, we see that if we substitute login for r, we get two times, two to the login power minus one times two, because two to the log n of n is just equal to n itself, we're going to substitute this value for n. So, we have the equation two times n minus one. Here, looking at a dominant factor, we have essentially two n minus two, dominant factor is two n, dropping the constant, the only thing that grows is n. So, we say the total run-time of all of the operations needed, if we're doubling the size of the array, is Big-O of n. This is much less than n squared. So, what we see is if we analyze the run-time, we can see that the strategy actually makes a big difference. Instead of taking n square time two to all of the copies, we take just n time, this is awesome. So, here's an example of where the strategy we use to resizing array makes a difference. So, strategy number one, growing by plus two each time is going to take n squared work. Strategy number two, doubling each time takes O of n total work. Now notice we talked about total work at each point. What we really want to care about is how much work is done every timing insert. If the total work to insert n elements is O of n, and I'm doing indifferent inserts do all that work, then the total work O of n divided by number of inserts I do is going to be equal to O of one, and we call this amortized running time. Because if we look at this diagram, we see that most of the time, looking here between rounds three and four, we see that we've copied over eight elements, then we get a free insert, we get a free insert, we get a free insert, we get a free insert, we get a free insert, we get a free insert, most of these operations don't require any copying at all. Only once every so often do we have to actually then copy over all the data and move forward. But then we can insert all of that data again before we have to do another copy operation. So, the average time on an average operation is going to be O of one time, that on average, resizing array takes a constant amount of time, amortized across the entire run-time. So, let's look at how this all comes together. We looked originally at the fact that we have a table that we filled out at the very beginning of this video, where the access time for an array is always O one, and the access time for a linked list is always O of n. What you've just been introduced to is runtime analysis, and runtime analysis allows us to formalize a method of computing the speed of an algorithm as the size of the input group. You saw two different runtime analysis, you saw the runtime analysis of what it takes to access an element, and you saw the runtime analysis of resizing an array. We summarize runtime analysis in what we call Big-O notation that we leave out everything, but the most dominating term in the equation. So, the most dominating term may either be O of one which we call constant time, that means is going run approximately in the same amount of time no matter how big the data is, for example, looking at our array and getting us particular index out of array runs in O of one time, might run in linear time, as the data grows, the running time is going to grow at the same rate, it's linear or O of n, and then we have O of n squared or polynomial time. This is the total amount of work, for example, if we resize the array by adding two elements at each step, is O of n squared a polynomial time? O going to be much slower than linear time and it's that's going to be much slower than constant time. So, as we do analysis, we're going to want to try and achieve all of one type of fault if at all possible, otherwise, we may see O of n or n squared time. We'll keep looking at some more analysis in the next video, so, I'll see you there.
