CS50 for Business - Lecture 1 - Analyzing Algorithms

Hello world. My name is David Malan, and in this lecture we'll analyze algorithms, step by step instructions for solving some problem. Among today's problems, searching, sorting, and more with CS 50's own, Doug Lloyd. Alright, so this is analyzing algorithms and before we start to analyze algorithms, it's probably a good idea to actually discuss what an algorithm is. So algorithms are processes that are designed to complete a specific task. Now you may not have called it by this name in the past, maybe you've referred to it as a recipe or a routine. That's basically the idea for what an algorithm is. Uh, you're just trying to complete some task that you go through every day. So for example, you might have a morning routine or a morning algorithm as I do. I turn off my alarm on my phone and then the first thing I do is play a game of Wirle. It's a way to wake up my brain in the morning. And even going through the process of solving awle is someone's routine or there's an algorithm for doing it. Most folks who do so choose a starting word and always will go off of that word and then you go step by step iterating through trying to solve that puzzle. That is an algorithm. Algorithms complete specific tasks. They also have well defined inputs and outputs. So for example, let's go back to the idea of a recipe. If you're trying to make scrambled eggs for breakfast, you have all of your ingredients at the beginning and you're trying to accomplish some objective at the end, namely a nice warm plate of scrambled eggs. In order to do so, you need to go through a sequence of steps that are clear and ordered. And unambiguous, so you don't, for example, when you're making scrambled eggs, put your eggs in the pan immediately. First you have to crack the eggs into a bowl and then add seasonings and add whatever else you'd like into your eggs, turn the oven on, and you're going through these steps in a particular order because if you do things out of order. You end up with a cold pan or eggshells in your breakfast, which is probably not ideal, and so that would be an example of the basics of an algorithm towards making scrambled eggs unambiguous, ordered clear instructions to complete a specific task and ideally this algorithm does not go on forever. This does not, for example, though, preclude the opportunity to repeat something over and over. So if you're, for example, having an algorithm to count out numbers out loud, the algorithm might be say the number you're starting at. So let's say we're starting at 00. The next step could be add 1 to that number in your head, say the next number out loud, and you go back and forth through those two steps over and over. The algorithm itself has a finite number of steps in this case to add 1, say the next one out loud, but this algorithm will run forever. So algorithms can be take an infinite amount of time to run, but they have a finite number of steps associated with them. So now that we have this idea of what an algorithm is. A set of instructions for completing a task with the caveats we just discussed. Let's talk about how we analyze algorithms in a computer science context. There are basically two ways that we will do so. The first is based on how much time that algorithm takes to run. And we're gonna discuss this at length in a little bit, but we care about how long it takes some process to run, and we may find, we'll certainly find today that there are several ways to do the same thing that take different amounts of time. The other way, which we've talked about a little bit today, is how much space or how much memory on your computer this algorithm takes up, and sometimes we'll see that trade-off can be very important. We may take up far more memory on our computer in order to save time doing something. Um, the reason there's a bit of a catch here which is that we don't exactly use time as a metric because different computers had different processors. The first computer that I got when I was a kid in the 90s was a lot slower than the computer that I have now, and the same algorithm, same code or some same process running on both of those machines

would run at very different amounts of time. So instead of using time literally like seconds, minutes, hours, we instead consider how many steps an algorithm might take and in particular we care about how many steps an algorithm might take as the data set that algorithm applies to gets bigger and bigger. So we care about what an algorithm will tend to do as some huge data set is thrown at it. To give us a sense of how it will generally perform because again different processors, different computers are all going to handle things slightly differently and so we only care about the general idea, the general number of steps it might take without focusing too heavily on literal minutes and seconds. There are also different situations that might come up when we're analyzing algorithms. Something a data set that we have may not be the cleanest. It best option available, or organized in a way that is very conducive to what we want to do. And so we have to consider what if this is, this data is just in the worst possible shape and we need to do something to it. And what if this data is in the best possible shape and we need to do something to it. The run times or how long it takes or how many steps it takes to deal with that data may vary based on whether that data is in good shape or in bad shape or worst case and best case and these terms, by the way. If you have done any other study in computer science or if you have any formal training in mathematics, these are actually kind of, kind of loaded terms. They have particular meaning and so when we're discussing worst case and best case scenarios, those terms do actually are sort of terms of art in the formal study of algorithm analysis, but we're gonna use it in more of a layman's terms context today. And um whenever we're talking about an algorithm, algorithms are always operating on some data, some inputs, and yielding some output, and we use the letter N or the variable N to represent the size of the data that we are, uh, we are working with. So you'll see that term the letter N, mathematical variable N come up a lot. All right, so I mentioned that we have this concern about what data will tend to do, and I want to illustrate this by way of pointing out a couple of algorithms whose run times or how many steps they take. I've completely made these up, but it's to illustrate a point about why we care about what an algorithm tends to do and how we will use terminology. To describe what this algorithm tends to do over time. So let's just imagine for a second that we have these three algorithms. Again, I've made them up. We're never going to get into this level of detail. This first algorithm in this first column here runs in N cubed time. We'll start, we'll describe it that way, which basically means it takes N cubed steps to run. The second algorithm N cubed plus N2d, again, we're just completely making this up. It's going to illustrate a point in a moment. And the third one is that funky mathematical expression over there. Um, Let's see what actually happens or how many steps these algorithms might take over time. So if we have a data set of size 1, for example, this first algorithm will run in one step. 1 cubed is 1. The second one will run in 2 steps, and the third will run in 13 steps. So suddenly this seems like this last algorithm is pretty bad, right? It seems that way because it runs it takes 13 times the amount of time to run compared to the first one. Now with the computers these days, they can perform billions of operations per second. So we probably won't ever notice this, but you can imagine a situation where You would notice some, uh, if we were talking about a computer, some general algorithm, you would notice that amount of time. As the data set gets bigger though, things change. So that's why we don't care about N as a particular value. We it scales because now if our data set is a size 10, the first one takes 1000 steps, the second takes 1100 steps. That's probably roughly the same, but now the third algorithm, which was the worst by far at size 1 is actually better. It only takes 400 steps to run. So again we're seeing differences here, but as we get even bigger, so now we talk about a 1000 size data set. This takes a billion steps. That's a lot. and a million steps. That's a lot, but that's not materially different from what a billion steps is, and this takes just shy of a billion steps. This is 992 million steps. So what we're seeing here is that as this data set

tends to get bigger, the algorithm tends to stop caring about this term. And these terms, it's really the N cubed term that matters. And so when we say an algorithm runs in N cubed time, what we usually mean by that is that that's generally the term that's going to dominate how long or how many steps it takes to do something. We don't concern ourselves with lower order terms like N2, and we don't concern ourselves with constant factors because those lower order terms don't contribute. As much to how many steps something takes to run, and those constant factors can be eliminated by having faster processors or having more powerful machines that analyze this data for us and just to really hammer home the point here, if we had a data set of size a million. Uh, this is, if my math is correct, 1 quintillion, it's a very large number. Uh, this is 1 quintillion and a little bit more, and that less. So all three of these algorithms on small data sets, we see very big ranges in what they can do or how long it takes them to do whatever they're doing, and again we just made these up. But as the data set gets bigger, they all tend to take exactly the same amount of time and that is the language that we use to discuss uh. Run times of algorithms is what they tend to do as the data set gets bigger and bigger. So for all three of the algorithms that we just talked about on the preceding table, all of those generally as we saw as those numbers got larger, tend towards running in what we would call N cubed time as that data set gets bigger, that is generally how many steps that algorithm takes to run. Uh, if those times that we just discussed represented the worst case scenario run times, uh, we may describe them as big O of N cubed. Uh, big O is on the order of, and we would describe that as in some ways an upper bound on how many steps that algorithm would take again in the worst case. And conversely if they represented the best case scenario. That would be represented with this symbol omega here omega of N cubed as the lower bound on how many steps it may take for that algorithm to run. And so that's how we would describe algorithms using time. And one way that we can classify an algorithm is based on its running time and there are different. Sort of categories of running time that we might consider. So for example, and these are in increasingly how long or how many more steps they may take to run so we could have an algorithm that runs in constant time. We may describe that as being an O of one again in the worst case 0 of 1. Uh, that is an algorithm that is irrespective of the size of the data in question, it's just going to run in one step or 4 steps or some constant number of steps. Logarithmic time, O of log N, and if you're mathematically inclined, you can imagine there's a little subscript number 2 there, of log to the base 2 of N because computers typically work in binary and so we care about the number 2 quite a bit. Uh, that is an algorithm that would be proportional to the logs, the base 2 of N, so we're basically dividing a problem in half repeatedly as a way to think about it. So the number of steps is maybe going to be quite a bit smaller than having to consider every single element, which would be the case of linear time or an algorithm that runs proportional to the size of the list in question, the size of the data set in question. And we get increasingly more steps are more involved from this point on log linear time, O of N log N. we'll talk about that a little bit later as well. Polynomial time, O of N to some constant number, so N squared would be quadratic time, sort of a special case of polynomial time exponential time, those numbers are reversed so instead of the constant is in the base and the number of elements being. Operate on in the exponent this is starting to get into really rough territory. This is gonna be these algorithms are gonna take a lot of time to run. They're generally to be avoided if at all possible factorial time O of N factorial. And then there are actually cases, and we may see one a little bit later, of algorithms that may take infinite time in the worst case, and we would have to categorize those as being unbounded. Uh, there is theoretically infinite amount of time it may take to run and perhaps. You have heard of this problem in computer science famously known as P equals NP or the problem is, does P, in this case P being polynomial time equal NP, which is short for nondeterministic polynomial time, that's going to be a subject for another day. We'll leave that one aside. But if you happen to be in a position to solve that problem someday, which comes with a $1 million prize, try to remember where you learned of this concept for the first time from. I want to just take another second to show how some of these run times can really explode

uh, as we get into the really, really rough ones. So again, a data set of size 10. If it runs in log N steps, that's only 4 steps, and would be 10, and logn 40, so you can see that these get worse over time, and factorial with just even 10. Takes 3 million steps, so you don't want to have a factorial time algorithm if you can avoid it. With 1000, I don't even know what that number is. It's very, very large, 4 times 10 to 2,567th power. You probably don't want that algorithm to be running and uh my computer, my calculator would not even tell me what 100,000 factorial is. So yeah, these increasingly get bad quite quickly, especially once we get out of polynomial time and into exponential time algorithms, so. As datasets get bigger, this is why we care about how efficiently we can run algorithm or how many steps something takes. And again, here's a, here's a visual representation of that same idea where we have log in as uh data sets get bigger if the algorithm runs in log in, very slow growth. It won't take much longer, but very quickly and log in and squared, all of those algorithms really will run away and take substantial amounts of time as we go. So real quick again, just this idea of constant time algorithms, they will always take a fixed number of operations regardless of the size of your data set. So for example, An algorithm that always outputs the first element of a list. Typically we refer to lists by their first item, the eas it's the first easiest thing to get a hold of. So if it doesn't matter how big the list is, if you're always just saying what's the first element, that's a constant time operation. An algorithm that adds two numbers together is also a constant time operation. It's not one step per se. Maybe it's 4 if you think about it, we need to get the first number, get the second number, add them together, output the result, but it's always some constant number of steps. There's no trickery, or an algorithm just completely ignores the data set entirely and does something else. So an algorithm that gives you the link to a viral YouTube video that has nothing to do with the data set, that'll be a constant time operation. Linear time operations by contrast, always are always directly proportional to the size of the data set. So it may be 1 for 11 step for every 1 element, it may be 3 steps but it's directly proportional to the size of that data set. An example of this might be an algorithm that tries to find the number 5 in a list. For this list here, it may take 5 steps because we have 5 elements in the list. For this one here, it might take 6 steps because we have 6 steps or 6 items in the list. It may not take that in a better case scenario, as we'll see in a second. And as the list gets bigger, it takes more and more steps. It is directly proportional to the size of the list in question. And this leads us into our one of our two big topics for discussion for the rest of today's class, which is the concept of searching, and then later on we're going to talk about the concept of sorting. So searching for a value is one of the most fundamental things that we can do with a data set, and this is true in computer science, but this is true. And for any business operation, for example, if you have a client list you need to go through, or you have a product list of SKUs that you need to go through, you're gonna be searching through that data set quite a bit. There are a couple of ways to solve this problem with basic lists. Um, we'll look at more advanced data structures a little later in the course, but with basic lists there are only a couple of ways to solve this problem, and we're going to look at two of them, um, but they behave differently and they require slightly different situations to be true. One of them can be done on any list. One of them requires us to tweak that list a little bit in order to be able to take advantage of an efficiency. Uh, but let's start with the more fundamental one, which is linear search. And Linear search is basically what we're showing a second ago on these slides, where we have some list of data. And we have some target that we're trying to find in that list, so. We're looking for the number, the number 5, for example, uh, in a list. And this is what's called pseudocode, or we could go through this as a, it's just an algorithm. This is a series of operations. These are our steps that we're going to go through operate this algorithm of linear search. As long as we have not gone past the end of the list, so we know how big this list is, as long as we haven't run out of items, we're going to check to see if the current item we're looking at matches the target we're looking for. If so, we can stop because our search was successful. Otherwise, we go to the next item and go back to this first step here. OK, so this is a finite number of steps. Remember, algorithms have finite numbers of steps, but there is this looping procedure or iteration

procedure where we keep going back to the beginning until we run out of data to check. And if we get past all of this, and now we have gone past the end of the list, so this is no longer true, we haven't, we have searched the entire list and the search was unsuccessful. OK. So this is a basic algorithm, these steps here, of linear search. So let's see it visually to see if that makes a bit of sense. So here is a list. There are 15 items in this list, and we'll note that here by saying there are 15 items in the list. And let's just say we are looking for the number 99 is our target. In this list. So what are we going to do? Well, we need to start stepping through this list. Now that we probably want to do is have a way to refer to the items in this list. And so we're going to give them all an address or just a number, something to indicate a position. Imagine this like a neighborhood of houses where every house has an address, and you may notice that we have a little 0 here. In computer science, we typically start our counting from 0 for a variety of reasons. So we'll do that here as well. So there are 15 items in this list that range from index 0. Up through index 14, those are the addresses, uh, those are the numbers on the houses as we walk by and check to see if 9 lives in any of these houses. So we'll go through the algorithm. Starting at element 0, as long as we haven't gone past the end of the list, which we can check by seeing, are we looking at a number that is over here? Are we looking at 15 or 16 or something that doesn't exist in the list? As long as we haven't gone past the end, let's go through our process. Check to see if the current item being examined matches the target. So 11 didn't match the target, so instead we're going to advance to the next item and return back here. Does 23 match the target? No. So we advance and we keep doing this over and over until one of two things is true. Either we found what we're looking for or we run off the end of the list. In this case we do find what we're looking for. We find the number 9 in the list, and so we advance to this point here. We have reached the target. We are successful. Now, let's try and find a different element that we can see with our eyes is not in the list, the number 28. We'll do the same thing again. We'll start at the beginning. We've indexed, we've reset our element counter back to 0, and we're going to step through. So as long as we haven't gone past the end of the list, check to see if it's, uh, if we found the target. If so, we can stop. If not, we advance. So we're going to keep stepping through this one. And we know what's going to happen here, right? We have eyes, we know that there's no 28 in this list, but the algorithm does not. The algorithm doesn't have any extra information. The computer doesn't have this wide angle view of what we're doing. So we eventually reached the end of the list and then we would advance past element 14 to element 15. There is no element 15 in this list, right? We have gone past the end of the list. So this condition here highlighted in white, or the white background rather, is no longer true and therefore we have examined the full list and the search was unsuccessful. Now I want to draw something. Uh, attention to something real quick, which is this is not necessarily mean that the algorithm was unsuccessful or the algorithm was incorrect. We did exactly what we were trying to do. step through to find an element. We didn't find the element, but our search was still correct. We still exhaustively made sure that element did not exist in the data set. Uh, I see we have a question from the audience. If the size of the list is 15, how come there isn't an element 15? So in computer science, the general idea is that we start counting from zero. So there are 15 elements in this list, but there is no element 15 because we started our counting from index 0. It's just we gave it an arbitrary address. We could have instead increased these numbers all by 1 and said this is element 12, and so on, and this is element 15. But just as a uh computer science norm, we typically refer to the first element in a list as element or item or index zero. It's a great question. So that's why there's no element 15 in this list, but there are 15 elements in the list numbered from 0 up through and including 14. OK, so let's use the language you discussed at the very beginning, or a little while ago rather, to talk about how this algorithm can be analyzed or how we would classify this algorithm using that terminology we discussed before. In the worst case scenario, we have to look through the entire list to find either that the item we're looking for is in the last spot position 14, index 14, that the item we were looking for wasn't in the list at all. Uh, in that case, that would be the worst case scenario. That was the maximum or the upper bound on the number of steps that this algorithm might take to do its job.

In the best case scenario, as you might imagine, it could be that the target we're looking for is at the very beginning of the list. So we don't have to go through that entire process. And when we were looking for 9 a moment ago, we didn't have to go 15, we have to look at all 15 elements. We only had to look at 6 or so. And so the best case scenario would be 9 is at the very front. We only have to look at one element. And so using that language we discussed earlier, we could say that this algorithm runs in big O of N or in the worst case scenario or the upper bound on the number of steps this algorithm takes is N or proportional to N. and in the best case scenario, Big Omega, it's 1 because it may be that we find it right away on the first step. OK, so that's linear search, and I mentioned there's another way to do this, and that's binary search, but binary search is a little bit different because it has a special condition attached to it, which is instead of considering any list, we now have to consider a sorted list and we haven't talked about sorting algorithms yet, but we will. The list needs to be sorted in binary search to take advantage of something, and we'll see what that is in a moment. So we're gonna have a list of known size, a target to search for, same as linear search, and we're also gonna take note of the locations of the endpoints. And we're gonna call them start and end or beginning and end, and we'll see why in a moment that that's gonna be very helpful for us. And then, and this might look weird at the moment, we'll get there, as long as the start is less than or equal to the end, which is trivially true at the beginning. We find the midpoint of those two values, right? So we're going to look at the beginning, look at the end, find out where the middle of the list is at that point, check to see if that matches. If so, we can stop just like Linear search. Search was successful. If not, though, and this is where we can take advantage of the fact that this array or this list rather is sorted. And what we are looking for is less than the current element, so you can imagine that would be to the left of the current element. We can instead change our endpoint to look at a smaller subset of that list. Effectively, what we're going to do then is be able to throw away half of the list because we know things are sorted. If I'm looking for something smaller than what I found in the middle, I don't need to look at everything that's bigger than what I found in the middle. So we're going to have an, an efficiency that we can take advantage of that we'll see makes binary search run more quickly or in a different runtime class from those that we discussed earlier. So if not, and it's less than what we're looking for, we change our end point and look at a smaller subset. And by contrast, if what we're looking for is bigger, we're gonna do the opposite, we're gonna change our start point and look at only the larger items as opposed to only the smaller items. And again, same as before, if we have done something where we have, as we move those end points closer and closer to the middle, we'll eventually get to a point where they cross over each other potentially if the item we're looking for is not in the list. And if that happens, uh, we can declare the search to be unsuccessful at that point because we have compressed our list that we're searching through into nothing and therefore that item cannot possibly be in the list. So here's our list again. Let's give everything an address and pull up our algorithm for this process and not forget that we need to indicate the start and end points. Again, we're going to use the indexes here 0 and 14. We're looking for the number 19, and we need to make sure for binary search that our list is sorted. So we'll do a little bit of magic here to sort it and we'll talk about a way to do that in a moment. Now we have a sorted list. Now we can go through this procedure. As long as the start is less than or equal to the end, that is true. Star right now is 0. The beginning of the list, end is 14, the end of the list. We're going to calculate the midpoint. Midpoint is 7, so we find number 7 here. Then check to see, is that what we're looking for? Is 15 The answer is no. So in that case, what we're going to do is say the target what we're looking for is greater than 15, target member is 19. So if it's going to exist in this list because this list is sorted, it must exist over here to the right. It cannot left. If it did, that would mean that our list is unsorted, and this trick, this efficiency we're trying to take advantage of would not be possible. And so what we do, we set the new start point just to the right of the current midpoint. So we've set the midpoint right now to 7, that's in the center of our list. What we're going to do now is say I only want to look at this part of the list. That's the only place 19 could be if it exists. And so we'll set our new start point to 8, and what we effectively do then take this portion of the list out of consideration and hopefully that makes sense as to why we can do that. Uh, and why we can only do that if this list is sorted with Linear search, we couldn't necessarily throw away half the list because

there's no rhyme or reason to our ordering, but here there is. So start still is less than end. We're starting now. Our list is just this portion from 8 to 14, so we can go through this process again, calculate the new midpoint to be position 11, check to see if that's what we're looking for. The answer is again no. 23 is now too high. It's the opposite problem. So what we'll do instead is set the new endpoint to be just to the left. So now I don't need this part anymore, I just need these items here. And we can basically disregard the far right portion of the list. And then we'll just keep going back to this process. Start is still less than end, we haven't crossed endpoints yet, we calculate the midpoint to be 9, and we can see again visually, this is going to be a successful search. We found the number 19 where we hoped we would. The search was successful. If you think about it, how many times do we have to go through this process? Go back to linear search for a moment. We had to, when we couldn't find what we were looking for, go through this in this case 15 times. But here, if you were counting, we only went through it 3. We only had to look through, we only iterate through this loop 3 times. So that feels faster even if it's a little bit more heady. It feels faster. And in fact it is faster. Now let's see what happens if we have an unsuccessful search just to confirm that this algorithm will still be correct or will still behave the way that we want it to. So it's the same process we're looking now for the number 16, which, if it existed would exist here. It doesn't. So let's see what happens with binary search and see if it's still a successful or correct algorithm. Calculate the midpoint, the midpoint is 7, 15 is not 16, it's close, it's not quite there. So instead we're looking for is greater than 15. We're going to do the same thing as before, change our start point to be number 8 just to the right of the current position. And then throw out that portion of the list. We go through this process again. This is going to be the same start as the last one or the same sequence of operations. 23 is less, 23 is too big. 16, the target is less than 23, and so we can now eliminate all of this portion to the right. We set the new end point to be 10. And we can disregard the far right portion of the list. Now again, what's the midpoint between 8 and 10? It's 9. Is 9 is the value at position 9 what we're looking for? Unfortunately, no, it's less than that. And so we can set the new endpoint just to the left of where we had calculated the midpoint to be, position 8, and disregard the remainder of the list. Now our end points haven't crossed yet. They're in the exact same spot, so this part is still true. Start is still less than or equal to the end point. And so we can still go through this process. What is the midpoint of 8 and 8? Well, it's 8, so we'll recalculate the midpoint there. We'll check to see if the value at position 8 in our list is what we're looking for. It is not. We are looking for something that is less than that. And so we are going to set our, uh, we're going to set our end point just to the left of where we currently are. Again, we're trying to home in on where this item would be in the list if it existed in the list. In this case, now we set our end point to 71 less than the current midpoint, and now we have triggered the condition where this search is complete but was unsuccessful. The algorithm was still correct. The algorithm confirmed that the number 16 did not exist in this list, so even though it was an unsuccessful search, it was still a correct run through of the binary search algorithm. So that took fewer steps. It was probably more talking because we were going through this idea of compressing the list and eliminating things versus the stepwise nature of linear search, but we went through that process of going back to the beginning and trying again far fewer times in this case. So as you can potentially imagine, this algorithm is again given the condition that the list is sorted. Going to be faster in general we're able to toss out half of the list every time. So worst case scenario, we have to cut this list in half repeatedly as many times as possible down to a single element that is either what we're looking for or has wiped out the whole list because we've gone through that process so many times. In the best case scenario, it would be that the very first time we calculate a midpoint from beginning to end, we found what we're looking for right in the middle. So in this case, the best case, we'll go do this in reverse for a second. The best case, lower bound is 1. It takes one run through the algorithm, one step calculate or to find what we're looking for. And in the worst case of the upper bound on steps, it's log N. That's where that earlier I mentioned there's a sort of a hidden subscript number 2 here, log to the base 2. That basically means we are cutting this list in half over and over, and every time we do so, we can disregard or throw out

half of the list. And so binary search again with the caveat that it requires a sorted list is more efficient than linear search, uh, but how do we get. A sorted list that's gonna, that's gonna be a problem we have to solve and we're going to solve that in just a moment right after uh we have a question from the audience. Is this algorithm the same then as tearing a phone book in half again and again? Is this algorithm the same as tearing a phone book in half over and over? And the answer is yes, in a phone book, assuming the phone book, of course, is sorted. If it was not sorted, this would not work. But it's like opening to the middle of a phone book, finding that the name you're looking for is not on the page you happen to have opened up to, but is on one side or the other, ripping the phone book in half and throwing away the portion that does not have the name in it. You don't have to look at those several 100 pages' worth of information. Because you know that what you're looking for is in this part over here, not the part over there. And similarly, you can keep tearing that part in half over and over so you can have 1000 steps. Remember earlier we showed a slide of how many steps it might take for log N or N, given a size. For 10, for size 10, which a phone book is gonna have a lot more than 10 names in it, it only takes 4 steps for 1000, I think it was, uh, it wasn't much more than that. I don't recall off the top of my head, but. We're not looking at 1000 steps here. We're looking at a very, very small number, as the charts we saw earlier too, as that number gets bigger and bigger, the log and graph tends to get quite flat. So even though our input every time our input doubles in size, we only have to add one more step because we can eliminate half of the problem, basically canceling out that doubling every time we go through a step. OK, sorting is the other type of algorithm we're gonna talk about quite a bit today, and I want to stress at this point that we're talking about searching and sorting pretty exclusively today, um, these are not the only kinds of algorithms there are, right? Like there are algorithms to make breakfast. There's algorithms to do. Anything there's algorithms to figure out what you want to recommend to a customer who has purchased a particular item and you want to try and suggest that they purchase a different item. That's neither a searching nor a sorting algorithm, but there is a set of steps that goes through an analysis of what they might want. Uh, we're talking about searching and sorting state because they are very easy to visualize, but these are not the only kinds of algorithms we have. But since we just talked about binary search and the fact that we need to sort in order to use binary search, we should probably talk about sorting. organizing data is also very important for any business operation we're doing. We need to keep our client lists maintained, SKUs maintained. We need to keep our databases in order and so keeping things sorted is very important to do. There are a lot of ways to do it. There are far more ways to sort than there are to search through lists of things. We're gonna talk about several options today, but they are non-exhaustive. I want to be clear. And let's use our language of run time to talk about these various algorithms starting with selection sort. So the way selection sort works, one of the five we're going to talk about today, consider that we have this list and it's unsorted. Obviously if it was sorted, that would be a lot easier, but we're gonna consider an unsorted list and we're going to say that the whole thing at the beginning is unsorted. We don't know anything about the state of this list, so we're going to describe the entire thing as unsorted. Our objective is to find the smallest item left in the list, so we can use, for example, linear search to do this, we can step through to find the smallest item left in the list. And then we can swap that such that item becomes the beginning of the list. If we find this, if we walk through the entire list and we find the smallest thing, and then we put that thing at the front. We can now no longer need to be concerned about what this item is, the first item is, and we can just repeat that process again with the remaining elements in order to effectively sort the list, and we'll go through this visually to see this in a moment. So let's imagine we have this list of 6 items. We're going to go through this list of 6 items for all of our sorting algorithms today. And as we can see, it is unsorted. So we're going to go through our algorithm. Our algorithm in this case is just a couple of steps. Find the smallest item remaining in the unsorted portion of the list. Again, we can just use linear search for this. Then once we have found the smallest item, swap it with whatever the first element is of the unsorted portion at the beginning here, the entire array is unsorted. As items become sorted, we'll indicate that visually. And expand our sorted portion. So we'll see how that goes. So we need to first find the smallest item in the list. So we're going to start at the beginning, as we do with any list and step through to find the smallest one. So we look at the beginning. So far 5 is the smallest thing we have seen. We go through 2 is now the smallest thing we have seen

so we're going to keep track of that. Then as we go again, 1 is the smallest thing we have seen. Keep track of that. We go to element 3 or the 4th item in the list whose number is 3, that is not smaller than what we've seen, so that is no, we don't need to indicate that. We're just going to keep stepping through, see if we find anything smaller, and the answer is no, we don't. So once we've gone through the list and found the smallest item, we are going to swap that item with whatever the first element is of the unsorted portion of the list. The whole thing is unsorted at the beginning, so we're going to take 1 and 5, and we're going to switch their positions. And then we can declare, since we have found the smallest thing, that this element, this one must be sorted. And so now we have a fairly small sorted portion of our list. And 5 elements remaining in this 6 element list that are unsorted. And we can just go through this process again, so we're gonna find the smallest element in the list. We step through all of them, we find that the smallest one is 2. We don't actually have to do any swaps here. 2, we need to swap 2 with itself and declare that 2 is now sorted. We go through again, we find that 3 is the smallest item remaining, we swap 3 with 5. And declare that is now sorted and hopefully you can see that this is building over time this sorted list and it does not take too, too long in a 6 item list, a bigger list it might take a little bit longer to get all of the elements in position. At the very end we swat5 into place, 6 is the only thing left, so 6 must necessarily be the last thing that we can add to the sorted portion of the list. And now, after going through this process quite a few times, if you saw as we were going through, we keep iterating through, we have sorted everything. How do we analyze this though? So it's not quite as straightforward as Linear search, right? In Linear Search we went through the list trying to find something, but we only had to go through the list once from beginning to end. Here we went through the list from beginning to end multiple times. How many times did we do it? Well, it turns out we actually did that process roughly again down to a constant factor because the list got a little bit smaller as we went along, um, roughly N times. So we went through N elements of the list. And again, the list got a little bit smaller every time as we went, roughly N times. Again, there's a constant factors here, so it's not exactly that, but when we disregard those, that's what we get to. So the worst case scenario, we need to look at every element in the list on each path, and we have to repeat that process end times because we only get one element right every time we run through this. In the best case scenario, It's exactly the same. We have no way to check to see if things are already in the right position. We still have to step through. We don't have any other metadata or any other variables we're using to keep track of things, so there's no like efficiency we can gain with this particular algorithm. And so in this case, worst case scenario or the lower bound on runtime, or sorry, the. Upper bound on run time and the lower are exactly the same. They are both considered N2d algorithms and again that's because we need to run through the list of N elements end times. We have to repeat that process, so it's N across, and down, you can kind of visualize it that way. That is how we get tonsquared. So the question is can we do better than that? And the answer is yes we can. And so let's take a look now at Bubblesort to see if Bubblesort can help us out a little bit. So with Bubble Sort, we're gonna start with the same basic idea. The idea is that we have a list that is completely unsorted at the beginning, and over time we're hoping to build a sorted portion. Differently though, this time we're gonna look at 2 elements at a time, and if the two elements are out of order, we're gonna switch their position. What this effectively does is bubble the bigger element further and further to the right as we go. And so it's sort of the opposite of selection sort in as much as we're trying to find the smallest and pull it to the front by swapping. In bubble sort we're kind of pushing the biggest element to the end and if we push final position, that element is correctly positioned, and we can just keep repeating that process over and over. There's one other thing we're gonna do, which is keep track of how many times we make a swap. It may seem strange at the moment, but we'll get to why that is actually a pretty good idea in just a moment. So same list that we have been looking at, uh, let's go through this process again. Here is our algorithm and we're gonna keep track again, as I mentioned, of how many swaps we have. If two adjacent elements are out of order, swap them, then look at the next pair and do it again. And at the end of one pass, once we've gone through the entire thing once, hopefully the largest element should have bubbled or been pushed as far to the right as possible. So let's see, so we're going to start by looking at this pair of elements 5 and 2. If we're imagining this being sorted left to right in increasing order, uh, we need to swap them.

And so we will exchange the position of those two values and make note that we have made one swap in our swap counter. Now we look at the next pair. The next pair is not 1 in 3. 5 and 1. So we're looking at every pair of numbers carefully. 5 and 1, they are also out of order. We will swap them and we will increase our swap counter by 1. 3 and 55 and 3 rather are also out of order, so we need to swap them and increase our swap counter again. 5 and 6 are correct, we don't need to swap them. We're again, we're only looking at in this algorithm at just this pair at a time. This pair happens to be correct, so we don't have to make any swaps here. We look at 6 and 46 and 4 are out of order. We swap them. And now we have pushed the largest element as far to the right as it can go. There's no other pair to look at, so we can declare at this point that the largest element has bubbled to the end, and we can say that is sorted. OK? So we have pushed it all the way to the end, it is sorted. This is now this orange portion here is our unsorted portion. The blue is the sorted portion. Once we go back to the beginning, we want to reset how many times we've made a swap. And we'll go through this process again. Our 2 and 1 out of order? Yes, we're going to swap them. Our 2 and 3 out of order? No, we'll leave that alone. Our 3 and 5 alone, but 5 and 4 are out of order. We're going to switch those and again indicate that we have added one more swap to our swap counter. And at this moment we as humans can see this happens to be correct. We know that this is sorted, but this is only because we can see more at once than the computer can see at once. So the only thing the computer can guarantee at this point is that, or the algorithm. that the 5, which is the largest element in the unsorted portion, has been bubbled all the way across and so only can we say at this point that the 5 has been sorted. But now we're going to see why that swap counter is going to come in handy. We'll reset it again and we'll start comparing pairs. So 1 and 2 don't need to swap, 2 and 3 don't need to swap. 3 and 4 And now we're done and we made no swaps. If we didn't have to change the position of any values, then everything else has to be correct and so we don't just get one, we potentially can now get all of it or we do in this case get all of it and can say that everything left because we didn't have to change anything must be in the correct order, so. That's an advantage. We didn't have to go through the looping process and times. We did it in this case 3 times instead of having to do it 6 times, so that feels better. Is it actually better? Well, the answer is again because we're keeping track of how many swaps, yes, it is better, but in the worst case, it's actually still just as bad. That was, that was a medium case that was pretty OK. The list wasn't completely in backwards order, but if it was, we would have had to keep bubbling just the first element over, then the next, and we would only get one at a time in the worst case, a completely backwards, uh, list, but that wasn't the case here. But in the worst case that would happen. In the best case though, imagine that we had a completely sorted list. If that was the case, when we went through it one time. Our swap counter would be 0 when that was done and therefore we would only need to make one pass through the entire list. And so the upper bound on run time, the worst case situation, is that this algorithm runs in big O of N2d, having to look at all N elements and bubble the biggest one over N times again disregarding constant factors and so on. But in the best case, we only have to make one pass looking at each of the N pairs or N minus 1 pairs or N elements. So it's not omega of 1 because we still have to look at all of the elements, it's omega of N. So that is, that is in fact an improvement over uh selection sort in the best case. All right, so let's talk about another one. And I'm gonna, I'll reveal now that this is actually going to have exactly the same run time as bubble sort, but it's going to do it in a very different way. So this is an example of how two algorithms that appear to be quite different can actually have the same effect and can run in the same amount of time but do so in very different ways. So with insertion sort we're going to again start with a completely unsorted list and can call the whole thing unsorted. Arbitrarily we're gonna say the first thing we see has been sorted. It seems kind of weird, but OK, we declare the first thing sorted. Then we look at the next element, and if it is out of order, we're gonna shift or rearrange the elements that are sorted to fit that one into place. So, OK

so as we go through, we declared the first thing sorted, and we're just gonna keep shifting things around to make room as we, as we go. So we'll look at one element at a time, put it in the right spot, spot. Let's see how this looks with our, uh, typical starting list here. So we arbitrarily decide we're going to declare the first element sorted. 5 is sorted. Again, we can see that seems wrong, but we'll go with it, we'll trust the algorithm here. Then we look at the next one and we either append it to the sorted list, so if it's larger than the largest thing in the sorted list, we can just tack it on or we shift things around. So now we're going to look at the 22 is clearly before 5. It's supposed to be there to the left. So what we're going to do is kind of set it aside temporarily. We're going to slide 5 over and then we're going to pull the 2 back to where the 5 was. And now this portion in blue has been sorted. OK. Now we look at 1. One clearly also belongs to the left here. So we'll pull that out, we'll push these two over, and we'll pull the 1 back into the starting position. We go through that process again. For 3, we don't have to move everything, but we do have to push the 5 over and then pull the 3 back into position. The 6 is greater than the 5, so we can actually just tack that on. We don't have to move anything around. It happens to be bigger than the biggest thing we have sorted thus far, and so we can just tack that onto the end. And the 4 also requires the 6 and the 5 to move over to be put into position there. So. We have made one pass through the list, right? That's different than bubble sort. Bubble So it went all the way to the end. We've got one thing in position and then we go back to the beginning and do it again. Here we went one element at a time, but every time we looked at just one element we had maybe had to push a lot of things out of the way. So that's maybe where these two algorithms, even though they have the same run time. Um, behave very differently. One of them we're looping through multiple times. This one we're having to push potentially up to N elements for each of the N elements, right? If we have 6 elements here, we might need to push 5 of them out of the way to make room for just the one that we need, and that's gonna be the same math, believe it or not, as a bubble sort N times N in the worst case scenario. So I kind of buried the lead there but worst case scenario, same as Bubble So if it's in reverse order, we have to potentially push up to end elements out of the way. Best case scenario, we just keep tacking on the uh as the example here a moment ago with 5 and 6, we can just keep tacking on if we find everything's in the right order, we just keep appending it to the end of the sorted portion. So same exact outcome as bubble sort in terms of run time, but it is a very different approach to that same idea. So the algorithms we've talked about so far have done. This iterative process we go through the steps, we start at the beginning, we continue on, and oftentimes we go back to the beginning again. That process is called iteration. And we're to talk about the next uh sorting algorithm, we're gonna have to take a bit of a detour here and talk about this concept called recursion. Which is also a very important, uh, problem solving technique in computer science and is going to be the way we need to, we need to get our heads around this idea before we can discuss this next sorting algorithm. As I mentioned, we're going to keep doing something in an iterative algorithm until something, some trigger occurs, either we've reached the end of the list or we found what we are looking for. We go back to the beginning and do it again. In a recursive algorithm, it's a slightly different concept. Instead, we try and make the problem we're trying to solve a tiny bit smaller and just solve a teeny portion of that problem and then sort of play a game of telephone where we call somebody else up or call the algorithm again on a slightly modified version of the problem and wait for their response to answer the question. And we we're going to illustrate this, and we've heard this word already today. Is through the concept of the factorial function in math and if you have, if you recall from your math days what the factorial function is, it is a calculation that represents the product of all integers from 1 up to and including the number you are looking for. So the factorial of 3 would be 3 times 2 times 1. The factorial of 4, which is an illustration we're going to get through in a moment, is 4 times 3 x 2 times 1 or 24. So this algorithm calculating a factorial, and another example of an algorithm that's not searching or sorting but it's probably also not something you're doing every day in your company, perhaps is uh can be expressed iteratively. Set a running product value that we keep track of to 1, not 0 because we're multiplying things by 0, that would just go to zero forever. So we start the value at 1. We set a counter equal to one where we're going to start counting up from, and then as long as the counter is less than or equal to the number we want to calculate the factorial of

we multiply it by the current product and increase the counter by 1. So if we're calculating the factorial of 4, we start at 1. And we have our counter at 11 times 1 is 11 times 2 is 22 times 3 is 66 times 4, which is the number we're trying to calculate, the factorial of 4 is 24. So that's an iterative approach to calculating the factorial. But we can also have this idea of a recursive approach where we are trying to solve a slightly smaller version of the same problem. And we keep asking, it's like a game of telephone, I think a great way to think about it. We call somebody up and say, Hey, do you happen to know the next this other version of this problem that might be a little bit easier for me to solve. Let's see this in action. Maybe that'll help visualize this idea a bit. So if the value the algorithm is currently operating on, so we're going to start at 4, it's kind of the opposite in this case, we're going to count down towards 1. If the value we are operating on is less than or equal to 1, we return a value of 1. This is oftentimes when you're talking about a recursive algorithm called the base case. It's the simplest problem we can definitely solve. The factorial of 1 is 1, the factorial of any number less than 1, also if you're curious, is just defined to be 1 because if it was 0, it would mess everything up, um, so. If we have that specific case, we can solve that very specific problem and say the answer is one. Otherwise we return whatever we're currently operating on multiplied by the factorial of the number one number smaller. So we're kind of trying to get towards that base case. We're trying to get a slightly smaller version of the same problem. And we're gonna wait, we're gonna be on hold on the phone waiting to get the answer from somebody else down the line to then give that answer back to us. So it's a different approach. Let's take a look at it. So we're gonna calculate the factorial of 4. what is the factorial of 4? Well, according to my rule, if it's 1, a factorial of 1, I know it's just 1. Otherwise though, it's factor of 44 times the factorial of 3. But what's the factorial of 3? I don't know. I don't know if I answer that one off the top of my head, but I can just recurse. I can do this process again on a slightly smaller version of the same problem. So what's the factorial of 3? It's not 1, but I do know by this case that it must be 3 times the factorial of 2. It's the same rule I just applied a moment ago. So what's the factorial of 2? I don't know, but I do know that it is 2 times the factorial of 1. So what's the factorial of 1? I do know that by definition of the recursive algorithm we've discussed, the base case we've set up, that value is 1. And so factor of 1 is 1. And now I can, I've sort of played telephone. I've had, I've been waiting on hold for everybody else to tell me the answer. One says I'm 1, that gets kicked back up. I'm 2, 2 x 3 or 6, and now 4 times 3. Uh, 4624. So that's the idea of this factorial or sorry, this recursive process is that we are operating on successively smaller or easier to nibble on bits of the same problem until we get to one that we definitely know and then all this information can immediately flow back to what we originally started with. So we end up with the value of 24, the same way we would with the iterative algorithm. And the reason we talk about this is to get into the next algorithm we're gonna talk about, which is mergesort, and mergesort behaves quite differently from the other algorithms we've already discussed today to do sorting. Um, and requires us, doesn't actually require us, but it's a lot easier to conceive of as a, as an, as a recursive algorithm as opposed to an iterative one. So far the best we've been able to do for speed in the worst case, the upper bound on run time. Is O of N squared. Mergesort will allow us to do better, but we have to think outside the box, and we have to come back to that original trade-off we discussed, which is this idea that algorithms, the things we care about are time. And memory or time and space and in this case we're going to use more memory to solve the problem as opposed to more time if that's a trade off we're willing to make mergesort will allow us to do a little bit better in terms of time as long as we have those resources available to us to spare. Every algorithm, like I said, we've talked about has been done in place. We're working on that same array. We're just exchanging values or we're rearranging values, we're pushing values to the end. Um, in Merchar we can't do that. We can't just use that same 11 single array of 6 elements over and over. We have to make duplicates or triplicates of that and do a couple of things elsewhere in memory

holding things in place while we do something and then eventually put the pieces back together. So that's what we're gonna do here, and we're gonna be leveraging recursion to, uh, to implement this algorithm. So let's take a look at the merge sort algorithm. Sort the left half of the list. Then sort the right half of the list, and then merge the two halves together. If you're looking at this and you're saying that doesn't seem like you're solving a problem. You're right. Uh, this alone, I, I'm kind of outsourcing the problem, sort the left half of the list. Unless that list is of size one, which is something I do know how to sort, I guess a list of size one is automatically sorted. I don't know what to do, but what I can do is recursively apply this algorithm to say, well, if I have a list that's bigger than one, I guess I can just do this again on it and keep splitting until I get to something I can do a list of size one trivially sorted. It's the only thing that's in it, and then start merging the pieces together. So we're going to walk through this one quite a bit more slowly just to get your head around this idea of what is happening. So merge sort, same list, let's sort it using this approach. We're gonna sort the left half of the list. That's this. That's all the algorithm tells me to do. I don't know how to do that. And also just for visual sake, so we can discuss this without saying the left of the left repeatedly, I'm going to call this the yellow list for the rest of this discussion, and we're going to call this the purple list, but this is still the left half of what we started with, and this is the right but it will allow us to not have to go so many layers down in our discussion today. So instead of saying sort the left half of the list, I've just changed this to now, sort the yellow list. Well, I don't know how to do that, and the only thing I have for an algorithm are these three steps and the fact that I remember that a list of size 1 is trivially sorted. So what can I do? The only option I have is to do it again. Take this yellow list and apply our algorithm to it. sort the left half of the yellow list. I can do that. Now it's a list of size 3, so what do we do with it? It's not like it splits evenly, a list of size 6 split nice and evenly into two equal parts. In the event that we have unequal parts, we'll just arbitrarily say that the left one should always be smaller. We're just gonna pick that arbitrarily. So I want to sort the left half of the yellow list. Can I do that? This is the left half of the yellow list, this would be the right half of the yellow list. This I can do. This is a list, again, I'm kind of like, if you think about it as like layering down, I'm just focusing on this piece. That I can do. That's a list of size one that is trivially sorted. So we're gonna say, OK, we'll put a pin in that, that is sorted. Now, I need to sort the right half of the yellow list. That's those two elements there. I don't know how to sort a list of size 2. The only thing I know how to sort is a list of size 1. And so faced with this problem, the only thing I can do is start this process again, kind of putting a pin and everything else and trying, trying this again. So what I need to do instead is sort the left half of the right half of the yellow list. OK, so now I'm back to just focusing. I want to sort this right here. The left half of the right half of the yellow list is an element of size is a list of size 1. I do know how to sort that, that's 2. The right half, uh, of the right half of the yellow list, that is a list of size one. I do know how to sort that. So now, 1. So I have now sorted the left half. Of the left half of the yellow list. I have done these individual fractions of this list, but now I'm going to come down to this step, which we haven't talked about yet, merge the two halves together. Of this portion here. How do I do that? Well, I look at each of the two lists and I say, which one is smaller. I take whichever one is smaller and I put that into position and then I do that over and over. Now in this case it's just two lists of size 1. But if I had bigger lists, I would look at the first element of both of those lists, compare them, put it into position, then I would look at what's next for both of them, put it into position. So among these two options, which one is the smaller one, if I want to put things in order, it's the 1. So I put the 1 into position. And then all I have left is the 2. I put the 2 into position. So we have now sorted the right half. Uh, of the yellow list. So now

if you're thinking about this in terms of where we started, we have this full list. We split it into a yellow list and a purple list, and now we're trying to drill through this idea of sorting the left half of that overall list. We're getting pretty close at this point. We now need to sort these pieces together and once we have done that, we will have sorted these three items overall. I know this is a bit strange. You have to keep in mind that we're layering down and then we're kind of like undoing. It's sort of like that telephone call for factorial. We're making calls down the line and sorting smaller and smaller problems, and then we kind of back our way back out back to where we started. So let's merge this list of size 1, the 5, and 2, the 1 and 2, into a single sorted portion, and that will complete the overall objective of sorting the left half of the whole list that we started with. Hopefully that makes sense. So we look, which one of these is lower, 5 or 1. That's the only comparison we have to make when we're sorting the two halves together. The 1 is lower, and so we put that into position here. Now we've already excluded the 1, we've already got the one in place, we look at the, again, the first element of this list, and the next available which is smaller, the 2. And then which is smaller, 5 or nothing in this case 5. OK, so quick pause, where are we? We have now sorted the yellow list, which, as we recall, was the left half of the whole list that we started with. So in the overall process of this algorithm, we have done the first step which we said was sort the left half of the list. Now we have to repeat that process again on the right, but just for context and grounding as to where we are, we kept breaking our problem down from a list of size 6 to 3 1 and 2. We had to split that 2 into a couple small lists, and then we built them back up in assorted order. So we go back a second and just look at where we ended, we took this piece here, 521. And through a whole bunch of layering and recursive application of this algorithm we end up with 125. 125 is a correct sort of this yellow list. We still have the other half list to deal with, but we have correctly sorted the left half of the overall list. Alright, so let's do this process again with the right half of the list and hopefully this will start to make a bit more sense now that we've seen it once before. So now we're gonna handle that until we get, uh, With a sorted right half of the list and then we'll do one more merge together and we'll be all squared away. we need to sort the, we just sort of the left half of the whole list, and now we're going to sort the right half of the whole list, which we've called So let's sort the purple list. How do we do that? It's a list of size 3. We don't know how to sort a list of size 3, so we're going to go back to the beginning and start again, and we're going to sort the left half of the purple list. list again, we're deciding if we have an uneven number of elements, an odd number of elements, we're going to pick that the left side gets the smaller piece. We do know how to sort a list of size 1, and so we will declare the element 3 to be sorted. We do not know how to sort a list of size 2, and so we recursively go back and apply this process again now just to that two element list 64. Can we sort the left half of that sublist, the left half of the right half of the purple list? The answer is yes, we can do that because that is a list of size 1, so we can declare that is sorted. Can we sort the right half of the purple list? Yes, that is also a list of size 1. We know how to sort a list of size 1 because it is trivially true that it is sorted, and we declare that is in position. So now we need to merge these two halves together. To get to complete that section of the algorithm. We look and we decide which one is smaller, the smaller one is 4, then what's smaller is 6 or there's just nothing left, so it has to be 6. OK, so now we have sorted the right half of the whole purple list, and now we need to merge the two halves of the purple list together. Now again, visually we can see that that's the case, but the computer doesn't know that, so we have to make a comparison between 3 and 4, which is smaller, 3, and then between 4 and 04, and then between 6 and nothing, 6. And so ultimately now through this process we have sorted. This list, the purple list is sorted. The yellow list, the left half of our original list is sorted.

So there's only one thing left to do. Uh, so again, let's just frame ourselves as to where we are. We have sorted both of those halves of our original list, so we have completed step 2 of our big overall original problem of sorting the list. We've sorted the left half of the list and we've sorted the right half of the list. And so now all we have to do is merge those two halves together. Now I'm going to do a little bit of cleanup here. We're going to just blank out a bunch of this stuff and we're going to return our original array color scheme back. So this was all the work that we did. This is this represents the space that we sort of took up while we were doing work because again remember we in merge so we're making this tradeoff of time and space. This represents sort of space that we did to do our work. And now all we need to do is merge this left half of the list and right half of the list together and we'll put them back into our original list. So let's just clear that list out. We'll just make room for everything we're about to copy in and we'll begin our comparisons, which is smaller between 1 and 3, the beginning elements of the lists that we are starting with. That's 1. Now which is smaller, 2 or 3, those are our two options are the elements at the front of our lists. 2 is smaller, which is smaller, 5 or 335 or 44, and then 5, and then 6. Merge sort is weird and if your head's spinning a little bit, that's OK, especially if you've never seen this concept of recursion before. But what we did was we kept breaking this problem down into smaller and smaller pieces. Until we got to a piece we knew how to solve a list of size one. And then we just started reassembling. It's like taking a set of blocks, tearing it all apart, and then rebuilding it back together in a different order. It's kind of the same idea. So once we have finished putting all these together, the list is sorted. And you're probably gonna think that felt like it took a lot longer than bubble sort or selection sort or insertion sort, and that's probably because we spent a lot of time talking about it, but in fact, when we get to very large data sets, this is actually significantly faster if you're willing to make the trade-off of time versus space. So. Worst case scenario, the list is in a completely reverse order. It makes no sense. Um, the algorithm though will never know this because the only thing it knows how to do is sort elements of sort lists of size one and then put them back together and then put those, you know, keep comparing those lists and merging them back together. It does not matter what order the original list is in, the algorithm has no shortcuts to get around it. Um, the best case scenario is exactly the same. The algorithm knows nothing about the list and so it can't, there's no tricks or efficiencies like we have with Bubbleor or insertion sort where we could just keep, uh, with Bubblesort, for example, keeping track of how many swaps were made or with insertion sort just keep adding things to the end. There's actually no efficiencies we can gain here. So in the worst case scenario or the upper bound on run time, uh, merge sort is better. It runs in n times logn, which is generally for N as again we care about how things uh as N grows uh for large N that is significantly better than Nsquared time. But the lower bound on run time is actually uh higher. It's n times log in as opposed to N, which is the case for bubble sort or insertion sort. There were tricks we could take advantage of with bubble sort or with insertion sort to make it run quicker or that would allow it to end uh more quickly rather than run quicker uh if the list happened to be in order. But the merge sort doesn't have any tricks like that up its sleeve so. The worst case of the upper bound run time is higher, but the, uh, or sorry, lower, but the lower bound run time uh is worse. Hopefully that makes sense. OK, and then I just want to quickly get back to why this is N times logn, so we have N elements in this list. So in this case 6, and we may need to merge a single element back in log and times. So log in a log of 6, log the base 2 of 6 is slightly between 2 and 3. We always round that up. So there are 3 potential mergers that need to happen and 6 elements. That's why it's n times logn N is the number of elements. Logn in this case represents the number of merges that may need to happen for that to come into play. One more sorting algorithm I'd like to talk about today is called BOGOSort. Is this going to be better than anything else we've seen so far? So let's see. Let's go back to our original concept of we have a list that's completely unsorted, um.

And we want to try and sort it, so the whole list is on sort at the beginning. What are we gonna do in this algorithm? We're going to randomly shuffle the elements of the list and check to see if it is sorted. We just do that via linear search, make sure that everything is uh increasing or greater than or equal to. If not, repeat the whole process until it is, so we reshuffle the whole list and try again. Is this going to be better? You probably can guess what's gonna happen here. So, we start here, great, this is sorted. No, it's not. That's OK, we'll try again. All right, this is sorted, this is sorted. OK, we're doing good. No. That's not gonna work. We do this, OK, problem again. And we can do this for a really long time, a really, really long time. Keep reshuffling, and eventually we hit upon this after years of waiting. Uh, with a 6 element array, hopefully it won't take years, but with a very large one it might, and we can start going through this again. Is this in order? And the answer is finally, yes, this one is in order. That was exhausting. Uh, this is an example of a very bad, very, very bad snoring algorithm. Hopefully, uh, you're not using this in any way. Uh, let's do this in reverse. The best case scenario is what we just saw. If it happens to be that the random shuffle happens at the beginning, uh, that would be great. It's in order. That actually would end up being better in that case than the best case scenario for merge sort. But the worst case scenario is that we reshuffle that list over and over, and we never find the correct order, which is possible because we're not keeping track of all the permutations that we've done. And so we may check the same permutation multiple times over and over. And so this is kind of an interesting case where we have an unbounded run time for this algorithm. It theoretically could run ad infinitum. It could go on forever. And so there is no way to classify this as having a run time. It is unbounded, but in the best case scenario, it actually is just as good. As uh the potential best case scenarios for bubble sort or for insertion sort. Which is that it would run in omega of N and BogoSort by the way, is short for bogus sort, it's not uh actually a real sorting algorithm, but it's kind of a fun way to express this concept that there are algorithms that despite having very few steps involved. Uh, can run for insanely long amounts of time, uh, to the point where there is no way to conceive in the framework that we've been discussing today, uh, a way to express that other than to say it just is unbounded and goes on forever. Yeah, I think you have a question. Would you ever want to actually use Bogosort? You would not want to use BogoSort other than for a fun illustration of what can happen with a very short algorithm. If you are not careful about what you're doing or you introduce randomness into an algorithm, uh, you don't want to use Bogoort though to actually do anything with your own data, that's for sure. But it's a good way to illustrate this idea that algorithms are not necessarily just confined to these nice little uh time classes that we've been describing that if you're not careful about being precise with your algorithm, it can become a monster unto itself. Alright, so let's quickly just take a summary of everything we've talked about today and see how many different run times we experienced or encountered variety of sorting algorithms, for example, running an N squared time. We've seen algorithms running an N log N. We've seen algorithms where the best case and the worst case run time or the lower bound and upper bound as the case may be, are identical in the case of selection sort and merge sort. We've seen algorithms we absolutely should not be using to do any sort of sorting. Uh, Bogoor for example with unbounded run time we've seen algorithms like linear search and binary search where we may only take a single operation to do what we need to do. So a variety of algorithms can run in a variety of times and that's just gonna be the case in some situations. Uh, there are other algorithms as well that we did not discuss today that can also be used in place of some of the ones we have discussed today. You may have heard of one, for example, called Quicksort, which also runs in. Uh, a time comparable to mergesort but may handle larger data sets better and then there are other algorithms that we can use that may have better run times than mergesort or Quicksort that run in closer to, but not exactly O of N, but they impose additional. Constraints on what we can do with the data we need to either ensure that the data is confined by some bound or have enough space on our machine in order to let the algorithm run its course. So this is just a sampling of some of the options that we have available. All of these algorithms did exactly the same thing. 5 ways in sorting to solve the same problem. All of them are correct with maybe put an asterisk on BOGO sort in this case

but given infinite time, it is correct, um, so all these items do the same thing. They all are correct, but they have very different uh run times and ways of achieving those run times. Bubble sort and insertion sort is a great pair to consider because they run, we would classify them using our notation exactly the same way, but the process by which they do this is very, very different. So Coming back to just bring things full circle today, we have discussed two main ways or two main types of algorithms to talk about, right, sorting and searching. There are far more algorithms than this that you will encounter, um, that have nothing to do with uh sorting or searching at all, and it's very likely that you will not be in a position to be, uh, implementing these yourself, but you may be in a position. To be a decision maker for what resources are relevant, what are we gonna spend our time on, money on, what are we, are we gonna get more server space to handle whatever large sets of data come into play? And so having a vocabulary about these algorithms and being able to communicate with some of the more technical members of your team will hopefully pay dividends for you in the future. Thanks for joining me and we'll see you next time.