[MUSIC] In the previous lecture we saw a simple example demonstrating why algorithms matter when it comes to the speed or efficiency of our programs. Let's look at a second example in a little more detail. Let's say our task is to reverse the elements of a vector. Now of course in MATLAB you can do that easily in multiple ways. But in MATLAB, all easy problems have easy solutions. So for the sake of this example, let's pretend that these built-in reversing methods don't exist, and write our own function. Also, let's forget recursion. First, we need to come up with an algorithm. Let's make our problems slightly more difficult and say that we want to solve this problem in place. That is, we don't want to create another vector and simply copy the elements from one to the other in reverse order. Instead, we want to move the elements within the original vector. Here's an idea. Why don't we start at the second element, save a copy of its value. Shift the first element to the second position, and then copy the save value of the second element back to the first position. So now we've swapped the first and second elements. Then save a copy of the third element, shift the first and second elements up by one. And copy the third element back to the first place. We keep doing this, save the nth element, shift elements 1 through n minus 1 up. And copy the nth element back to the first place. You can see that this approach will indeed flip the elements of the vector. And here's the implementation of this algorithm. It's a step by step implementation of the algorithm I just showed you in the animation. Let's run it. And let's run it on a bigger list. Works like a charm. By now you probably suspect that once we increase the size of the vector our function will slow down. Let's check that out. 15 hundredths of a second to reverse a 10,000 element vector. It's hard to tell whether that's good or bad. But before we go any further, let me show you a better way of measuring the running time of a function. tic, toc gives a good idea of the running time, but it measures the clock time between tic and toc which may include time devoted to other things your computer is doing while running my_flip. A better approach is to use MATLAB's time_it function. To measure the time that my_flip takes, it'll do it as its name says, it'll time it. And it does a better job because it comes closer to measuring just the time used by the function you're evaluating, by reducing the impact of extraneous time for swapping in and out. And housekeeping and stuff that your operating system may decide to do in the middle of running my_flip. That makes it hard to compare functions that don't take a lot of time. time_it uses tic and toc, but to get a better estimate. It runs the function multiple times and returns the median running time, which is robust against a run or two in which the CPU does non-my_flip work. An extra benefit is the time it requires that we give it a handle to the function we want to time. So we get to practice what we've learned about function handles, and it gets better. time_it does not allow you to include arguments for the function you're testing. I have no idea why it doesn't, itt causes problems and I've complained to Mathworks about it, but nevertheless it doesn't. As of today, time_it evaluates only functions that take no arguments. So how are we going to time my_flip, which does require an argument? Well, here comes the anonymous function to the rescue. Here's how it works. If you forgot this syntax, I don't blame you. I have to look it up every time. The @ operator followed by empty parenthesis creates a function handle to an anonymous function. That is a function with no name, that takes no arguments. The body of the anonymous function must be just one command, which in this case is a call to my_flip, with the vector 1:1e4. So timeit gets what it needs, a function handle to a function with no input argument. And we get what we need, call of our function with an input argument. It's brilliant? I bet when you learned about anonymous functions, you said yourself, what on earth is this aberration? When am I ever going to use this weirdness, or words to that effect. And here we go just a couple of weeks later, suddenly we can't get along without it. So let's run it again, but this time let's save the output in a variable. T10 by the way means 10,000. Okay, let's time it with 100,000 numbers on the list. This is going to take quite a while. And one reason it's going to take quite a while is that as we said earlier, timeit actually runs my_flip several times to get a more reliable number. And it gives you the median of the time elapsed. So I'm going to compress time for you. I'll let it run and then I'll be back in just a few seconds. Well, more than a few. Okay, we're back and it took about 40 seconds for this thing to run. And you can probably hear my fans running a little louder. But the elapsed time that it calculated for my_flip doing 100,000 numbers is 14.1923. So a little over 14 seconds. Well, that seems slow for MATLAB doing a job this size. I mean hundred thousand numbers sounds like a lot, but it's not a lot for MATLAB. We've done more complicated stuff than this on larger data in much shorter times. But what's maybe more interesting is this. We increased the size of the vector by a factor of 10, but the time needed to completed the job increased by a factor of right out 100. That seems odd. Let's try some numbers in between 10,000 and 100,000, maybe 20,000 and 40,000. And here's 40,000. And again, I'm going to let you get away with not waiting all the way through this. It took a little under 30 seconds to come up with an average of 2.27 seconds. And let's check their ratios to the original time. So when I doubled the size of the input from 10,000 to 20,000, the time grew by a factor of about 4. When I quadruple the size of the input the time grew by a factor of about 16. It seems that there's a quadratic relationship here between the growth of the number of elements, and the growth in time required by our algorithm to calculate the output. The question is, why? Let's see if we can get an idea of why the time grows like that by looking at our function a bit more closely. There are two nested loops here. The outer loop visits all the elements except for the first one. So if the length of the input vector v is n, the outer loop will execute in n- 1 iterations. If we double the length of the vector v, this loop will execute in approximately twice as many iterations. What about the inner loop? That's a bit trickier because it starts at the current value of the outer loop index, ii, and goes down to 2. So the inner loop is going to carry out a different number of iterations every time it's executed by an iteration of the outer loop. For the first iteration of the outer loop when ii is equal to 2, the inner loop will start at jj = 2. And stop right there, just one iteration. For the second iteration of the outer loop when ii is equal to 3, the inner loop will go from jj = 3 to 2, so two iterations. For the third iteration of the outer loop, when ii = 4 the inner loop will do three iterations, and so forth. With the number of iterations of the inner loop increasing steadily from 1 to n- 1. So the average number of inner loop iterations is just under one-half n. We just want to get an idea whether quadratic growth makes sense. So if the outer loop iterates, about n times, and the inner loop iterates an average of about n over 2 times for each of those in outer loop iterations. The total number of inner loop iterations will be approximately n times n over 2, which equals n squared over 2. In other words, the number of times that v jj is set to v jj- 1 is approximately proportional to the square of the number of elements in the input v. Note that this calculation tells us nothing about how many seconds the function will run. That depends on many factors including the kind of computer we use, and also how long each of the elementary steps takes. But the actual execution time for one particular run of this algorithm is not as important as the trend and that runtime as the size of the input increases. Here's the key concept from this lesson. What this kind of algorithm analysis tells us, is how the execution time depends on the input size. In this case, we can conclude that there is a quadratic relationship. Doubling the input size will increase the execution time approximately fourfold. We can use this type of analysis to decide whether our algorithm will perform well enough for the task. If we know that the largest vector that we need to work with will be 100,000 elements, then anything less than one minute is acceptable. This algorithm is okay. But if our problem size could be large as a million, we know that our current solution will take somewhere in the neighborhood of 20 minutes. If we need this to work for vectors with 10 million elements, then we'll need over a day and a half for it to finish. Thanks to our analysis of the algorithm, we can run a few small problems, and then calculate what will happen for the biggest problem. We don't have to try it and wait. If our algorithm analysis tells us that our approach will take too long, then we know that we need to find a better solution. While we're on the subject of a better solution, you've probably already figured out that there is a much simpler algorithm to flip the order of elements of a vector in place. We can simply swap the first and last elements, and then the second and next to last elements, and so on, until we reach the middle point. Here's an implementation of that algorithm. Just one loop this time with the number of iterations equal to about half the size of the input. And these three lines do the swapping, using the standard approach of saving one value temporarily In this variable name TMP during the swap. Let's see how fast this function gets the job done. I've written a function to help with that called test_fast_flip. It starts by constructing a list of 10 vector links spread uniformly from 1 million to 10 million. And it calls timeit with vectors of these lengths. Prints the vector lengths, And the times and then plots execution time versus vector input size. Let's run that. Wow, 10 million numbers reversed in under five hundredths of a second. That's a little bit better than my_flip which took a leisurely 14 seconds for just 100,000 numbers. So this second flipping algorithm is simpler and faster. And as you can see from the plot, The time is roughly a linear function of the input size. There's a little bit of startup time on the order of 5,000th of a second. And then the calculation time itself is very linear with a little fluctuation because timeit doesn't completely eliminate the system's use of the CPU for other purposes. And is this linear behavior what we would expect for this algorithm? Well, it has a single for loop and runs for about half the length of the vector as we mentioned. So the number of iterations is approximately proportional to the size of the vector. Furthermore, each iteration does the same three calculations. So each iteration takes the same amount of time. Therefore, yes, we would expect the time required to be linear in the input size n. Could we do better than linear for reversing in place? Square root of n maybe, or a log of n? No, we have to move each element. So there's a little room for improvement for this algorithm. Nevertheless, the built in MATLAB function still does better than our solution. Under three hundredths of a second instead of our slow-pokey five-hundredths of a second. Why is it better? Well they use a similar algorithm, that's also linear. But the built-in functions are really optimized to work as fast as possible using low level features of your computer. In fact flip has many other built in functions of MATLAB, it's not even implemented in MATLAB itself. Let's look inside that function. Hmm, nothing but comments. There's no MATLAB to show you because it doesn't use MATLAB commands. So why the comments? Well, this is just the text you see, when you type help flip. This is the same as this. And so we've done what we promised. In this second part of our study of algorithmic complexity, we've looked in more detail at the effect on execution time on the algorithms that we use to solve a problem. Instead of merely saying one algorithm is faster than another, we've analyzed the algorithms to determine how their execution times depend on the size of the input data. We looked at two algorithms for reversing the elements of a vector, where the size of the input data equals the number of elements of the vector. The execution time of our first algorithm was proportional to the square of the size. For the next algorithm, it was proportional directly to the size. This seems like a trend. How about an algorithm whose execution time is proportional to the size raised to the 0 power? In other words, proportional to the number 1. Is that even possible, does it even make sense? Guess you'll have to check out Algorithmic Complexity Part 3 to find out. And when you do, you're going to find out a whole lot more about this subject. [MUSIC]
