[MUSIC PLAYING]
DAVID J. MALAN: All right. So welcome back. This is CS50, and the is the end of week three.
So recall in the past several weeks, we've been spending quite a bit of time on C, on programming, on syntax. And it's quite normal, if you're still struggling with Problem Set 2, to be banging your head against the wall. It's cryptic-looking error messages and bugs that you can't quite chase down. Because, rest assured, that in just a few weeks' time you'll look back on things like Caesar, and [? V-genair, ?] maybe even Crack, and realize just how far you've come in a short period of time. So if that's any consolation, hang in there for now.
Today, though, we begin to transition to things higher level. And we start to take for granted that you guys know how to program, or at least the beginnings of that comfort level. And we'll start to consider how we can go about designing programs more effectively. How we can go about optimizing the efficiency of our algorithms, and generally solving more interesting problems. And starting to take for granted that, if we wanted to, we could code up any of the examples we have in mind. So today, we don't touch the keyboard for any form of code. It'll be much higher level, and ultimately, about problem-solving.
So to get to that point, let me propose that the following seven rectangles represent seven doors, behind which are a whole bunch of numbers, among which is the number 50. Let me project this on this screen here as well. And propose that we need a volunteer to help find me a number in front of the internet here to see. Come on up, in the pink. All right. What's your name?
JENNIFER: [INAUDIBLE]
DAVID J. MALAN: Sorry?
JENNIFER: Jennifer.
DAVID J. MALAN: Jennifer. All right, Jennifer. Nice to meet you. Come on up. So these here are seven doors, and what I'd like you to do for us here, in front of all of your classmates, is find us the number, 50. To find a number, you can peek behind any of these doors by simply tapping on one of the doors, and it will reveal its number. And let's see how quickly you can find us the number, 50.
15. 16. 50. Nicely done. All right. Round of applause for Jennifer.
[APPLAUSE]
All right. So what was your strategy for finding the number, 50?
JENNIFER: Um, I thought maybe if-- [INAUDIBLE]
DAVID J. MALAN: Oh. Give it one second. So was your strategy for finding the number, 50?
JENNIFER: So I just start at the beginning to see what the first number was, and then I thought, maybe if they're sorted, I'll just keep tapping higher up?
DAVID J. MALAN: OK. And we seem to have found that to be the case. Although, let's peel back the layers just a little bit, and you want to go ahead and reveal the other doors you could have chosen?
JENNIFER: Oh, dear.
DAVID J. MALAN: Ah.
JENNIFER: So I just got lucky.
DAVID J. MALAN: So you got lucky. All right. So not bad. But that's an interesting insight, right? If you assumed, and you did get, indeed, a bit lucky there. But if you assumed that the numbers were sorted, can you be more precise as to how that influenced your behavior?
JENNIFER: So if they were sorted, I thought maybe smallest to largest.
DAVID J. MALAN: OK.
JENNIFER: Or if this ended up being really big, then largest to smallest.
DAVID J. MALAN: OK. So largest to smallest, or smallest to largest. But let me propose, suppose you had gotten unlucky, and suppose that they were not, in fact, sorted, how many of those doors might you have had to peek behind in that worst case?
JENNIFER: All of them.
DAVID J. MALAN: All of them. So let's generalize that as n. There happens to be 7, but let's more generally say there's n doors on the screen here. So in the worst case, you would have to look behind 7 doors, or n doors. And so this really is, it's a bit of luck today, but it's really a linear algorithm of sorts, even though you were kind of skipping around. Is that fair?
JENNIFER: Yeah.
DAVID J. MALAN: Well, let me see if your strategy changes if I move us to our second example here with 7 different doors. Same numbers, but this time they are sorted. What's your strategy here going to be, trying to put out of your mind what the other numbers were--
JENNIFER: OK.
DAVID J. MALAN: --earlier?
JENNIFER: Let's start with the first one.
DAVID J. MALAN: All right. Start with the first one. 4. Now where you going to go, and why?
JENNIFER: 4 is really small. So if they're sort maybe smallest to largest, it should be twice that, and--.
DAVID J. MALAN: OK. Let's see, which you think?
JENNIFER: Try the last one. Nice.
DAVID J. MALAN: Very nicely done. All right.
[APPLAUSE]
DAVID J. MALAN: OK. So you're actually doing this horribly, because you're doing it very well. Which leaves us unable to make certain points. So let's try to roll back here.
JENNIFER: OK.
DAVID J. MALAN: Very well done, nonetheless. So you started at the beginning, you saw that it was 4, then you moved to the end. But suppose you didn't get lucky there, and suppose 50 was somewhere else. What your third step have been?
JENNIFER: Go back to the beginning.
DAVID J. MALAN: Go back to the beginning. OK, so you would've touched this door, which was 8. All right. So that's not 50. Where would you have looked next?
JENNIFER: If I didn't know they sorted.
DAVID J. MALAN: Correct. Well, if you did know they were sorted--
JENNIFER: Oh, did know, yeah.
DAVID J. MALAN: --but you didn't know where 50 was yet?
JENNIFER: Just keep going.
DAVID J. MALAN: All right. OK. Keep going. OK, that I can work with.
JENNIFER: OK.
DAVID J. MALAN: Now, if you're just going to keep going, what's your algorithm devolving backed into.
JENNIFER: The linear--.
DAVID J. MALAN: It is kind of linear. But let me propose, let me put on the spot. Let me refresh the page. same number, same arrangement, same doors. But think back to that first day in class when we tore a phone book in half, sort of, and what was our strategy there?
JENNIFER: Start at the middle.
DAVID J. MALAN: OK. So start at the middle. So let's go ahead and simulate that. Start at the middle by revealing that door. So the number 16. So what would the strong guy have done, who tore the phone book in half, to get to the next guess?
JENNIFER: Go in this half.
DAVID J. MALAN: And why to the right?
JENNIFER: If they were sort of smallest to largest, then 50 should be at that end.
DAVID J. MALAN: Good. Totally reasonable. So like a phone book, you go to the right as opposed to the left, but here is the key takeaway. You now can throw away, or tear off, half of this problem, leaving you not with 7 doors, but really with just 3. Which is roughly half of the size of the problem. All right. So now what you would have done after you go right?
JENNIFER: So 16 is still pretty small, relative to 50, so maybe I'll try, like, this one.
DAVID J. MALAN: All right. 42. All right, so now what's your instinct telling you?
JENNIFER: I can throw away this and then just--
DAVID J. MALAN: OK. Good, you can throw away the left half there.
JENNIFER: --pick this one.
DAVID J. MALAN: And the right.
JENNIFER: Yeah.
DAVID J. MALAN: So even though it's hard to see perhaps, when there's only 7 doors, think about, now, the consistency of the algorithm you just applied. In the previous case, you did get lucky, which was great. But you did use a heuristic, I would say. You used sort of your instincts, and knowing it sorted, if it's pretty small at the beginning, obviously, we've got to go more to the right. But in some sense, you got lucky, because maybe this was the number 100, and maybe 50 was more in the middle. Maybe 50 was even over here.
But what you did a little differently this time was, you did the same thing again and again. And I would argue that what you just did, albeit influenced by the phone book example, is something much more algorithmic, and much less special cased. Much less instinctive. So in the end of the day, how would you describe the efficiency of the first algorithm, where you went left to right, versus the second algorithm here?
JENNIFER: This one should, like, maybe halve the time, or even more, yeah.
DAVID J. MALAN: OK, maybe even more. Let's push a little harder on that. What really, if we continue this logic, we definitely halved the running time with this second algorithm by throwing away half of the numbers, but what did we do on the next iteration, when Jennifer revealed the second number?
We halved the numbers of doors again. And then what did we do after that, if there were more doors to play with? We would halve them, and again, and again, and again. And this was just like you guys all standing up at the first week of class, half of you sitting down, half of you sitting down, half of you sitting down, until one lone soul was standing. And we said that the running time of that, the number of steps it took was on the order of what?
SPEAKER 1: [INAUDIBLE]
DAVID J. MALAN: So log base 2 of n, or just more simply, log of n. So something logarithmic. And the graph wasn't a straight line that just got worse and worse, it was this interesting curve that didn't get so bad over time. So let's hold on to this idea. Let's thank Jennifer. Thanks so much for coming on up. And, one sec. No desk lamps today, but we do have CS50 stress balls.
JENNIFER: Yay.
DAVID J. MALAN: All right, here. Thank you for incurring the stress up here. All right. So let's see if we can't now formalize this a bit more. So again, what we just did was essentially the same thing as we did in that first week. But rather than end with just a linear algorithm, which we depicted previously as this straight line, whereby, if we put one more door on the screen, then Jennifer would have had to look, potentially, behind one more door. If we put two more doors, she might have to look behind two more doors.
And so, there was this linear relationship between the size of the problem on, say, the x-axis, and the amount of time it takes to solve on the y. But the picture I was alluding to earlier was this green line. Green deliberately, because it just felt better. In theory, the algorithm, when we did it with the phone book, when we did it with you guys counting each other, and in the second case, when Jennifer just did it up here, it was sort of fundamentally better. Because it wasn't just twice as fast. It wasn't even four times as fast. It was entirely dependent on what the size of the input was, as to how many steps it ultimately took.
And so this simple idea that we all took for granted with the phone book, can similarly be applied to something like this. And this might be more casually known as, as you might imagine, divide and conquer. Not unlike what we did, of course, with the phone book.
But the pseudocode, recall, was this. So we won't do this again, but recall that first week, all of us stood up and then half of you sat down, half of you sat down, half of you sat down. That algorithm was implemented in a bit of a cheating way, in that, it wasn't just one of me counting, fundamentally, more efficiently. In that case, I was leveraging a secondary resource. Sort of, multiple CPUs, multiple brains, multiple smart people in the room were helping me get from something linear to something logarithmic, from something red to something green.
But in this case, Jennifer alone can fundamentally improve upon the performance of her first algorithm by, again, just thinking a little harder. And now, when it comes time to implement these things, figuring out what lines of code you can write such that you can repeat them again, and again, and again, sort of in a looping fashion. Because you're not going to have the luxury, like Jennifer did at first, to just have a whole bunch of ifs and say, hmm, if this first number is 4, let me jump all the way to the end. Ooh,if that number's too big, let me move arbitrarily back to the second element. You'll find that it's going to be a lot harder to formalize what we humans take for granted as very reasonable heuristics, but a computer is only going to do what you tell it to do.
Now this has very interesting implications. This graph is sort of meant to sort of overwhelm visually, but notice, where is the straight line in this graph? Where is the linear graph that we call n? Well, it's sort of toward the bottom of this picture, right? So all we've done is we've sort of zoomed out to the x-axis and the y-axis to try to get a sense of what other types of curves look like.
And the specifics of the mathematical expressions today won't matter so much, but notice that there's a lot of algorithms that are far worse than something that's linear. Indeed, n cubed looks pretty bad. 2 to the n looks pretty bad. n squared looks pretty bad. And we'll see what some of those might be in reality today. And log n doesn't feel as bad, but better than n is log base 2 of n. But you know, it would have been even more amazing if Jennifer, or if we, that first week, had come up with something that's log of log of n.
So in other words, there's this whole range of possible solutions to problems, but even here, notice what's going to happen. When I zoom out, which of these curves is going to prove to be the absolute worst of the ones on the screen now? So n cubed looks pretty bad at the moment. But if we zoom out and see more of the x and the y-axis, who's going to dominate ultimately? So it actually turns out that 2 to the n, and you can figure this out just by plugging in some increasingly large numbers, and you'll see that 2 to the n, indeed, gets bigger much faster. If we really zoom out, a 2 to the n algorithm absolutely sucks. I mean this is going to take quite a bit of time for the computer to churn through.
But you'll see over time, especially with future problem sets and even final projects, is your data set gets large, all right? Even in the first version of Facebook, as the number of friends, and the number of registered users got large, you can sort of phone it in and implement something with linear search, or a very simple sorting algorithm, as we'll see today. You have to start thinking harder and harder about these problems. And the types of problems places like Facebook, and Google, and Microsoft, and others work on is exactly these sort of big data sort of questions increasingly these days.
All right. So Jennifer's success in that second algorithm, frankly, she did amazingly well the first time, but let's write it as luck so that we can make this point. In the second case, she leveraged an algorithm that repeated again and again, but she took for granted a certain assumption that we allowed her, but she exploited some detail the second time that she didn't have the first time. Which was what?
That the list was sorted. So as soon as the list was sorted, we claim that Jennifer was able to do fundamentally better. 7 doors, yes, is not that interesting, but suppose it we're 7 million doors. Log of n is definitely going to perform much, much faster in the long run. But she had to have the doors sorted for her. Now, I took the liberty of doing that in advance on the computer screen here, but suppose that Jennifer had to do that herself? Suppose that the doors in question represented data in a database, or friends registered for Facebook, or any web pages on the internet that various websites might need to index or search over.
Suppose that you just had a raw data set and it was left to you, or to Jennifer to do that sorting? That, rather, requires that we answer the question, well, how much time would have taken Jennifer, or even me, to sort those numbers in advance so that she could take advantage of that? Right? Because the implication, of course, is if it takes me quite a while to sort the numbers, who the heck cares that you can find a number like 50 so fast, as in Jennifer's case, if we more than overwhelmed the amount of total time it took by sorting things in advance?
So let's see if we can't the paint the picture here. I have a whole bunch more stress balls, if that helps break the ice here. And if you wouldn't mind, we need seven volunteer-- on, OK. Wow. So we don't have to spend on desk lamps, it seems. All right. So how about you two in front. How about you two guys in back. So that's four. How about you in front five, six and seven. Right there. Your friend's pointing you out, so you get the prize.
All right. Come on up. And why don't we have you guys come on over here. I'm going to give you each a number. And go ahead and arrange yourselves identically to what's depicted on the screen.
[INTERPOSING VOICES]
DAVID J. MALAN: Oop, sorry. Bug. All right. Well, here we go. Number five. Number six. One, two, three, four, five, six, seven. Oh, this is awkward.
SPEAKER 2: I'll just get a--.
DAVID J. MALAN: Good deal. All right. Thank you for participating.
[APPLAUSE]
OK. All right. So we have four, two, six, one, three, seven, five. Perfect so we have seven volunteers here who are equal in width to the array that we're playing with the earlier. And I chose seven for reasons that will be just convenient in a little bit. And I'm going to propose first that we sort these seven volunteers. If you'd like, first, to say hello though. Since this is going to be an awkward several minutes. Introduce yourselves.
GRACE: Hi, I'm Grace. I'm a sophomore in Leverett House.
BRANSON: Hi. I'm Branson. I'm a freshman in Weld.
GABE: Hi. I'm Gabe. I'm a junior in Cabot.
NEIL: I'm Neil. I'm a freshman in Matthews.
JASON: I'm Jason. I'm a freshman in Greenough.
MIKE : I'm Mike. I'm a freshman in Grays.
JESS: I'm Jess. I'm a sophomore in Leverett.
DAVID J. MALAN: Excellent. All right. Well, thank you to all of our volunteers here thus far. And the challenge at hand now is going to be to sort of these guys, but then we're going to have to think a little hard about how efficiently we actually sorted them. So let's first try this. You guys can see each other's numbers just by placing around the corners. Go ahead and take a few seconds, and sort yourselves from smallest on the left to largest on the right. Go.
OK. Good. That was really darn fast. Now someone here, what was the algorithm that these guys applied?
SPEAKER 1: Least to greatest.
DAVID J. MALAN: OK. Least to greatest is really sort of the objective, but I'm not sure that's really an algorithm. Least to greatest doesn't tell me step-by-step what to do. Yeah?
SPEAKER 1: [INAUDIBLE]
DAVID J. MALAN: OK. So if you see a person smaller than your number, then move to the right of them. So that's now getting more expressive, more like an algorithm, because you can say, if this, then that. So we have some kind of conditional construct. And these guys seemed to do that a few times, because some of you moved a bit of a distance. So there was presumably some kind of looping going on in their minds.
But let's try to formalize that. If you guys could reset back to this arrangement. Let's see if we can't formalize this a bit, and then ask the question, just how efficient is this? Of course, when we do this more slowly, it's going to feel as good of an algorithm, but let's see if we can put our fingers on the precise steps.
So you two guys are four and two. Or you correct or incorrect order? Obviously incorrect. So we swapped. Now I'm going to move aside here and say, four to six. Are you correct or incorrect?
GABE: Correct.
DAVID J. MALAN: Correct. Six and one? Nope. Swap. So that's two swaps. Six and three? Nope. Swap. Six and seven? Looks good. Seven and five?
JESS: [INAUDIBLE]
DAVID J. MALAN: OK, swap. And sorted. All right. So obviously not, right? So there was more going on. But, indeed, these guys, even just instinctively. kept moving. They didn't just stop, once they corrected one problem. So. Indeed, I'm going to have to do the same thing. I'm going to have to sort of rewind back to the beginning of this problem, or the beginning of this array of people, let's start calling them.
And now what should my algorithm on the second pass be?
SPEAKER 1: Same thing.
DAVID J. MALAN: Same thing. And this, I'm starting to like, right? As soon as you can find yourself doing the same thing again and again, that's becoming more like an algorithm, and less human instinct.
So now, here we go again. Two and four? No. Four and one? Ah, there was indeed some work still to be done. For and three? Good. Four and six? Six and five? Six and seven? OK, now, done. OK, no. I have to go back.
So now, again, we're doing this a little more deliberately. And now, there's just one brain executing this algorithm. One CPU, if you will. And frankly, that's the only resource we're going to have access to. And once we do go back to a keyboard and have something like C at our disposal, we're only writing a program that can do one thing at a time. Whereas, these guys a moment ago, we leveraged their collective brainpower like you guys did in week zero. So let's keep doing this.
Two and one. Two and three. Three and four. Four and five. Five and six. Six and seven. Done? So I am, but let me play devil's advocate. Do I, the sort of computer who just made a pass through this array of people, know that I'm done?
SPEAKER 1: No.
DAVID J. MALAN: So why? What would I have to do in order to conclude decisively that I am done? Probably one more pass. Right? Because all I know from that previous pass is that I corrected a mistake. And that means, maybe there's still another mistake that I need to correct. So I can only be sure by rewinding, and then checking, one to two, two and three, three and four, four and five, five and six, six and seven. OK, now I did no work.
I can certainly remember that I did no work with something like a variable, like an int. Call it swaps, and if swaps is 0 once I get here, and it started at 0, then I would just be stupid to keep going back and forth, checking again, and again, and again, right? Because you get stuck in some kind of infinite loop. So as soon as there's 0 swaps, we can claim that this algorithm is indeed complete.
Now, let's put a name on this. The algorithm that I propose we just implemented is something called bubble sort, known as such in the sense that the numbers that are bigger kind of bubble their way up to the top, or up to the end of the array of numbers. But how efficient was this algorithm? How many steps did I physically have to take, for instance, to sort these seven humans?
Four to five? OK, too many is ultimately going to be the answer. But even then, the specific number isn't so interesting. Let's generalize it as n. So if I had n people up here, and they were, sort of, in random order at the beginning, in that original order. Well, how many steps did I have to take on the first pass? It was one, two, three, four, five, six, and they're seven people, so that's seven, six--, so that's n minus one steps the first time.
Now, how many steps did I have to take when I rewound? Well, we could actually double that if we really wanted to, but for now, I'm just going to say, all right, another n minus 1. So the n minus 1 is going to get annoying to keep track of, so let's just round up slightly. So 2n steps. So 14 steps, give or take.
How many times did I take a step the next time? Well, it's 3n. really. And now, in the worst case, for instance, how many times would I have gone back and forth, back and forth, executing this algorithm, swapping people on each pass, roughly? It's actually n squared, right?
Because in the worst case, you can kind of think about this intuitively, even though it might take a little bit of time to sink in. In the worst case, what would these seven people have looked like, in terms of the arrangement of their numbers? Completely backwards, right? And just to simulate that, what was your name again?
MIKE : Mike.
DAVID J. MALAN: Mike? OK, Mike, can you just join me over here for just one second? Actually, no. Sorry Mike, let's rewind. What's your name again?
NEIL: Neil.
DAVID J. MALAN: Neil. OK, Neil, you come with me, if you don't mind. So I'm going to propose, just for simplicity, that Neil is now in his worst possible case. But recall how I implemented my algorithm. I'm comparing, comparing, comparing, comparing, comparing, oh. Now these guys are out of order, so I fix. So you guys swap. But consider now, how much farther does Neil have to go? It's roughly n. You know, it's not actually n. It's like, n minus 1, but I'm getting annoyed keeping track of the little number, so let's just call it n.
So if Neil moves one step maximally each time, and to move Neil one step, I have to make this really tedious pass back and forth, this is roughly doing this, n steps, a total of n times, because it's going to take me that many steps to get Neil all the way to where he belongs. Let alone everyone else if you guys were all mis-ordered as well.
So let's call bubble sort n squared. The running time of this algorithm, the performance of this algorithm, the efficiency of this algorithm, we shall just describe more generally as n squared. Which is nice, because I could do the same example with eight people, nine people, a million people, and that answer is not going to change.
So if you guys wouldn't mind, let's reset you to where you started. And let's try two other approaches and see if we can't do fundamentally better than this. So this time, I'm going to propose a sort of different algorithm. That was very clever of us last time, and you guys were right to have the right instincts of just kind of swapping pairwise. But if I really wanted to approach this simply, and my goal is to move all of the little numbers this way, and push all of the big numbers that way, why don't I just do that in the most naive way possible and see if I can do better than what was a fairly complex algorithm?
So let's see. Four is a pretty small number, so I'm going to leave you there moment. Ooh, number two is even better. So can you just step forward for a moment? This is currently my smallest numbered candidate, and I'm going to remember that with, like, a variable. But I'm going to keep checking. Is there someone whose number is smaller? Six, no. Oh, there's Neil again.
So I'm going to push you back sort of conceptually. Neil will come forward. And now, the variable that I'm using to keep track of who has the smallest number is updated to contain Neil's location. Well, let's see. Three, seven, five. OK, I know Neil was the smallest. What's the simplest thing for me to do now? I'm not going to waste my time by just bubbling Neil one spot to the left. Why don't I just put Neil where he belongs, which is of course where?
All the way at the beginning. So Neil, come with me. And what was your name again?
GRACE: Grace.
DAVID J. MALAN: Grace. OK. So Grace, unfortunately, you're kind of in the way. So how do we solve this problem? Right? If this is an array, there's only seven locations. Recall that, with Rob, we talked about declaring ages, and we only had a finite number of ages? Same idea here. We only have a finite number of ints. Grace is kind of in our way, so how do we fix?
The simplest way is like, Grace, sorry. You're going to have to go over there so we can make room. Now, if you think about this, maybe we just made the problem worse. And maybe we did, because what if Grace were in the right place? But we know she's not, because otherwise, she would have been standing forward instead of Neil at this time, right? We already checked her number out.
All right. So now, Neil's in the right place, and I can do a slight optimization. For the next minute, I'm going to ignore Neil all together, so as not to waste his time, or accidentally swap him to the wrong place. So now, how do I find the next element that's smallest? Two. That's a pretty good number, if you want to step forward and I'll remember you. Six, no good. Four, three, seven, five, no good. So let me move you to your right place. And we just got lucky this time.
Now, I'm going to ignore these two guys, and now do one more pass through this. Six, that a pretty small number. Come on forward. Oh, sorry. Grace's number is better, so step on forward. Four. Sorry, Grace. Go back again. Number three is better. Seven. Five. And now what's your name again?
JASON: Jason.
DAVID J. MALAN: Jason. So Jason is now the smallest element I've selected. Where is he going to go? So where six is. And your name is again?
GABE: Gabe.
DAVID J. MALAN: Gabe. Gabe's in the way. What's the easiest thing to do? Swap these two guys and continue. So now let's see. Who's the smallest? Four. Let me just kind of cheat. Five is going to be the smallest. I find next, if, you want to step forward, what do I have to do with these guys, with Gabe? Swap again. So now, still slightly out of order. I found Gabe to be the smallest, so I pop him out, move you guys over. And done.
So answer is the same. The end result is the same. Which of these two algorithms is better? The second one, I heard. Why?
SPEAKER 3: It's n steps [INAUDIBLE].
DAVID J. MALAN: It's n steps at most. Interesting. So is it though? So how did I find the smallest element? How many steps did I have to take the find the smallest element? I had a look all the way at the end, right? Because in that worst case, what if Neil were over here? So just finding the smallest element takes me n steps, or n minus 1. But, OK. So fix Neil. Remember that, a minute or so ago.
But how did I find the next smallest element? It's n minus 1, or n minus 2 really, from the number of steps. So OK. So I did n minus 2. All right. So that feels a little better. All right. How many steps the next time to find number three? So n minus 4. So it's decreasing, one fewer step on each iteration. So this does feel better, right? If last time it was roughly n times n, this time it's n minus 1, plus n minus 2, plus n minus 3, plus n minus 4, dot, dot, dot. But if you recall from your high school textbooks, the little cheat sheet at the back that has formulas, if you add up this series of numbers, what is the total number of steps going to be that I take here?
This is one of those, like, n minus 1, times n, divided by 2. So let me see if I can pull this up for just a moment. And again, I'm kind of rounding some numbers just to keep our life simple, but as I recall, it's something like if I do n minus 1 things, then n minus 2, then n minus 3, it's roughly something like this over 2, and if I multiply this out, that's actually n square. That's not feeling too good. n minus n over 2.
But here's the thing. In computer science, when the problems start to get interesting is when n gets really large. And when n gets really large, which of these values is going to dominate all of the others? It's kind of the n squared, right? Yes, dividing by 2 is pretty good. But if you're talking about billions of pieces of data, or trillions of pieces of data, OK, so you're twice as fast. But who really cares if that big number, if this factor is what gets bigger and bigger. And surely, it makes more of a difference than this guy. So even though you guys are right, the second algorithm, we'll call it selection sort, is, in the real world, a bit faster potentially, because I am taking fewer and fewer steps each time.
It's not really fundamentally faster. Because if we actually play this out for large values of n, at the end of the day, for big enough n, it's still going to feel pretty slow. Well, let me take one last pass at that. That's what I would call selection sort. Can you guys reset yourselves one last time? And in this last case, I'm going to propose something called insertion sort. Insertion sort being, conceptually, a bit different.
Rather than going back and forth and selecting the smallest element, I'm just going to deal with each of these guys as I encounter them, and insert them into their correct place. So I'm just going to start with Grace, and I see that she's number four. Where does number four belong? I haven't started sorting anything, so Grace gets to stay right there. And now I'm going to claim, if you could take a step to your right, this my sorted list, this is my unsorted remaining list. So now I'm going to proceed next, and what's your name again?
BRANSON: Branson.
DAVID J. MALAN: Branson. So Branson is number two. So I'm going to take you out for a moment. And now, where do you belong in this array? So to the right of Grace. So again, we're kind of making Grace do a lot of work here. Where do we put you? So we're going to slide you to the left, and insert Branson there. But now I claim that you guys are done. But notice, I'm not using extra space. It's still 2 elements here, 5 over here. Total array size is 7, so I'm not cheating, all right?
So now we have, with Gabe here, the number six, where do you belong? You got lucky again. So you get to stay right there. Just take a slight step to the right just to make clear that you're sorted. And now we have Neil again, number one, where do you go? And now is where we'll begin to see that this algorithm, though on first glance, feels pretty smart, watch what's about to happen. If you could step forward.
Where do we want to put Neil? So obviously here, so how do we get Neil there? Let's do this step-by-step. Gabe, where do you need to go? Yep, so take one big step, or two half-steps to make one step over there. Grace, where you go? Good. So another step. And finally, Branson? Another step. And now we can put Neil into place.
So now, continue this logic. Even though we are not shifting Neil over, and over, and over, to put him where he goes, in the worst case, the next number we might encounter could be the number, say, there was a number zero, then we're going to shift all of these guys. Suppose that there's a number, negative one, then we have to shift all of these guys. So we're really just kind of flipping the problem around, such that we're transferring the expense from the selection process so the insertion process, such that you guys just had to move roughly n minus something number of steps. And that number of steps is only going to increase as I select more numbers, if I have to keep shoving you guys back, and back, and back.
So the sad thing now is all of these algorithms are n squared. Let's go ahead and thanks to these guys, and visualize these a bit differently. Very well done.
[APPLAUSE]
All right. There you go. Thanks for--
BRANSON: [INAUDIBLE] keep the numbers.
DAVID J. MALAN: No, you may keep the numbers as well. All right. Nicely done. All right. So let's see if we can't now summarize more rapidly, and more visually, exactly what just happened here as follows. I'm going to go ahead and pull up Firefox. We'll link this demonstration on the course's website. Java is a bit annoying to get working in some browsers these days. So if you do play with this at home, realize you might need to use Firefox to get it working. And what I'm going to do with this demonstration is the following.
At the bottom, I have a whole bunch of menu options, including a start and a stop button. Also, as an aside, there seems to be a bug in these programs, whereby you can't actually see the start or stop button unless you hold Command or Alt plus and zoom in, which curiously shows you more buttons. So just FYI if you play with this at home. Now I'm going to click Start in just a moment, after specifying a delay of, like, 200 milliseconds here, just so we can see what happens.
So I claim that this is a visualization of the first algorithm these guys did, bubble sort, whereby we swapped people pair-wise. The key insight to this visualization is that the height of the bars represents the size of the number. So the taller the bar, the bigger the number. Shorter the bar, smaller the number. And if you notice, we're going through the first iteration of this algorithm, swapping big and small numbers, so that the small number comes first and the big number goes to the right.
And as soon as we get the end of array of many more numbers than seven, we're going to go back to the beginning. And anticipate this. On the far left, that little guy's going to swap to the side, and this process repeats. Now this visualization quickly gets boring, so let me go ahead and stop it, change the delay something much faster just to get now, a feel for this algorithm.
So even though I've sped it up, this is like upgrading my processor, buying a new computer. I haven't fundamentally changed my algorithm, but you can indeed see more clearly than with humans, that the big numbers are bubbling up to the top, and the small numbers are bubbling down to the bottom. And now this thing here sorted. And as an aside, in the squares, there's just some bookkeeping there to help you count how many comparisons, or how many swaps have actually been done.
Well, let's try one of the others we saw. Let me click on bubble sort here, and let me choose, and this whole web page is a little buggy. Let's accept the risk and run it again. There we go. So let's do selection sort. I don't know why the menu appears over there. Let's zoom in to fix that bug, change this to 50. Ah, let's actually do that much faster. Five milliseconds or so, and Start.
So this is selection sort. So again, think about what we did with the humans up here. We went through the array and selected the smallest element again, and again, and again. Now I claim that was still pretty bad. It was still n squared, give or take, but it was, in the real world, a bit faster, because I was indeed taking slightly fewer steps each time. But we're only talking what? Maybe 40 or so bars here? We're not talking 40 million. So it's not totally clear to me that was indeed a significant gain.
Let me now go back and change to our third algorithm, which was select insertion sort. And now it's really buggy because the menu really shouldn't be down there. So now we'll scroll back up here and start this algorithm. Whoop, start and stop. So this one kind of has a pretty pattern to it, whereby we're again inserting the humans, or in this case, the bars into their appropriate location. And it's already done before I turned around. But this one, too, in theory, is still n squared.
So let's see if we can't summarize these as follows. I'm going to go ahead and just to give us sort of a common way of talking about these things, let me introduce just a bit of notation here. You're about to see something called big O , because it is literally a big O. And this is a way that a computer scientist or a mathematician even uses to describe the running time of some algorithm. How many steps does it actually take?
Now I'm going to embarrass myself with my handwriting here in just a moment. But let me go ahead and say that this will be big O over here. And let me introduce one other symbol, a capital omega. Omega is going to be the opposite, essentially, of big O. Whereas big O means, in the worst case, how much time might some algorithm take, in terms of n, omega is going to be how much time might it take in the best case. And we'll see what we mean by best case in just a moment.
So let's start something simple. Let me start with a linear search. So not sorting. We'll call this linear search. And now, make a little table out of this. And now, in the case of linear search, in the worst case, how many steps is it going to take me to find a number of arbitrary choice? And there's n total doors or n total numbers. Worst case. How many steps am I going to have to take to find the number 50 in an array of n doors? And why? Because it might be all the way over onto the end. So much like Jennifer encountered, the number 50 was all the way over, so in the worst case linear search is big O of n, we'll say.
What about the best case, if you get really lucky? It's just going to take one step, or a constant number of steps. So we'll describe that as 1. So this is pretty good. Now what if we did something like binary search? So binary search, in the worst case, took how much time?
[INTERPOSING VOICES]
DAVID J. MALAN: So actually, I heard it in a couple places. So it's actually log n, give or take, because as we divide the list in half again, and again, and again, we're able to find, ultimately, the value, if it's there, but there is a catch. What's the assumption that we have to take for granted for binary search? It has to be sorted. It's not sorted, you can split the thing in half again and again, and you can go left, and you can go right, and you can go left and right, but you're not going to find the element if the list isn't sorted, because you might miss it. Because your heuristic, for going left or right is going to be flawed if it's indeed not sorted. So there's sort of a hidden cost to using something like this.
Now, let's go into our sorting algorithms not searching-- oh, actually let's go in this blank. Binary search in the best case? It's also 1 if it just happens to be in the very middle of the array, or the middle of the phone book. Now let's do bubble sort. So again, now we're entering the sorts, not the searches.
In the worst case, how many steps did we claim bubble sort's going to take? n squared. So I'm going to draw that. Ooh, my handwriting looks even worse when it's projected that big. All right. So that's n squared. And in the best case of bubble sort, how many steps is it going to take? 1, I heard.
SPEAKER 1: n.
DAVID J. MALAN: n, I heard.
SPEAKER 1: 2.
DAVID J. MALAN: 2, I heard. Do I hear 3? All right. So I've heard 1, n, 2, but let's pick apart at least the first of those suggestions, 1. It's not a bad instinct, because it kind of follows a pattern here. But if it only takes 1 step, how in the world could I claim that the list is sorted, because if I'm only allowed to take 1 step, how many elements could I actually check to be sure? Well, just 1, which means there's n minus 1 elements that could be out of order, and I'm just going on faith after looking at 1 element that the thing is sorted. So 1's not correct here. So minimally, how many do I have to look at?
[INTERPOSING VOICES]
DAVID J. MALAN: n minus 1, or really, n, because I need to look at every element to make sure that it's not out of order. But again, we'll sort of wave our hands at the smaller numbers and assume that, as n gets large, they're uninteresting anyway. So that's bubble sort. And now, let's do these last two. Selection sort, and then we'll do insertion sort. And then we will blow your minds with something much better than all of these. All right.
What is the worst case running time of selection sort?
SPEAKER 4: n squared.
DAVID J. MALAN: n square, I'm hearing. But why n squared, intuitively?
SPEAKER 4: Because we just did it.
DAVID J. MALAN: Because we just did it. OK. Good answer. But intuitively, why is selection sort n squared? What did we have to do again and again? We had to keep scanning through, are you the smallest, are you the smallest, are you the smallest. And granted, we were able to take n steps, then n minus 1, then n minus 2. But if you kind of add those all up, or take it on faith that I've added them up in advance, we get roughly n squared minus some smaller numbers. So I'm going to call this n squared. But with selection sort in the best case, how many steps is it going to take me?
SPEAKER 5: [INAUDIBLE]
DAVID J. MALAN: It's unfortunately still n squared, right? Because if I'm selecting the smallest element, and we had seven people here, I only know, once I get to the very end, that I've found the smallest number, wherever he or she may have been. But how do I find the next smallest number? I have to do another pass. So in the best case, what is the input to selection sort? It's an already sort list, number one, number two, number three, number four. But I'm a computer. I can only look at one thing at a time. I can't sort of take a step back like a human and say, ooh, this looks correct.
I can only adjudicate correctness in selection sort by selecting the smallest number. But even if I find number one first, if I don't know anything else about the other numbers, which I don't, all I know that I've been handed an array or a set of doors behind which are numbers, the only way I know that one was the smallest? If I get all the way here and realize, damn, one was indeed the smallest.
But how do I then determine that two is the next smallest? By doing the same inefficiency again and again. So finally, with insertion sort, how, in the worst case, did we say it performs? It too is n squared. And how about with the best case? We'll leave that as a cliffhanger. We'll fill in that blank next time, but first let me propose that we fundamentally do better than all of these, all right?
So think for yourself what insertion sort's going to be. Well, that wasn't very dramatic, because I'm the only one that saw the change. Wow. OK. So here we have a somewhat different demonstration. If I zoom in here, you'll see that on the left we have bubble sort, in the middle we have selection sort, and on the far right, we have something we haven't looked at yet called merge sort. But consider what we've been doing here thus far today. When Jennifer first came up on stage, we went through the array of numbers again, and again, with linear search, and we got linear running time, big O of n, so to speak.
When we now consider the first week of class, when we had divide and conquer, and we had the phone book tearing, and Jennifer, and we collectively leveraged that key insight, which was to repeat yourself again and again by somehow throwing away, throwing away, throwing away, half of the problem, or generally, dividing a problem in half, and then treating the smaller piece of the problem as conceptually equivalent to the other, we somehow did fundamentally better. But with bubble sort, with selection sort, with insertion sort, we've may no such insights that Jennifer did. We pretty much just walked back and forth a whole bunch of times, and we tweaked things a little bit, swapping in this order, maybe inserting or selecting. But at the end of the day, I did a lot of awkward walking back and forth. We didn't really leverage something smart like Jennifer did like dividing and conquering.
So merge sort, by contrast, which we won't see until next week, it's going to leverage that key idea by dividing the input, and then halving, and then halving, and then halving. And on each iteration of that loop, sorting the left half, and the right half, then the left half of left half, and the right half of the left, then the left half of the right half, and the right half of the right half. And repeating again and again.
So you'll see this visually, but this is what awaits us next week. And in general, when we think a little bit harder on any such problem. We have n squared on the left, n squared in the middle, and n log n on the right. So there's your real cliffhanger. We'll see you on Monday.
[APPLAUSE]