[Week 3, Continued] [David J. Malan - Harvard University] [This is CS50. - CS50.TV] All right. Welcome back. This is CS50 and this is the end of week 3. So for those unfamiliar, last year Harvard launched what's called the Innovation Lab, or i-lab, which is a wonderful building across the river on HBS's campus that is open to college students, GSAS students, students from all across campus, including faculty, and it's a place to come together to work on innovative things, particularly entrepreneurial things if you and 0 or more friends are thinking of doing something entrepreneurial either during this class, after this class, or beyond. So one of the things they do over J term is these trips, one of which is to New York, one of which is to Silicon Valley. Space is very limited, but it's an opportunity to rub shoulders with MBAs and graduate students across campus and actually spend time in those respective areas chatting up startups, chatting up entrepreneurs and the like. So if interested, check out this URL here. It is also available on the slides online. Could we tone down the house audio just a little bit? If you would like to join us for lunch this Friday, 1:15pm in Fire & Ice, please head there. Apologies if the form is already filled by the time you get there. But we'll continue this tradition onward. Today we continue the higher level discussion of various problems that we can solve, focusing much less, today at least, on code and much more on ideas. So think back to week 0 when we tore a phone book in half, the objective of which was to do something, admittedly, a little bit dramatic but to send the point that searching doesn't have to be, necessarily, as obvious at first glance as you might think. And problem solving in general might not necessarily always be the best-- The most obvious solution might not necessarily be the best. So we had this phone book and, frankly, all of us in this room had the instincts, most likely, to start in the middle when looking for Mike Smith and then go left or right based on whatever letter of the alphabet we happened to end up on. But that simple idea that we humans have taken for granted for so long really should start to come to the forefront of your mind because as the problems get much more complex than a phone book, those same simple, brilliant insights are what are going to allow us to solve much more complicated and more interesting problems, among them some of the things we take for granted already these days. Billions of web pages out there, and yet Google and Bing and the like are able to find things for us like that. That's not happening by using a linear search, searching through all possible web pages. Facebook is able to tell you who all of your friends are or friends of friends, and that too can be done seemingly in an instant these days even though they have millions of users. And so how we actually solve problems on that scale will ultimately reduce to the ideas we looked at in week 0 and a bit more today. We won't re-execute this algorithm, but recall we also did in week 0 this exercise where we had everyone stand up, take on the number 1, and then we had everyone self-count by pairing off, adding your numbers together, then half of the gang sat down on every iteration. So we went from 500 students to 250 to 125 and so forth. But as we said on Monday, the powerful idea there was that if we doubled the size of that problem and all the kids from Justice or Ec 10 came back into the room and joined us, well, we could probably count that whole aggregate group with just 1 more big iteration of the loop because they would only maybe double the size or in Ec 10's case a bit more than double the size. And so we would have to spend a little bit more time, but we wouldn't have to spend 400 or 700 more steps. Just to paint this picture in a way that's a little less abstract, let's not have everyone stand up. But if those of you who chose to sit in the orchestra today wouldn't mind standing up, let's see if we can figure out among you who the tallest person is by doing the same sort of comparative algorithm. So if you're sitting in the orchestra, my apologies, but step 1, stand up; step 2, pair off with anyone nearby you, figure out who is taller, and sit down if you are shorter. Then repeat. [students murmuring] Okay. Okay. One is left standing. What's your name? >>Andrew. Andrew, you are the tallest person in the orchestra section today. Congratulations. [applause and cheering] Okay. Have a seat. So we found Andrew. But how long would it have taken me, for instance, to find Andrew in this orchestra section of 50+ or so people? I could have taken a fairly simple approach and start here. And I have 2 people stand up and I just compare them, and then I say to whoever is slightly shorter, "Okay, you sit down," and I'm going to remember who the taller person was. Then I repeat, repeat, repeat, and I hang on to the tallest person until I find someone slightly taller than them, at which point the slightly shorter person has to then sit down. But in that algorithm in this orchestra section, if there's n of you, how many steps is that algorithm going to take? >>[student] N. It's going to take n, right, because in the worst case, so to speak, the tallest person is the very last person that I get to just by random bad luck. So in the worst case, the running time of that algorithm is linear, it's n, where n is the total number of people in the space, the size of the problem. What about this algorithm? The fact that you all stood up and then again half of you sat down, half of you sat down, half of you sat down. How many steps should that have taken if there's n of you here? [student] N log n. >>That would be worse. Log n. So log n, even if you don't quite remember what a logarithm is, for now, just appreciate that it relates somehow to this halving and halving and halving. It doesn't have to be a factor of 2. It could be a factor of 3. But it's this repetition of the same kind of factor such that the size of the problem starts here but then immediately goes here, then here, then here, then here. You're not taking small bites out of the problem, you're really chopping away at it with a big fell swoop each time. So we had 50 people, then 25, then 12½ or 13 people standing, then 6½ and so forth until finally just Andrew was left standing. So we're going to call that log of n, and you can visualize this as follows. Recall this picture here where a linear algorithm is like the red line there, the yellow line was the counting by 2s algorithm that we used for counting students in the past, but today the holy grail is going to remain this green line where if we doubled the number of people in the orchestra section or just said, hell, let's have everyone in the whole room stand up, not such a big deal because we roughly double how many people are down here, 1 more iteration, not a problem. We've found Andrew or whoever happens to be taller than Andrew in the mezzanine or in the balcony. So this simple idea that we took so much for granted in a phone book, realize that there are so many different places in which we can apply it. Just to slap some jargon--actually, rather than jargon first, let me go to this picture here. Right now we talked about n and n/2 and then log of n, but we can certainly come up with, as we will over the course of the semester, other sort of mathematical formulas to describe this general notion of running time. These are out of context for now because we'll see before long algorithms that these actually represent. But notice here the linear line n, the straight line, is actually very low pointing right now. That's sort of an optical illusion in that we just change what the x axis represents and the y axis, and we can make a straight line point in any direction we want. But the reason that it's so seemingly flat now is because we needed to make room on this graph for much slower running times. For now, know that there are some pretty bad algorithms in life, some of which don't take n steps or, better yet, log n steps but more. So above the line n here at the bottom notice there's n times log of n, and we'll see what this means before long. Above that is n squared, and we haven't seen any n squared algorithms yet but we're about to. And that looks really bad. There's 2 to the n, something exponential, which feels even worse. And yet, curiously, then there's n cubed, which if you're sort of thinking ahead, if you kind of do the math, 2 to the n actually becomes much straighter, much higher up than n cubed if you look at the axes far enough out. So notice right now these axes are arbitrarily 2 to 10 on the x axis. And what does that mean? That means 2 people to 10 people in the room. That's all x means: size of problem, whatever the context is. And a vertical axis right now is number of seconds or number of steps-- some unit of time. But notice that it's 0 to 60 and 0 to 10. But if we kind of zoom out, as you might in Excel or some charting software, and we go up to 200,000, notice that something like 2 to the n is going to completely overwhelm the running times of n squared, n cubed, n log n--everything we've talked about thus far. And yet the catch is when you start talking about things like Facebook where you have many, many, many people all interconnected, you have n people, each of whom might have as many as n friends if everyone is sort of buddy-buddy in the world, well, that's n times n already, so that's n squared possible friendships, at least in 1 direction, n squared possible friendships. So that already suggests that searching Facebook's social graph, so to speak, can start to be expressed in these kinds of formulas. We'll come back and make this much more concrete, but for now, the objective for the next many weeks is going to be sure not to go about implementing algorithms or code that end up taking as much time as something like this. But the fascinating thing about computer science if you continue on in this field taking classes like CS121, CS124, both of which are theory courses, is that there are actually some problems that exist in this world that fundamentally, as far as we know, cannot be solved any faster than the worst of these graphs actually suggests. So there's a lot of open problems in this world to do much better than humans have thus far. So let's start then with this example. We saw Sean struggle with this on camera, all too awkwardly on video. But the reality was when Sean was tasked with finding on a board like this the number 7, recall that I said that, "There is somewhere behind these pieces of paper or white doors "the number 7. Sean, find it for us." And it was wonderfully awkward to watch because he was really struggling with this problem. But the reality was Sean did as well as anyone in the room could have done. He took a little longer than a typical person might have, but he assumed that there was some trick to this problem, he assumed that he was missing something. And it didn't help that hundreds of eyes were bearing down on him. But the reality was if the input to the problem is a bunch of random numbers and you're being asked to find 1 such number, the best you can do is linear search. Start at the left, move to the right, or start at the right, move to the left. Retroactively, we might be thinking, "Sean, why didn't you just start from the other end?" Well, 7 could have just as easily been here randomly, but I deliberately put it there because I figured he's not going to start at the end. So I kind of manipulated the situation, but by random chance 7 could have been anywhere. So starting from the right end might have been better then, but what if the next year I move 7 elsewhere? That's not a fundamentally new solution to the problem-- starting from 1 end or the other--when you're given no other assumptions. So Sean started looking through the numbers and he said, "5. That's not here." Then he went here and saw 19, then he paused for about 20 seconds, then he opened this for 13, and then it became apparent that there doesn't seem to be a pattern here. It wasn't 1, 2, 3, 4 or the like. There were gaps in the numbers, which didn't help. And too, the fact that I used these cheap pieces of paper to cover up the numbers is actually deliberate, because if I removed all these pieces of paper, most of us, Sean included, probably would have glanced sort of macroscopically at the blackboard and said, "Oh, 7 is obviously right there." We did it instantly. And that might be the way the human brain works to some extent, but in reality, his eyes or mind was probably skimming the numbers from right to left, left to right, middle on out--something was going on physiologically such that it felt like it was happening instantly, but odds are even internally there was some kind of methodology to finding 7. And indeed, now that we're talking about arrays and data structures and memory inside of a computer, the only thing we humans can do is look at individual memory locations 1 at a time. So every other location might as well be covered up with some piece of paper because we can't see it anyway. We can only do 1 thing at a time. So in this case, in Sean's case, we went here and then we went here and then we went here, here, here, here, got clever by the end and just kind of skipped this one arbitrarily and found 7 there. This one wasn't particularly special. It too was out of order. But he finally found 7. But now the takeaway really is that the best you can do when given no information other than randomly sorted numbers is to start from the left or start from the right. Or heck, you can randomly open up doors, but even then what does it mean to be random? Well, we'd have to somehow formalize what it means to start here, then go here, then go here. Sean did great, and it was just fun to watch. What if instead we change the problem a little bit and bring up this year's Sean, if you will? Would anyone be comfortable coming up on stage and solving a slightly different problem and appearing on camera? Let's go beyond the orchestra because you guys have been quite involved today already. How about in pink, in the hat? Come on down. What is your name? >>Alex. >>Alex. Okay. So Alex will be this year's Sean and will appear in the next several years worth of CS50 lectures. Alex, nice to meet you. >>Nice to meet you too. The challenge at hand for you is that you have it a bit easier in that I'm telling you the same numbers are here, but they are now sorted. So now your goal is to find the number 7. And actually, we should really make this--you're kind of cheating, like a computer would not, by looking at what the numbers were a moment ago. With chalk this actually isn't going to help all that much, but let's pretend that you don't know what the original array is. All you know now is that you have an array of sorted numbers that might have gaps between them, and your goal is to find the number 7. How would you, a reasonable human being, go about finding the number 7? Go from low to high? >>Okay. Go low to high. And don't tear them off. Let's just lift them up so we can reuse them. Okay, so 1. Wait. Before you keep going, that was 1, clearly wrong. So what's going through your mind next? What's your next move? The next one. >>Okay. The next one. Good. 3, so incorrect. What's your next move? Keep on going. >>All right. Keep on going. 5. So keep on going, and let me hand you this for posterity. 7. >>Excellent. Very good. Found the number 7. [applause] So that was good, but Sean too found the number 7. And I argue that you haven't really exploited this additional piece of information, which is that these numbers are sorted. So can we do better? Any suggestions here? Yeah, in back. [student] Binary search. >>I have no idea what binary search is. [student] Start in the middle. >>Start in the middle. Okay. So let's see if we can get there. So if instead you're told start from the middle, go ahead and open up the middle door. There's 8 of them, so you're going to have to arbitrarily choose the one slightly to the left or to the right. Okay. 7! [applause] Very nice. Okay, but where were we going with this? Let's suppose just to break the tie you had started here because that equally could have happened as well. We just happened to know that 7 was there. So this is 13. So if they're sorted and we just started in the middle, what would the optimal next move have been? Go the left. And so here comes the phone book example again. If 13 is here and we know the list is sorted, then all of these pieces of paper are uninteresting to us now because we already know that 7 must be to the left if these numbers are sorted and we found 13. So what's your next move here? >>Go to the left. >>Okay, good. So go to the left, and--wait, hey, hey, hey. That's cheating. So you found 7, but what was the algorithm we just applied? Start in the middle. >>Good. So what's the logical extension of that same idea? Oh, for just these. >>Exactly. >>So I start here. >>Good. So now we went slightly to the left again. It's 3. But the interesting takeaway now is which one do you not have to care about? These 2. >>These 2. So now this one can go away, this one can go away. Now the problem that was 8 then was size 4 now is size 2. We're getting pretty close. Again, go to the middle of these 2 elements. Okay. So it's sort of unfortunate that now we're always going left because we're rounding down. But that's fine because now we throw this away and everything else, leaving us with just 7. Let's give a round of applause. We found 7 again. [applause] Okay. Sure. Hang on for just 1 more second. Even though that next process kind of took a little longer than we felt it would, frankly, your first instincts were the best, right? We found 7 instantaneously. But we would have found 7 faster, no matter what, in this example versus this one because if the numbers are all sorted, much like the pages in a phone book, you can indeed chop half of the problem out again and again and again. And it's not quite as easy to see this with just 8 numbers as opposed to a 1,000-page phone book where you really see it visually, but in this case here when Sean was searching for 7, how many steps in the worst case would it have taken him? >>[student] 7. 7 in the worst case. Well, in the worst case not 7 if there's 8 doors here. It would have taken him 8 steps. So if there's n doors, it might have taken Sean a couple years ago n steps. Now, in your case, Alex, given that these numbers are sorted-- and we can kind of infer this from where we've been thus far in this story-- what's the running time of Alex's more intelligent algorithm of starting from the middle and then repeating? [student] 3. >>So it's going to be 3, roughly, if you go from 8 to 4 to 2 to 1. So 3 steps or, more generally, that's log n again. Any time you're halving and halving and halving and halving, that's an expression of this idea of log n. And so that would have taken you only 3 steps, and indeed it did once we opened the doors halving and halving, whereas this would have taken Sean some 7 or 8 steps. So thank you for being with us this year. >>Thank you. Nice meeting you. Thank you to Alex. >>Likewise. [applause] What's then the real implication of this? Now imagine that it's not 8 doors, which, frankly, all of us could find something behind 8 doors pretty quickly just by tearing the pieces of paper and going with our instincts. But what if it's a million doors? What if it's 4 billion doors? In the case of 4 billion doors, you're really going to want to go with Alex's algorithm, binary search as we'll start calling it or divide and conquer, more generally, where you keep halving and halving the problem, because if you have 4 billion doors, how many times can you chop 4 billion in half? [student] 32. >>It's actually 32. You can work this out on a piece of paper or in your head. You go 4 billion to 2 billion to 1 billion to half a billion, to 250 million, dot, dot, dot. And if you do out the math, you're going to indeed get 32, and that actually relates to computer science because we usually count in powers of 2. 2 to the 32 happens to be 4 billion. So there's a lot of relevance to these kinds of powers of 2 in computer science. But what about 8 billion? How many steps is that going to take if there are 8 billion doors? [student] 33. >>So 33. What if there's 16 billion doors? How many steps is that going to take? [student] 34. >>34. We could kind of continue this ad nauseam. But that's a powerful thing. You can introduce billions of more inputs to your problem but, no big deal, you just take 1 additional bite out of it and thus gives us something like binary search or divide and conquer, more generally. But I'm kind of cheating here, right? In the case of Alex's algorithm, she had an advantage over Sean. She knew that these numbers were sorted, but Alex did not have to sort them herself. I in advance came up to the blackboard and kind of made sure that I drew them all out in sorted order, then I covered them with paper. But how much work did that take me? If we had started off with these numbers in some seemingly random order-- in this case these simpler numbers, 1 through 8 here-- how do we go about sorting these values? If you were a human given this task, what kind of intuitive approach would you take to sorting a whole bunch of numbers? These things were laid out as puzzle pieces. Yeah. [student] I would take each number and compare it to each one and keep going to the left. >>Okay, good. So take each number, compare it to the one next to it, and then just keep moving along the list, kind of rejiggering things as you go. So here we have a chance for maybe a few more folks to get involved. Do we have 8 more volunteers who would love to come up? A little less pressure since you're not the only one. 1, 2, 3, 4, 5, 6, 7, 8. Come on down. You guys are going to be the numbers 1 through 8. Let's see if we can't do this sorting for Alex much in the same way I did it in advance. 1, 2, 3, 4. Go ahead and if you would, line up on stage between the music stand and me here in the same order as the slide on the screen. Uh-oh. We'll work you into the next example. Oh, wait, wait. Here we go. Wait. The next example is now. Here you go. Number 8. Come on up. All right. Sort yourselves according to this. Slide just a little bit to the side of the music stand here. So we have 4, 2, 6--get in there, over here, right there--3. Yeah. Okay. You go over here. No, you stay there. Yeah, right there. No. I'm wrong. Right there. Okay, very good. Okay. So now let's sort them in an increasing order. How can I go about doing this? The algorithm that was proposed a moment ago was why don't we just compare the folks who are kind of next to each other and then fix any mistakes, moving from left to right. So here we have 4 and 2, obviously out of order. Let's swap you. Okay. So now I'm going to move down the line. 4 and 6, nope. [laughter] 6 and 8, pretty good. 8 and 1, let me swap you guys. All right. So 8 and 3, swap you guys. 8 and 7, let me swap you guys. 5 and 8, excellent. I give you a sorted list. All right. So not quite. But it's better because the bigger numbers--case in point 8-- have kind of bubbled up from the left over to the right. So I got 1 of them right, but it feels like this didn't quite solve the problem. So what would you propose we do next? >>[student] Keep doing it. >>We keep doing it. And realize, again, we set things up by just having all the humans sort of intelligently arrange themselves based on that picture, but now we have to be much more methodical. We have to be algorithmic about it as though we're writing code-- in this case verbal pseudocode. So let me just try that again. That worked pretty well. It didn't solve it. But when it doubt, just try and try again. So 2 and 4, didn't help anymore. 4 and 6. Ah! 6 and 1, slightly better now. 6 and 3, good. 6 and 7, 7 and 5, 7 and 8, good. And you know, I can probably ignore 8 now because he's at the end of the list. Maybe we don't have to worry about someone going past him. But let's see if that's a safe assumption. Now list is--damn--not sorted. Let's try this again. So 2 and 4, 4 and 1, 4 and 3. 4 and 6, good. 6 and 5, good. 6, 7, and 8, good. But notice, can I just stop here now and stop here now? [student] Yes. >>Yeah? What if one of you had been the number 9 all the way over there? It would have been sorted. >>Good. It would have been sorted the first time around. Good. So let's go back again. We're almost there. 1 and 2, 2 and 3, 3 and 4, 4 and 5, 5 and 6, 6 and 7, 7 and 8. I am done now but, again, I'm a computer that can only do what I'm told to do, and my only recollection now is that I actually just did a bit of work. Something changed here. So I haven't technically confirmed visually or algorithmically that this list is indeed sorted. So just for good measure, just to be anal about this, let's do this 1 more time. So 1 and 2, 2 and 3, 3 and 4. And you know what? Just for good measure, I'm going to keep track on my hand this time how many swaps I make just so that I know how much work I've actually done. 3 and 4, 4 and 5, 5 and 6, 6 and 7, 7 and 8. No swaps. So now I would legitimately be an idiot to do this again because if I did no work through this pass of the humans, then clearly that's going to happen again if none of them is sort of randomly adversarially moving themselves around. So now I can stop. Now let's ask the question, how much work did this actually take me? How many steps did that take? >>N squared. Yeah, so n squared. Where do you get n squared from? You have to check each num-- There is n numbers, and you have to check each number with the other n numbers. Good. >>So it's n squared. >>Good. So it feels like it could very well be n squared, right? There's n of these guys, 8 specifically in this case, but every time I went through this list I was comparing the first person against the second, the second against the third again and again and again, and when I got to the end, what did I do? I redid it. So if we generalize this explanation, we have n people and I'm making, obviously, 8 steps, n steps, every time I go through this algorithm. But how many times in the worst case do I have to go through this list of people? [student] N times. >>Probably n, right, because in the worst case, what's probably the worst case arrangement of these guys from the get-go? If they're completely reversed order because just suppose mentally, let's-- What's your name? >>Bowen. Bowen. Okay. So Bowen, come on over here for just a moment. Suppose that Bowen was here at the beginning of the algorithm, and we don't know what everyone else is, but Bowen here, according to this algorithm-- and if you want to just stroll with me--is going to bubble up, as he did the first time around, all the way to the end. But suppose that the person next to Bowen was the number 7. I have to go back and get number 7, which means I have to go all the way back here. Now I have to have that same stroll with the person who is number 7. But what if then number 6 was next to him as well? Then I have to go back and get 6. So again, on every iteration of this loop I'm talking to each of the n people, and I might have to make n of these strolls to make sure I'm pulling all of the biggest elements back and back and back to the very end of the list. So n things n times is just n times n or n squared. So here already we have an algorithm that's no longer n, that's no longer log n, it's actually worse than anything we've done before. So Alex kind of got lucky in that I did all of the work apparently up front for her, all of the expensive work, so that she could enjoy in this binary search algorithm, which is log of n. But this is consistent with Monday's theme. We gave a little bit more space, we used more bits, in order to speed up our running time. So much like there's this trade-off between time and space, there might also just be trade-offs between time spent up front sort of getting things ready to go and actually executing an algorithm like search. Let's try another one. If you guys wouldn't mind just quickly rearranging yourselves to match that again, let's try something slightly different where it's not quite as simple as just fix all the pairwise mistakes, which is super intuitive. Let's instead be a little more deliberate and do this. This one too I would propose is probably pretty intuitive. Let's select the smallest person from the list again and again. So here we go. 4, you are the smallest person I've thus seen so far, so I'm going to mentally remember that by just pointing at you for now. 2. Ooh! Forget about number 4. I just found the new smallest element in this list. I'm going to kind of remember that. 6, 8. Ooh! 1. Goodbye. So now I'm going to remember number 1. We know that 1 is the smallest, but I'm the computer. What if there's a 0? What if there's a -1? I have to keep going. So 3, 7, 5, nope. Okay. So number 1 was the smallest. Let me select you from the list--we'll go this way-- and put you arbitrarily at the beginning of the list. Now, wait a minute. I kind of cheated. If these guys represent not a list of 8 people but an array, 8 chunks of contiguous memory--do you mind stepping back for just a moment? There's actually no space for you right here. So how do we make space for--what's your name? >>Sammy. >>Sammy. How do we make space for Sammy? We move the n that are before me. >>Okay. So we could move the n people who are before him, so if you guys want to take 1 deliberate, dramatic step to the left. They all did that in unison, but last time I wrote some code, you can't sort of move many things all at once. We could do it in a loop, moving everyone once at a time. So if you guys wouldn't mind stepping back to the right, and Sammy, if you could step back because there's still no room for you, now let's do this. Where was Sammy a moment ago? Right there. So there's a gap there. So you could move into Sammy's spot. Now next person up and now next person, now next person. Now we have room for Sammy. Now, someone from the audience--that was good, that was correct, it felt a little time-consuming--what's faster? Yeah. [student] A new array? >>What's that? >>[student] A new array? >>Okay, good. So consistent with this theme of just trade-offs, why don't I just make a new array and then Sammy will be swimming in space in front of these people, for instance, and we can just start filling a new array altogether. That too would work. But I'm not interested in spending more space today. What's another approach? [student] Swap. >>Okay. We could just swap these 2 guys. What's your name? Mario. >>Mario. So Mario, you were currently here. Sammy, can you back up for just a moment? Mario was here. We don't have room for you anymore, so if you wouldn't mind going to where Sammy is, we'll put Sammy here, and now I'd argue that Sammy's swapping operation was much faster. We did 1 operation to swap these guys, or maybe 2 to swap these guys, but we didn't do 1, 2, 3, 4, so that feels better. Now, wait a minute. I kind of made the problem worse because number 4 was kind of close to the beginning. Now number 4 is a little closer to this end, but I didn't really know or care about that. So this is just bad luck that number 4 is a little farther away from its destined place. So let's now repeat this algorithm. To recap, as long as that story was, all we did was walk through the list looking for the smallest numbered person. So now let's do it again. We don't have to worry about Sammy anymore. We can just go here. Ooh! Number 2. That's a pretty small number. 6, 8, 4, 3, 7, 5. Okay, good. And thankfully, by coincidence, I don't have to move-- >>Willie. Willie because he's in his right place now. Let's do this again and ignore these 2 guys. 6. That's a pretty small number. Ooh! 8 is definitely bigger. 4. Let's focus on 4. Ooh! 3 is even better. 7 and 5. So what do we do now with-- >>Roger. >>Roger? Let's swap him with number 6. So if 6 and 3 would like to swap, we've now kind of gotten lucky in that 6 is closer to where she should be, but it's just coincidence here. So let's now go here. 8 is a pretty small number. Ooh! 4 is smaller. 6, 7, 5. What do we now do? >>Swap. >>Exactly. So now let's do this sort of faster. 8, 6, 7, 5. Where does 5 go? Good. Okay. 6, 7, 8. 6 gets to stay where she is. What's your name? >>Rosalie. Rosalie gets to stay where she is. 7 gets to-- Let's see. 7, 8. Okay. So 7 gets to stay where she is. What's your name? >>Amna. >>Amna. So Amna gets to stay where she is, and number 8 is already where he now should be. Okay, good. Feels like we're just creating work for ourselves here, though. What's ultimately the running time of this algorithm? If we think about these people not as 8 but as n? >>It's n. It's n steps, but we're checking every single time. Okay. N but you're checking every single time? Okay, but if it's n steps, shouldn't I have been able to sort you by just going 1, 2, 3, 4? Oh! Okay, that's a big difference. So n squared why? What's really happening? There's n people in this list, but to find the smallest person in the list in the worst case, how many steps do I have to take? >>N. N, right, because in the worst case, number 1 is all the way over there, so I have to go get him or her. And then when I finally realize 1 was the smallest, then it's pretty quick to swap them. But now I have to start from the beginning and look for who? The next smallest person, which is 2. Where in the worst case is 2? Oh, my God. It's all the way over here at the end. So now I've just done another n steps, another n steps. And if we've got n people and in the worst case the smallest person is n steps away, that's again n times n, and so we again have n squared. This isn't feeling so good. And in fact, even in the best case--suppose that they start off sorted-- how many steps does it take for me using this algorithm to sort these n people? N squared. >>I heard n squared. Why n squared? Because you still have to check every single time. >>Yeah. And you have to swap them. >>Even though we humans are kind of omniscient in the sense visually that we can just kind of see that this is sorted, a computer is not that smart. It's going to look here and here and here, but if what it's looking for is the smallest element, you only know that you found the smallest element by what point? Once you're at the end. But at that point you've only found the currently smallest element. You don't necessarily know anything else about the state of the world. So you have to go again and again and again. So this time I really do look dumb because I'm checking, okay, 2, you're the smallest, but I don't know that in total yet. 3, 4, 5, 6, 7, 8. Okay, good. 2 was indeed the smallest. Now let's find the next smallest. Okay. 3, you're currently the smallest. Let's see. 4, 5, 6, 7, 8. Okay, got lucky again. 3 was indeed in the right place. But I'm going to keep doing this again and again and again. How can we do ever so slightly better? Instead of having people bubble up pairwise from smallest to largest and instead of going back and forth through the list selecting the then smallest person, why don't we instead insert these people into a new list step by step? Let's try this. Now let me call this thing insertion sort. So here we are here. Number 1. I don't care about anyone else in this list. My goal right now is to put number 1 at the beginning of a sorted list. And I'm going to propose since I only have 8 chunks of memory, arbitrarily right now I am the wall between my supposedly unsorted list, and anyone who is behind me I'm going to claim is sorted. So now we have number 1. I want to insert him into my sorted list, so I'm just going to move my wall over here, and now I claim this list is sorted, this list is unsorted--at least so far as I know. I can't see all the numbers at once. Now I happen to encounter number 2. What do I do with him? I insert you now into the sorted list. But notice how easy that was. I just have to look. Number 1 is there. Oh, obviously 2 goes to the side of number 1. Now what do I do with 3? I insert you into the sorted list. But that was super easy. This is super easy, this is super easy, this is super easy, super easy, super easy. And now everything is sorted behind me, and how many steps did that take? [students] N. >>So it's only n. We got lucky. It was only n why? >>[student] Because the list was sorted. The list is already sorted. So we got lucky. But we designed an algorithm this time that harnesses that kind of luck, that best case scenario, by not wasting unnecessary time. So we now have what we'll call bubble sorts where people kind of bubble up pairwise. We now have selection sort where we pluck out the smallest person again and again. And now we have insertion sort where we sort of proactively put people where they belong in an increasingly sorted list. If we could, a round of applause for these guys here. [applause] Let's take our 5-minute break here. And when we come back, we will blow all of these algorithms out of the water with something better. All right. Thanks very much. You can keep those as souvenirs. All right. We are back. And to recap real fast, we had these 3 different approaches to sorting, the whole point of which was to get to the point where someone like Alex could search a list of numbers quicker than someone like Sean could. And even though we have such simple examples with 8 numbers, you could extrapolate easily to 8 web pages, 8 billion web pages, or 800 million friends on Facebook. So these algorithms can certainly scale to those kinds of values, and the ideas are ultimately the same. So bubble sort was the first where we kind of bubbled up the biggest person all the way to the right by swapping people pairwise. Then we had what we'll call selection sort where I a little more deliberately kept looking through the list, selecting the smallest number again and again and again, the logical result of which is that the list is eventually sorted. Then in the third one, I inserted people into their appropriate place, and we did a very contrived example in that the list was already sorted, but that was to send the message that in insertion sort's case, you can get lucky. If the numbers are already sorted, it's only going to take you n steps to confirm as much, whereas selection sort you're a little more tunnel vision and you don't ever realize that the list is already sorted. So let's see bubble sort in action here. In the following example, we're about to see vertical bars whose heights represent numbers so that we can sort of visualize sorting happen. The smaller the bar, the smaller the number; the bigger the bar, the bigger the number. And we'll play it at this default speed. It's going to move a little fast for now, but red is what's showing 2 bars being compared side by side. And if you watch closely, what happens is that if the bars are out of order, the smaller one gets moved to the left, the bigger one to the right, and then you keep advancing. So if we do this again and again, notice that the smallest bars are going to keep inching their way to the left and the biggest bars are going to keep inching their way to the right. And indeed, we're starting to see a pattern all the way on the right-hand side just like we saw 8 and then 7 eventually bubbling up to the far end of our human list. So this is going to very quickly get a bit tedious, so let me stop this for a moment. Let me change the speed to be much faster. I'm not changing the algorithm, I'm just making the animation happen faster. Still bubble sort, same algorithm, but now you can see much faster than our verbal demonstration that the biggest elements are indeed bubbling up to the top. As an aside, these little squares at the bottom left and bottom right are just little reminders as to how many comparisons you're doing. But for now, we can focus on the pyramid that's taking shape, and there it goes. The smallest element is on the left, the biggest on the right, and everything else in between. Now let's instead take a look at selection sort. I'm going to go ahead and hit Stop. We're going to get a new random set of bars. Selection sort, recall, goes through the list again and again and again, plucking out the smallest element. So here is selection sort. It looks like there's less work happening now because we're not comparing pairwise but we're just sort of cherry picking the smallest elements from right to left. That took very little time, so there's a dichotomy already. Just because an algorithm is said to take n squared time, like bubble sort and like selection sort, those are really worst case running times. For instance, in the case of, let's say, selection sort, I actually am selecting the smallest person and putting him or her here, then I'm doing it again, then I'm doing it again, but there was a slight optimization I could make. As soon as I moved number 1 here--Sammy in that case-- what did I need to do with him thereafter? >>[student] Leave him. Leave him, right? Nothing. I didn't need to ever talk to Sammy again because if I had selected the smallest element and put him here, why waste time going to the end of my entire list? On the next iteration let me actually move only to number 2, only to number 3. So in reality, I wasn't doing n things n times. I was doing n things, then n - 1 things, then n - 2 things, then n - 3 things, then n - 4, dot, dot, dot. We have a bit of a geometric series, which just means you're adding up progressively smaller numbers. Not n + n + n + n but n + 7 + 6 + 5 + 4 + 3 + 2 + 1. And what that generally works out to be-- I'm going to mess up my board here for just a moment-- that's going to work out to be something like n(n - 1)/2 if we just kind of look at the back of a math book where you have all the cheat sheets for the formulas. If you're just adding something n + n - 1 + n - 2, it works out to be something like this. And if we just kind of multiply this out, that's n squared minus n/2. I kept saying n squared, though, and that's because I was kind of taking a mental shortcut because in reality, n squared minus n divided by 2 is indeed the true number of steps that an algorithm like selection sort would take if we really counted up all of those comparisons and all of the little busy work we were doing. But frankly, once n gets to be like a million or a billion, who the heck cares if you're doing a billion squared minus a billion divided by 2? A billion squared is a huge number. You can take another billion off of it with - n. It's not such a big deal. So the bigger the numbers get, the less important these lower ordered terms are. Who cares if you divide by 2 if you're talking about quadrillions of numbers of steps? So in general, computer scientists tend to throw away everything but the biggest term, and we just kind of simplify the world and say that that algorithm took roughly n squared steps. That's the running time of an algorithm. So we'll come back to this in just a moment with some concrete examples, but for now, that's sort of the intuitive motivation behind just simplifying our world and talking about the most important terms rather than getting into all these fancy formulas. So that was selection sort, and we got a little lucky there. Let's look at insertion sort. Let me go ahead and start this one as well. Now notice the pattern that's happening is a little different, and we started with random numbers, but if we actually count up the number of steps in the worst case, if the list started completely in the right order, we would only take n steps to realize as much. But if the list were actually backwards--for instance, in this case here-- then notice we actually have to do a lot more work in this case. And it should kind of feel to you like this one is kind of working harder to get those smaller elements to the left, and that's because we got unlucky. The list was sorted accidentally in reverse. By contrast, with insertion sort if we mimic what we did with our humans here by starting with everyone sorted and then start, it's a pretty good algorithm, right? It's already, in fact, sorted. So let's try to summarize exactly how much time these things are taking us by introducing just a bit of jargon or notation that's actually much simpler than the fanciness sort of suggests. This thing here, this big O on the screen, is what a computer scientist will generally use to describe the worst case running time of an algorithm. Again, by worst case, it's totally context-dependent. What we mean by worst case totally varies based on the problem we're talking about. But in the case of sorting, what's the worst possible scenario? Everything is backwards because it just feels like that means a lot of work for us. I've jotted down a few of the algorithms that we've seen thus far: linear search, binary search like with the phone book or the pieces of paper, then bubble sort, selection sort, and insertion sort like we saw with our humans, and then 1 other that's eventually going to be called merge sort. So in linear search in the worst case, how many steps does it take to find the number 7 if there are n doors like Sean faced? >>[student] N. N. So we're going to write big O of n. I'm just going to fill in some blanks. This is just a grid of blanks. But in the best case with linear search, 7 might have been at the very start of the list, and Sean might have started looking at the start of the list. So if you're using linear search and just checking left to right or maybe right to left-- they're equivalent--in the best case how many steps might linear search, like Sean's algorithm, take? Just 1 step. So I'm going to say that's the omega notation. This is just capital omega. Omega is just the sexy way of saying best case running time. So in the best case the running time is a single step or constant number of steps-- 1 in this case--but in the worst case, big O, it is actually n steps. And this one here, theta, we're actually not going to look at right now. It's not relevant to this particular example. But now let's try binary search. In the worst case with binary search, how many steps is it going to take to find the number 7 or whatever we're looking for? >>[student] Log n. Still going to take log n because just like Alex got unlucky when we really worked through the problem methodically and she didn't find the number 7 until the very last door she looked at, even though, in fairness, she got to throw away certain doors along the way, binary search in the worst case has a running time of log n. And again, that speaks to this dividing and conquering. But what about in the best case? And Alex actually experienced that best case right when she came up on stage. How many steps did that take in binary search? >>[student] 1. 1, just because she got lucky. But that's fine because omega refers to best case scenarios, best case inputs, even if it's just random dumb luck. Now, this too we're going to just kind of leave blank for now. How about now bubble sort? In the worst case with bubble sort, everyone is in reverse order, so we have to do a lot of bubbling. But how many steps is that going to take in the worst case? >>[student] N squared. This was the n squared, because if you think about it, if the list is completely backwards--8 is over here, 1 is over here-- as thing start to bubble, the number 8 is going to move this way, this way, this way, this way, but where is the number 7 in the worst case? Here she is still over there. So we have to do it again and again. And that's where we get n steps, then n - 1 steps, then n - 2 steps. And if you take my word for it--that if you kind of multiply it out, it's roughly n squared in the end with some other terms that we'll just ignore for now-- then in the worst case bubble sort is n squared, give or take. But what about the best case with bubble sort? What is the best case scenario? All of the numbers are sorted already. And what was the heuristic I used, the trick I used, to realize that I had done no work and could therefore stop early? [student] Check it once. >>Check it once. But what was I doing along the way? I was keeping track of how many swaps I made. And I realized if I haven't counted any swaps on my fingers, then I've done no work. I certainly shouldn't try to do no work again, so I can just stop. So in the best case of bubble sort when the list is already sorted, what would you say the omega notation is, the best case running time? It's just n. We have to do some work, but we only have to do 1 stroll's worth of work. And here too I'm going to leave this part blank. And now selection sort. Selection sort had me plucking the smallest person again and again. And what did we say the running time of that was? That was n squared in the worst case. And unfortunately, in the best case it's also n squared because I don't have the sort of omniscient view of the whole world; I only know upon a full iteration that I've indeed found the smallest person. So selection sort kind of sucks in that sense, but the upside is it's kind of intuitive. It's pretty easy to code up because all you have to do is write a couple of nested for loops, typically, that goes through looking for the smallest element and then puts the smallest element where it belongs at the end of the list. So here too there's going to be a trade-off. The amount of time it takes you to think and to actually develop something by writing code could very well take more time if you want a better algorithm and faster performance. But if you really just kind of code something up quick and dirty and just kind of take the stupidest possible idea you can think of, that might take you a few minutes to code, but with large data sets your algorithm might take hours to run. And even I in graduate school would sometimes make these trade-offs. It would be 3am, I was trying to analyze some very large data set related to the security research I was doing, and it was either spend 5 minutes tweaking my program to analyze the data and go to sleep or spend 8 hours getting it just right so it runs instantly and not go to sleep. And so there too it's kind of a conscious decision. Less development time, more sleep. In retrospect, I probably shouldn't encourage that when the goal here is to optimize quality of the code, but that too in the real world is a very reasonable trade-off. Less time, less performance or vice versa. So here we finally get a chance to talk about theta. Theta notation is something computer scientists can bring up in conversation when big O and omega happen to be the same. You say theta to really send the message that this is kind of a tight bound. No matter whether the scenario is good or bad, it's n squared. So it's just not relevant in these stories here. Insertion sort is the last one we looked at, where I was just inserting everyone into the right place. In the best case what was the running time of insertion sort as we saw it here? [student] The best case? >>The best case. It was n because in the best case everyone sorted, and Sammy and no one else really had to move at all. They were already in their right place. So insertion sort in the best case is, in this case, n. But in the worst case it's kind of n squared. Why? If my list of humans is in reverse order, I first start with the number 8 and I insert him or her into the right position, which is right here. I kind of move to the side. These guys are unsorted, he or she is sorted. But now I happen to find who next? >>[student] 7. 7 in the worst case because it's in reverse order. So here is 7. Where does 7 belong? Definitely behind me. But now 7 actually belongs not immediately behind me but behind number 8, so I have to say, "Excuse me, number 8, can you please move this way "to make room for 7?" Now I encounter 6. "Oh, excuse me, number 8 and number 7, can you move to make room for 6?" So in other words, with insertion sort, even though I'm not doing much movement, the people behind me are doing a lot more work, and that's got to cost someone time. It's going to cost the computer time. So in the case of insertion sort we still suffer. If you start adding up the total number of steps, we end up hitting roughly n squared because these guys need to make room for the human to be inserted back into that list. And so in this case theta is just not applicable to the particular story at hand. That's all nice and good. We have these 3 different ways of talking about the running time. But what does this actually mean in real terms if we actually try to code up an algorithm? Let me propose that there's an even better algorithm out there that itself has some trade-offs. We're going to call it merge sort, and it's sort of this magical algorithm that just works faster somehow, and it's so easy to express, at least in pseudocode. The implementation of this algorithm merge sort is going to be as follows. When you're given n elements--n numbers, n people, whatever--first there's a sanity check. If n is less than 2, merge sort just stops. It returns, so to speak. Why would you stop if n is less than 2? >>[inaudible student response] Right. And again, n is not the number in the list, n is the size of the list. If n is less than 2, that means your list is either 1, where you're obviously sorted if it's 1 number, or 0, in which case there's nothing to sort, so we need this sort of base case. If the list is so short that there's just nothing to do, literally don't do anything. Return. Otherwise sort the left half of the elements, then sort the right half of the elements, then merge the 2 sorted halves. This kind of seems like a little cheat whereby I'm asking you how to sort elements and you're telling me, "Sort the left half, sort the right half." I'm like, "All right. How do you sort the left half?" "Sort the left half of the left half, sort the right half of the left half, and then done." You're kind of cyclically defining what it means to sort, but it turns out that's actually brilliant in this case. It's not truly this vicious cycle that never ends because it does end when? >>[student] When you reach 1 thing. When you reach 1 thing. So even though you might start with 8 people and I say, "Sort the left half of these people, these 4 people," then I say, "How do you sort the left half?" "Well, sort the 2 people here." And then you're like, "All right, fine." "How do you sort the left half of those people?" "Just sort this 1 person here." What's the brilliant revelation now? I have to sort 1 person. Done. I don't have to do any work. But now I have to sort this person, but they're a single person, nothing to do. So the magic apparently is in this third step: merge the sorted halves. So merge sort takes this brilliant insight that if you break a big problem down into 2 smaller, identically-sized problems and then just kind of glue the smaller solutions together at the end, I propose that we can do much, much better [tapping sound] than any of selection sort or insertion sort. I've actually been ignoring that for half an hour, but I really don't know what's going on outside today. [whirring sound] [laughter] So let's see if we can see this with a little help from our friend Rob Bowden. There are 2 big steps in the process of merge sort. First, continuously split the list of cups into halves until we have a bunch of lists with just 1 cup in them. Don't worry if a list contains an odd number and you can't make a perfectly clean cut between them. Just arbitrarily pick which list to include the extra cup in. So let's split these lists. Now we have 2 lists. Now we have 4 lists. Now we have 8 lists with a single cup in each list. So that's it for step 1. For step 2 we repeatedly merge pairs of lists using the merge algorithm we learned before. Merging 108 and 15 we end up with the list 15, 108. Merging 50 and 4 we end up with 4, 50. Merging 8 and 42 we end up with 8, 42. And merging 23 and 16 we end up with 16, 23. Now all our lists are of size 2. Notice that each of the 4 lists is sorted, so we can start merging pairs of lists again. Merging 15 and 108 and 4 and 50 we first take the 4, then the 15, then the 50, then the 108. Merging 8, 42 and 16, 23 we first take the 8, then the 16, then the 23, then the 42. So now we have just 2 lists of size 4, each of which is sorted. So now we merge these 2 lists. First we take the 4, then we take the 8, then we take the 15 and 16 and 23 and 42 and 50 and 108. And we're done. We now have a sorted list. Rob was kind of taking advantage of something that we haven't yet done. It was suggested, but we didn't actually do it. He was doing something physically with the cups that suggests he was spending some resource besides time. >>[student] Space. >>It was space. The fact that he had this sort of bi-level table where he had space up here and space down here was actually implying that he's using twice as much space as any of our algorithms thus far--insertion sort, bubble sort, or selection sort-- but he was leveraging this additional space to kind of move things back and forth while keeping things in order. And even though it feels like we got to a sorted list, that felt like it took a while. In reality, what Rob was doing was exactly this algorithm. He first took the problem of size n, divided it into a left half and a right half. That's when he moved the cups. Then he repeated that process. He divided 4 into 2 sets of 2 over here and over here. Then he repeated that process and divided 2 into 2 sets of 1 for each of those various cups. And that's where the brilliant opportunity arises. At that point in the story, Rob had 8 lists of size 1, all of which were sorted already. So then what did he proceed to do? Pairwise he took this sorted list and this sorted list and merged them. Then he took this one and merged them, then this one and merged them, then this one and merged them. And then what did he do next? He then re-merged the bigger lists and then re-merged the bigger lists. And if you think about this just intuitively for now, what was he really doing? He was dividing the problem in half, in half, in half, in half in order to get these super small lists. Then he was kind of combining double, double, double, double. So he was doing twice as much work as we've seen thus far with anything involving divide and conquer, but no big deal. Twice as much work is not such a big deal. It's just a constant factor. And much like our arithmetic expression before, I'm just going to cross out constant factors like times 2. Who cares? If it's 2 billions times 2, that's still a lot of steps. So this merging step seems to be the key insight. Let's walk through this just numerically before-- Oh, that's not to be continued yet. Let's walk through this numerically just to actually see how this plays out. This is mostly just a little poor man's animation. Let's propose this. The running time of merge sort--we just need a way of talking about this. This isn't math; this is just kind of a succinct way of expressing ourselves. So T represents time and n represents what? >>[student] The size of the-- [Malan] The size of the problem, the number of people. So I'm claiming that the running time to sort n people is going to be 0 amount of time if n is less than 2, because if you have 1 cup or no cups, you have nothing to sort. But more generally, I'm going to propose that the running time to sort n elements is going to be the time it takes to sort the left half plus the right half plus--what's this additional + n? >>[student] Merge sort. [Malan] It's actually merging, because if you have n/2 elements here and you have n/2 elements here, how much time does it take to merge them? Just like Rob, you have to pluck this one over here, maybe pluck over here, pluck over here, pluck over here, pluck over here. You have to touch each of the cups once. And if there's 4 cups plus 4 cups, that's 8 cups or, more generally, 8 n cups. So the merging step we can express as n, and that literally involves the number of times Rob physically touched one of those Styrofoam cups. So let's now do an arbitrary example. If there's 16 cups, what's the running time of sorting, using Rob's algorithm, 16 cups? It's 2 times the amount of time it takes to sort 8 cups because we have 8 cups here, 8 cups here. I don't know how long that takes, so we're generalizing it as T for the moment. Who knows what it is? But now I can sort of recursively or repeatedly ask the same question. How much time does it take to sort 8 cups? 8 cups I'm going to say takes the amount of time it takes to sort 4 cups plus 4 cups, then merging them together. Fine. We're getting into a cycle already. How long does it take to sort 4 cups? The time it takes to sort 4 cups is 2 cups plus 2 cups sorting plus the merging process. Fine. How long does it take to sort 2 cups? 2 cups is the amount of time it takes to sort 1 cup plus the time it takes to sort another cup plus the amount of time it takes to merge, which is just 2. Fine. Last question. How long does it take to sort 1 cup? Here is the base case that we predicted we'd hit earlier. The fact that it takes no work whatsoever to sort the smallest of the problems means that now, sort of grade school style, we can just go start plugging these numbers back in. We now know what T of 1 is, so I can plug in 0 for T of 1. That will give me the answer to T of 2, which I then can plug in higher up. That will give me T of 4, which I can plug in higher up. That will give me T of 8, which I can plug in higher up. And if I actually do out that math by plugging in these answers, I then get T of 16 is 64. And what does 64 represent? If T is 16, yeah, it's 16 times 4. So I claim now that the running time of this thing called merge sort-- and this is going to be the fanciest of the ones we've seen thus far-- is going to be called n log n because how many times can Rob split a whole bunch of cups in half? Log n. It's the same as the phone book example, it's the same as the self-counting example. How many times can you divide something in half? However, there's this merging step. You might have to divide the cups into half again and again and again, but every time you're going to have to merge. And we said earlier that merging n cups takes n steps because you have to pluck out a cup, pluck out a cup, and you have to touch every cup once, just like Rob did. So if we're doing something log n times and we're doing n things on each of those iterations, each of those halvings, we have n times log n. So if we plug in 16 in this example, 16 times log of 16-- don't worry about why this is the case for now because I've not drawn the base-- but log of base 2 of 16 is 4, 16 times 4 is 64. But by contrast, if we had used bubble sort or selection sort or insertion sort with 16 numbers, what would the running time have been if n is 16? It would be 16 squared, which is 256, which even if you haven't quite followed all the math, 256 is bigger than 64. That's really the magical takeaway here. And realize that working through this in smaller examples as you will on a pset makes it all much more intuitive. But what that really means in terms of the feel of this algorithm is this: If we actually look at merge sort here--let me pull it up in this window here-- this is a slightly different example whereby we have all 3 of these algorithms-- bubble, selection, and merge--just side by side. They have all started with random bars, and that's good. No one has a fundamental advantage over the other. I'm going to in a moment click each of these animations--Start, Start, Start-- as fast as I can so that, roughly, they all start at the same time, and let's consider that bubble sort's worse case running time is what? >>[student] N squared. N squared. Selection sort's worst case running time is? N squared. And merge sort is apparently--even if you didn't quite follow all the math now, it'll become much more intuitive over time--is, we claim, n times log n. And because log n is strictly less than n once we have big numbers, n times log n is smaller than n times n or n squared. So what does it feel to actually be a better algorithm in terms of running time, n times log n as opposed to n squared? Here we go. Click, click, click. That's what it means to use something like merge sort. We have a moment. Let's see what happens here. [chuckles] Whose money is on bubble sort? It rather depends on the input sometimes. Let's see. Come on. It feels like he's catching up. >>[student] Go, bubble sort! [students murmuring] [Malan] Yeah, yeah. [students murmuring] Go, go, go! [all cheering] [applause] So now with 1 last, final demo, if it's a little tricky to wrap your mind around the math or sort of the visualization there, you can actually hear the speeds of different algorithms differently. This is an animation someone made that actually associates sounds with the process of swapping and the height of the bars. As we'll see here, there's a few more sorting algorithms out there that folks have thought of. This first one is going to be insertion sort, and this will fly through and give you an audible sense of how these various algorithms work. Here is insertion sort. [electronic beeping] [Malan] Bubble sort. [faster electronic beeping] [Malan] Selection sort. [faster electronic beeping] [Malan] Merge sort. [electronic beeping] [beeping slows down] [laughter] [Malan] Gnome sort. [electronic beeping] This is CS50. We'll see you next week. [applause and cheering] [CS50.TV]