In the previous lecture, we saw an algorithm with quadratic time complexity and an improved version with linear time complexity. Well, I may not have said it in quite that way, the term time complexity is a fancy way of saying how the estimated execution time of an algorithm scales with its input size. The word complexity is not used here in the vague everyday sense. When a newscaster talks about the complexity of a NASA launch, now we're applying the word strictly to algorithms. For one thing, when we say complexity, we mean computational complexity, or more specifically, algorithmic complexity. It's finally time for us to fulfill the promise we made at the beginning of this lesson, to give you a more precise definition of complexity. Of course, we also promised that we would do that in short order. Well, we failed you there, but by now you probably know that we don't know how to do anything in short order. We mentioned that there's an entire branch of computer science devoted to analyzing the performance of algorithms. Well, now that we've analyzed a couple of example algorithms, we can get more precise. Computer scientists use a special notation to describe algorithmic complexity, which we'll abbreviate simply as complexity, and it's called order notation. We're going to show you examples of this notation in this table as we go through this lecture. For example, our first vector reversal algorithm, which we implemented in the function named my flip had a time complexity of N squared, which means that if the number of inputs equals N and N is large enough, the execution time becomes approximately proportional to N squared. Because it's only approximately N squared and because the approximation gets better with larger N, we say that the algorithm is of order N squared, which is written in this way. If you want to sound like a professional algorithmist, which is a person who designs algorithms and determines complexities, you can say that the algorithm has order N squared time complexity, or that this is an order N square algorithm, or that the algorithm is order N square. The reason for saying time complexity instead of just complexity, is to emphasize that we're talking about the amount of time the execution takes instead of the amount of memory space. The space measure is not used as much, but algorithmists do study that too. Our improved vector reversal algorithm which we implemented in fast flip, had order N time complexity which is also called linear time complexity. You can say it's an order N algorithm or a linear algorithm. The branch of computer science dedicated to the study of algorithmic complexity is called complexity theory or analysis of algorithms, or just algorithms. If you happen to be one of the theoretical computer scientists in this field, then we know two things about you. Number 1, you're horrified at how sloppy our treatment of your field is and 2, you've have somehow clicked on the wrong course, you'll probably want to get a refund. But our goal is not to advance the field of algorithms, our goal is to give our students a practical field for algorithmic complexity that you can use when solving problems in your work or studies. We don't have the time or the need to treat the subject with mathematical rigor. All right, back to our topic. We were quite happy with our linear solution to the reversal problem, and we said that we can't do better. But are there any problems where we can do better than order in? Yes, there are. Consider the problem of computing the sum of the first N positive integers, like say, from 1-100. Without looking at the actual implementation of the built-in sum function, we can be pretty sure that it's linear. It performs N minus 1 additions. That's because the sum function is general, it adds up all the elements of a vector no matter what they are. However, the problem that we're solving is more specific, so we can use the extra information that we're dealing with the first 100 integers. Legend has it that Carl Friedrich Gauss figured out this approach when he was just seven years old. If we add up the first and last elements, we get 101. If we add the second and the second to last numbers, it's also 101 and so on. We have 50 such sums, so 50 times 101 is 5,050. We have an analytical formula for any N that gives us the solution. Mr. Gauss is a pretty smart cookie. By way of comparison, I didn't hit on this solution till I was nine. That two-year head start might explain why Gauss is one of history's most celebrated mathematician, astronomist, and physicists, and I'm teaching a course on MATLAB. The interesting thing about this method though, is that the solution doesn't depend on the size of the input. Whether n is 100 or 100 million, it'll take approximately the same amount of time to solve the problem. Such problems are said to have constant time complexity or we can say that they take constant time. Of course, we could also argue that the size of the input for this problem is just one, for example, the number 100. It's also linear time, just saying. While we're on the subject of formulas, there's a formula for the nth Fibonacci number 2, so you can calculate that in constant time. It's an amazing formula because it uses irrational numbers to calculate an integer. You can look it up. But in practice, we rarely get so lucky. The time complexity in most problems is going to depend on the size of the input. But are there problems whose algorithmic solutions have a complexity somewhere between constant and linear time? Yes, there are. Consider searching for a number in a vector. More precisely, the task is to return the index of the first occurrence of a given value in a vector of elements. As usual, there's a built-in function that we could use. It's called find. It's not quite all we need for this task because it doesn't actually search for a given value. Instead, it returns the indices of the first K non zero values, where K is the second argument. But we can use a logical vector to make this work for us anyway. First, let's make a row vector with 20 integers selected randomly from the range 1-100. Now let's find the index of the first occurrence of the value 28. But again, our goal is to illustrate a point, so let's forget that there's a built-in function that we can use. Here's our own search function. It loops through the input vector using the loop index ii to pick out individual elements and compare each one to the search value e. If it finds one equal to e, it sets the output argument named index to the loop index and returns. To handle the case in which the search value is missing from the list, it presets index to zero as a flag, meaning not found. Twenty-eight was too easy. Let's search for 98 and 900, which isn't even on the list. It works. Just by looking at the for-loop, we can conclude that this algorithm has linear time complexity. The loop can visit all of the elements in the vector. For example, when the element we're looking for is not in the vector and so it takes n-time. As a side note here, usually when we look at time complexity, we consider the worst case. That's because if we want to have assurance that our algorithm won't run for a long time no matter what the input data is, we have to look at the worst possible combination to make sure. In this case, the worst case is when the element is not there, because it forces the algorithm to examine every single element hence the linear time complexity. But I promised you something between linear time and constant time, didn't I? Well, what if the vector was sorted? Let's say it's a sorted vector in increasing order, then can we come up with a better algorithm, that is a faster algorithm for finding a number in a sorted list? Most of you are probably old enough to remember what a phone book is or was I guess. I haven't seen one in years. But in any case, the phone book has the names in alphabetical order. If you're looking for somebody with last name of Moore, you're not going to start on the first page, are you? No, you'd probably start somewhere in the middle. If you open up the phone book at, say, the letter R, then you'd probably go back 100 pages or so. If you end up with the letter L, you know you have to move forward some. Soon enough you'll find M and then Moore. But you're definitely not going to thumb through every single page from A until you get to Moore. We're going to use the same technique to find the number in a list of numbers stored in a vector. It's called binary search because at each step we, break our list up into two sub-lists. The part that comes before the element we're looking at, and the part that comes after it. That element tells us which one of these sub-lists to continue searching in. The only difference between looking for a name in an alphabetical list and a number in a sorted list is we don't have any idea how the numbers are distributed in our vector. We can't guess where to start in order to be close to the item we're looking for. In the phone book, if the last name is Zhang, you need to start near the end. If it's Baylor, you'd start near the beginning. But if we're looking for, say, the number 100,000, we have no idea whether it's near the end or near the beginning, or in the middle, even if they're only 100 numbers on the list. We'll start right in the middle. If we overshoot, we'll go back halfway. If we're now under, we'll go a fourth of the way forward. Basically at every step, we cut the size of the list in half. For simplicity, we're going to also assume that each number in our vector is unique. That is, there are no repeated entries. The reason for this assumption is that if there are duplicate entries, this algorithm is not guaranteed to find the first occurrence. It'd be easy to fix that, but that's not our goal here. Here's a function that implements the binary search algorithm. As you can see, we've chosen a recursive implementation. I'm not going to give a detailed analysis of it, but here's where it calculates the index into the middle of the list. Here's where it calls itself recursively to search the first half of the list, and here's where it calls itself recursively to search the last half of the list. Feel free to pause the video and study the function. It's also available from the course website. The key point is that every recursive call deals with a half-sized problem. Let's compare run times of the two versions on the worst case; the sequential search in the function my_search, and this algorithm. First, we'll put the integers one through 100 million on the list. Then we'll search for zero, which is the worst case because it's not on the list. As you can see, the binary search is much faster. In fact, it's about 80,000 times faster, over 80,000. Let's make the difference even more obvious with a billion element list. I cut out some of that time for you because it took about 40 seconds. You can probably hear that my fan has speeded up a little bit. Binary search doesn't take nearly as long. Let's calculate that ratio. This time it's about 460,000 times faster. Increasing the size of the vector tenfold, increase the execution time for my_search about 10 times, which makes sense because it goes through the entire list sequentially, and the list is 10 times longer. But binary versions time increased by about a factor of two. Although it's not surprising to see that the binary search time as measured by timeit increased by a smaller factor than the sequential search time, and is much less than the sequential search time. The advantages are probably even greater than what we're seeing because for extremely quick executions like the binary search, timeit overestimates how long it takes, because operations competing with binary search dominate the execution time. But still the ratio is impressive, almost half a million. But why is the binary search so much faster? Well, by cutting the problem in half every time, only a few steps are needed to cut down the list to a length of only one element. How many steps? Well, if you think about it, it's about equal to the base two logarithm of the length of the vector. For example, 1,024 is 2_10. If we have a list of length 1,024 and we keep splitting it in half, we'll get to a one element vector in 10 steps. For a billion element list, we'll get there in 30 steps. Such an algorithm has logarithmic time complexity or order log N. If we use the sequential search algorithm on a one billion element vector looking for something that's not on there, we need to take a billion steps. The binary search on the other hand would need only 30 steps. That's a ratio of 33 million. Now, wait a minute. When we ran the two versions on the same billion length vector, we got a ratio of only 465,000. How come? Again, these kinds of analysis are not good for predicting the time ratio of two different algorithms on the same input. They just tell you how the execution time of a given algorithm scales as a function of the input size. In this particular case, the binary algorithm is so fast that timeit can't give a totally reliable measure of its execution time. But even if it could, it's important to remember that a step in one function may take longer than a step and another function. For example, a step of the binary search function includes a function call. That requires all that stack manipulation that we talked about in lesson 2. That complication makes a given step in a binary search take considerably more time than a step in the iterative my_search. In general, an algorithm with better time complexity may be more complicated than one with worst time complexity. Even though it would need fewer iterations, each of those iterations may be much more time-consuming. That may mean that for small input sizes, a higher time complexity algorithm may be faster. It's more useful for small problems than one with lower time complexity. If your input sizes are relatively small, it may ironically be more practical to use the algorithm that has worse time complexity. I guess it's kind of surprising to hear that after we've dragged you through all this complexity stuff, right? But it's certainly not as surprising as the fact that I have managed to work the word ironically into a course on MATLAB programming. But you always have to judge for yourself whether a function you wrote is fast enough for the particular inputs you have. Even if an algorithm with better complexity is faster for the problem size you have, it still may make sense to use an algorithm with worse complexity. That's because algorithms with better complexity are often more complicated and take much longer to write and debug. For example, if the slow algorithm takes a minute or even 10 minutes to calculate what you want, but you only need to use it once or twice, does it really make sense to spend hours coding a more efficient solution to save 10 minutes? Of course not. In that case, the worse algorithm is the better choice and the more ironic choice. Man, the adverb and the adjective, can the noun be far behind? So there's no free lunch. To save computation time, you have to spend more programming time. It's a trade-off. If the savings is great enough and the function will be used enough, then it makes sense to put the programming time in to save computation time. But the irony is that an inferior algorithm may in fact save time overall. There's your noun. But there's no such irony to the binary search. It's not only lightning-fast, but it's easy to program. If your list is longer than 10 numbers or so, it's definitely the way to go. Well, that's the way to go if the list is sorted, but it's no good at all on an unsorted list. In that case, your only choice is to plod through that list item by item with sequential search. Sure, it's order N instead of order logN, but if the list is unsorted, what are you going to do? You're stuck with linear plodding. What about this idea? Maybe we could sort the list first and then use that lightning-fast binary search. Well, that's a good idea if you need to search for lots of numbers on that list. But it's a bad idea if you need to find just one number or just a few numbers because sorting the list takes longer than sequentially searching the list, even for short lists. It gets worse for long lists because the time required to sort the list grows faster than the time required to sequentially search a list. There are many good sorting algorithms available. But for general sort, the most efficient algorithms are all order NlogN. That's not as good as the order N complexity of that plotting sequential search. So far, we've seen algorithms with constant logarithmic, linear, and quadratic time complexities; and we've learned that general sort algorithms have NlogN complexity. We can do better than constant. But are there some problems whose best solutions are worse than quadratic? Yes, indeed. The best solutions to many important problems have worse, many times, much worse time complexity. In fact, there are problems that can't be solved in the world's fastest computers in a reasonable time at all, no matter what algorithm you use. Let's consider one, the traveling salesperson problem. Given a country with many cities and various roads connecting the cities, what's the shortest path a person could take to visit each city and return home? The simplest worst case is when the shortest road connecting each pair of cities doesn't pass through any other cities. It's easy to see that trying out all permutations would require N factorial steps, which is much worse in order N squared. It would become impractical for even 20 cities. Better algorithms have been found, but the best is still no better than order 2_N, not N_2. Mind you, I'm saying 2_N, and what a difference that makes. So for 10 cities, instead of 100 steps, 2_N is 1000 steps. For 20 cities, it's a million, for 30 cities, it's a billion. You say, "Who cares? Why is this an important problem? Can we just give the salesperson a cell phone?" Well, sure we can. The traveling salesperson problem is just a model. It turns out that many real-world problems follow the same model and have no solutions with complexity better than 2_N. If one can solve the traveling salesman problem efficiently, many other problems would be solved as well. For example, FedEx, DHL, UPS, and every postal service in every country need to decide which package should go on which truck and which route they should take in order to make sure everybody gets their packages by the promised date and minimize the fuel use and the driver hours worked every single day. This is very similar to the traveling salesperson problem. These companies are running computer programs to come up with these routes and schedules. But guess what? They never find the best solution, or if they do, it's just luck. There's simply not enough computers and time to get the optimal solution. Instead, their programs use approximations to find good enough solutions. If a clever programmer improve the solution of these algorithms by just one percent, that would save millions of dollars for these companies every year. Now you know why computer programmers make the big bucks. Well, we've now looked at problems with the sixth time dependencies that are most commonly taught when introducing algorithmic complexity. Three of them are powers of N, and since powers of N are examples of polynomials in N, they are said to belong to the set of complexities that grow in polynomial time. Two of these complexities involve the log of N. If you're wondering why we don't show the base of the log, that's because changing the base is just the same as changing the constant C. The base has no effect on the complexity expression. The worst complexity of the six we considered 2_N is an example of a category that's said to grow in exponential time. We can stop with these six. But we're going to squeeze in the complexity of one more problem because it's of fundamental importance to MATLAB, whose name means Matrix Laboratory. That problem is matrix multiplication. For the sake of simplicity, take an M-by-M matrix and multiply it by another M-by-M matrix. The result is going to be M-by-M as well. To compute the value of the single element of the output matrix, we need to multiply each of the elements of one row, the first matrix by the corresponding element of one column of the second matrix. That's M multiplications, and we sum up the results with M additions. How many output elements do we have? Well, M squared. All together, we need to make M times M squared, which equals M cube multiplications, and the same number of additions. That sounds like an algorithm with M cubed complexity. Indeed, it's customary to state the complexity of matrix multiplication in terms of the matrix dimension as being order M cubed. But to be fair to the algorithm, we should remember that the number of inputs N is itself equal to 2M squared. In terms of the number N of inputs, the number of operations is actually proportional to N _three-halves. That sounds more like N_three-halves complexity, and indeed the algorithm is order N_three-halves. It belongs here in the table because it's slower than N log N, but faster than N squared. Even though N is raised to a power that's not an integer, it's a polynomial time algorithm because algorithm must include all positive powers of N in the polynomial time set. Here's an implementation called matmul. We'll confine our testing of matmul to square matrices, but it works on general matrix shapes. It starts by examining the two inputs to make sure they're compatible matrices, and then comes the computation work. The telltale sign as far as complexity is concerned, is that we have a set of three nested for loops, each of which runs from one to one of the dimensions of one of the matrices. If each of the matrices is M-by-M, and this line right here is guaranteed to run exactly M cubed times. To test it, I've written a function called TEST_MATMUL. This tester has a couple of options, but we'll ignore that. You can study it yourself if you're interested. But when you run it with just one argument, which is a list of matrix dimensions, it'll form pairs of square matrices of those dimensions, feed them sequentially to matmul, and then time it on each pair. Finally, it plots the time versus M cube, and to make it easy to look at the resulting plotted time points and decide whether the plot is proportional to M cubed, the function also plots a dashed best fit straight line. If the time is indeed proportional to the cube of the dimension, then uploaded runtimes will lie on that line, or at least very close to it. Let's call it with seven dimensions. Starting with 100, going to 200, 300, and so on, up to 700. The last one of which I've already determined will run in a second and a half on my MacBook Pro with 3.1 gigahertz, Intel Core i7 processor. I'm not going to make you wait for all this. But here's our result. This is the time on the y-axis. This is M cubed on the x-axis. Friends, this looks pretty linear to me. Our experiment bears out our analysis of the algorithm. It's proportional to M cubed. Surprisingly though, you can do better than M-cubed. In 1969, a German mathematician named Volcker Strassen published a matrix multiplication algorithm of order M_2.8 power. As we mentioned, lower complexity typically comes at the price of more complicated steps which are also more time-consuming, and that's true for Strassen's algorithm as well. But if the problem gets large enough, lower complexity will eventually run faster than higher complexity. For matrices of dimensions greater than 100 by 100, Strassen's algorithm can for some implementations be faster than M-cubed algorithms. Its drawback then is that it takes a lot of memory. But that's not the end of the story either. Strassen got the ball rolling in 1969 but in the subsequent 50 years, researchers pushed the exponent down until the reigning champion as of now in early summer 2020 comes in at M_2.373 power. Unfortunately though, the champ's highly complicated steps takes so long that it's slower than the current M-cubed implementations for any matrix that'll fit in a computer's memory. What about MATLAB's algorithm? MATLAB itself uses an order M-cubed algorithm, but not the naive version we use in MATMUL. Like flip, which we talked about at the end of our previous lecture, is not written in MATLAB. It's also optimized to use lots of features of today's modern micro-processors, such as carrying out more than one multiplication at a time. Get ready for the amazing performance of MATLABs matrix multiplication, 0.0044 seconds. Well, that's considerably faster than the 1.5 seconds we got with MATMUL for a problem of the same size. That's 340 times faster. Let's see how it's time depends on matrix size. To do that, I'll go into test_matmul and change the operation that we give to time it here from a call of MATMUL to A*B. Let's test it with the same input. Well, now it's pretty fast. If I look at the plot, that looks pretty much like M-cubed. It's a little more uneven because the times are so short but that looks like M-cubed to me. Both the built-in MATLAB multiplication operator and our MATMUL show approximately order M-cubed behavior. But this is a good reminder that complexity analysis doesn't tell how fast one algorithm is relative to another on a given problem. It tells you only how execution time varies as the size of the problem grows for a given algorithm. With this brief study of the complexity of matrix multiplication, we bring our three part, introduction to algorithmic complexity to a close. The study of Algorithms and Algorithmic Complexity is fundamental to computer science. It's required in the pursuit of any Computer Science Major and it's considered to be distinct from the study of Programming. Our purpose in introducing complexity within this course on programming is to help you analyze solutions to computationally intense problems. A basic feature of that analysis is Order Notation. In these three lectures on algorithmic complexity, we've analyzed several examples in terms of that notation, culminating in Matrix Multiplication, which is an operation of fundamental importance in MATLAB, and we've organized them in a table from best to worst. We've looked at polynomial algorithms, log N and N log N algorithms, and exponential algorithms. However, we also noted that for smaller problems, better complexity may not be the better choice, because an algorithm with better complexity may in fact run longer than worse complexity solutions on a small problem. Even if it's faster, it'll typically take more programming time. Our goal is to give you an introduction to algorithmic complexity, and we've done that. But there's far more to this subject. If you're interested to learn more, there are many excellent textbooks dedicated to it. Look for titles that include the word "Algorithm". Look inside and if you see 'Order notation", then you're in the right place. But it's time for us to shift from the lofty study of algorithmic complexity, to looking at practical ways to speed up your code. We'll do that in our next lecture which is entitled "Efficiency in Practice."