YouTube Instagram TikTok How it works FAQ

The fastest way to turn talking videos into clean, searchable text. Free, private and no account required.

About

Built by Rishav Raj with one goal: free transcripts for everyone.

rishav@yttotranscript.com

Transcribe

YouTube to text
YouTube with timestamps
Instagram Reels
TikTok videos

Learn

How it works
FAQ
YouTube transcripts guide

More

Chrome extension
Contact
Privacy policy
Terms of service

© 2026 YTtoTranscript. Made for creators & researchers.

Not affiliated with YouTube, Instagram or TikTok. Respect creators’ copyright.

CS50x 2026 - Lecture 3 - Algorithms — Transcript · YTtoTranscript

Home/Transcripts/YouTube

YouTube Transcript

CS50x 2026 - Lecture 3 - Algorithms

CS50 · 23,955 words · 120 min read · EN-ORIG

Watch on YouTube

Share X LinkedIn WhatsApp

Below is the complete, readable transcript of CS50x 2026 - Lecture 3 - Algorithms by CS50 on YouTube. Read the full text, copy any part you need, or generate a transcript for any video with our free tool.

Heat. [music] Heat. [music]

>> [music] [music]

>> Damn.

by black. Black [music]

Why? Why? Why? Why? Why? Why? Why?

Heat.

Heat. [music]

[music]

All right, this is CS50. This is week three. And this was an artist rendition of what various sorting algorithms look and sound like. Recall from week zero that an algorithm is just step-by-step instructions for solving some problem to sort information as in the real world just means to order it from like smallest to largest or alphabetically or

some other heruristic. And it's among the algorithms that we're going to focus on today in addition to searching which of course is looking for information as we did in week zero too. Among the goals for today are to give you a sense of certain computer science building blocks. Like there's a lot of canonical

Transcribe another video

Paste any YouTube, Instagram or TikTok link to get a free transcript.

Free · No sign-up · Unlimited

Add to Chrome — transcribe in one click

algorithms out there that most anyone uh who studied computer science would know, who anyone who leads a tech interview would ask. But more importantly, the goal is to give you different mental models for and methodologies for actually solving problems by giving you a sense of how these uh real world algorithms can be translated to actual

computers that you and I can control. We thought we'd begin today uh with an actual algorithm for sort of taking attendance. We of course do this with scanners outside, but we can do it old school whereby I just use my hand or my mind and start doing 1 2 3 4 5 6 7 8 9

10 11 12 and so forth. That's going to take quite a few steps cuz I've got to point at and recite a number for everyone in the room. So I could kind of do what my like grade school teachers taught me, which is count by twos, which would seem to be faster. So like 2 4 6 8

10 12 14 16 18 20. And clearly that sounds and is actually faster. But I think with a little more intuition and a little more thought back to week zero, I dare say we could actually do much better than that. So if you won't mind, I'd like you to humor us by all standing

up in place and think of the number one if you could and join us in this here algorithm. So stand up in place and think of the number one. So at this point in the story, everyone should be thinking of the number one. Step two of this algorithm for you is going to be this.

Pair off with someone standing. Add their number to yours and remember the sum. Go. Okay. At this point in the story, everyone except maybe one lone person if we've got an odd number of people in the room is thinking of what number? >> Two. Okay. So next step, one of you in each pair should sit down.

Okay, good. Never seen some people sit down so fast. So those of you who are still standing, the algorithm still going. So the next step for those of you still standing is this. If still standing, go back to step two. Airgo repeat or loop if you could.

And notice if you've gone back to step two, that leads you to step three. That leads some of you to step four, which leads you back to step two. So this is a loop.

Keep going. If still standing, pair off with someone else still standing. Add together and then one of you sit down. So with each passing second, more and more people should be sitting down and fewer and fewer standing. Okay, almost everyone is sitting down. You're getting farther and farther away from each other. That's okay. I can help with

some of the math at the end here. All right, I see a few of you still standing, so I'll help out and I'll I'll join you together. So, I see you in the middle here. What's your number? >> 32. >> 32. Okay, go ahead and sit down and I'll pair you off with What's your number?

>> 20. Okay, you can go ahead and sit down. Uh, who's still? You're still standing. >> 27. >> 27. Okay, you can sit down. >> You guys are still adding together. Who's going to stay standing? Okay, what's your number? >> The worst part is doing like arithmetic across a crowded room, but >> 27.

>> 27 also. >> 47. >> 47. Okay, you can sit down. Is anyone still standing? Yeah, >> 15. >> Nice. 15. Okay, you can sit down. Anyone still standing? Okay, so all I've done is sort of automate the process of pairing people up at the end here. When I hit enter, we should hopefully see Oh, the numbers are

a little What's going on there? There we go. When I hit enter, we'll add together all of the numbers that were left. And if you think about the algorithm that we just executed, each of you started with the number one, and then half of you handed off your number. Then half of you

handed off your number. Then half of you handed off your number. So theoretically all of these ones with which we started should be aggregated into the final count which if this room weren't so big would just be in one person's mind and they would have declared what the total number of people in the room is. I'm

going to speed that up by hitting enter on the keyboard. And if your execution of this algorithm is correct, there should be 141 people in the room. According to our old school human though, Kelly, who did this manually, one at a time, the total number of people in the room, according to Kelly, if you want to come on up and

shout it into the microphone, is of course going to be >> I don't know, something around 160, I think. >> 160. So, not quite the same. Okay, but that's pretty good. Okay, round of applause for your your accuracy. [applause] Okay, so ideally counting one at a time would have been perfectly correct. So,

we're only off by a little bit now. Presumably, that's just because of some bugs in execution of the algorithm. Maybe some mental math didn't quite go according to plan. But theoretically, your third and final algorithm wherein you all participated should have been much faster than my algorithm or Kelly's algorithm, whether or not we were

counting one at a time or two at a time. Why? Well, think back to week zero when we did the whole phone book example, which was especially fast in its final form because we were dividing and conquering, tearing half of the problem away, half of the problem away. And even though it's hard to see in a room like

this, it stands to reason that when all of you were standing up, we took a big bite out of the first problem and half of you sat down, half of you sat down, half of you sat down, and theoretically there would have been, if you were closer in in uh space, one single person

with the final count. So let's see if we can't analyze this just a little bit by considering what we did. So here's that same algorithm here, recall is how we motivated week zero's demonstration of the phone book in either digital form as you might see in an iPhone or Android device looking for someone for instance

like John Harvard who might be at the beginning, middle or end of said phone book, but we analyze that algorithm just as we can now this one. So in my very first verbalized algorithm 1 2 3 4, you could draw that as a straight line because the relationship between the number of people in the room and the

amount of time it takes is linear. It's a straight line with each additional person in the room. It takes me one more step. So if you think to sort of high school math, there's sort of a slope of one there. And so this n number denoting number of people in the room is indeed a

straight line. And on the x-axis as in week zero, we have the size of the problem in people and the time to solve in steps or seconds or whatever your unit of measure is. If and when I started counting two at a time, 2 4 6 8 10 and so forth, that still is a

straight line because I'm taking two bytes consistently out of the problem until maybe the very end where there's just one person left, but it's still a straight line, but it's strictly faster. No matter the size of the problem, if you sort of draw a line vertically, you'll see that you hit the yellow line

well before you hit the red line because it's moving essentially twice as fast. But that third and final algorithm, even though in reality it felt like it took a while and I had to kind of bring us to the exciting conclusion by doing some of the math, that looked much more like our

third and final phone book example because if you think about it from an opposite perspective, suppose there were twice as many people in the room. Well, it would have taken you all theoretically just one more step. You know, granted, one more loop and there might be some substeps in there, if you will, but it's really just fundamentally

one more step. If the number of people in the room quadrupled, four times as many people, well, that's two more steps. Equivalently, the amount of time it takes to solve the attendance problem using that third info algorithm grows very slowly because it takes a huge number of more people in the room before

you even begin to feel the impacts of that uh growth. And so today indeed, as we talk about not only the correctness of algorithms, we're going to talk about the design of algorithms as well. Just as we have code, because the smarter you are with your design, the more efficient your algorithms ultimately are going to

be and the slower their cost is going to grow. And by cost, I mean time like here, maybe it's money, maybe it's the amount of storage space that you need, any limited resources, something that we can ultimately measure. And we're not going to do it very precisely. Indeed, we're going to use some broad strokes

and some standard mechanisms for describing ultimately the running time, the amount of time it takes for an algorithm or in turn code to actually run. So, how can we do this? Well, last week recall we set the stage uh for talking about something called arrays, which were the simplest of data structures inside of a computer where

you just take the memory in your computer and you break it up into chunks and you can store a bunch of integers, a bunch of strings, whatever, back to back to back to back. And that's the key characteristic for an array. It is a chunk of memory wherein all of the values therein are back to back to back.

So right next to each other in memory. So we drew this fairly abstractly by drawing a grid like this. And I said, well maybe this is by zero and this is by 1 billion. Whatever the total number amount of memory is that you have. We zoomed in and looked at a little something like this, a canvas of memory.

We talked about what and where you can put things. But today, let's just assume that we want 1 2 3 4 5 6 seven chunks of memory for the moment. And inside of them, we might put something like these numbers here. Well, the interesting thing about computers is that even though if I were to ask you all, find

the number 50 in this array. I mean, our eyes quickly see where it is because we sort of have this bird's eye view of the whole screen and it's obvious where 50 is. But the catch with computers and with code that we write is that really these arrays, these chunks of memory are

equivalent to a whole bunch of closed doors. And the computer can't just have this bird's eye view of everything. If the computer wants to see what value is at a certain location, it has to do the metaphorical equivalent of going to that location, opening the door, and looking, then closing it, and moving on to the

next. That is to say, a computer can only look at or access one value at a time. Now that's in the simplest form. You can build fancier computers that theoretically can do more than that. But all the code we write generally is going to assume that model. You can't just see everything at once. You have to go to

each location in these here lockers, if you will. Starting today too when we talk about the locations in memory. We're going to use our old uh zero indexing uh vernacular. That is to say, we start counting from zero instead of one. So this will be locker zero, locker one, locker two, dot dot dot all the way

up to locker six. So just ingrain in your mind that if you hear something like location six, that's actually implying that there's at least seven total locations because we started counting at zero. So that's intentional. Um we don't have in the real world yellow lockers. So we're going to make this metaphor red instead. We do have

these lockers here. And suppose that within these seven lockers physically on stage, we've put a whole bunch of money, uh monopoly money, if you will. But the goal initially here is going to be to search for some specific denomination of interest and use these physical lockers as a metaphor for what your computer's

going to do and what your code ultimately is going to do. If we're searching for the solution to a problem like this, the input to the problem at hand is seven lockers, all of whose doors are metaphorically closed. The output of which we want to be a bull, true or false answer, yes or no, that

number is there or no, it is not. So, inside of this black box today is going to be the first of our algorithm, step-by-step instructions for solving some problem where the problem here is to find among all of these dollar bills, specifically the $50 bill. If we could get two volunteers to come on up, who

are ideally really good at Monopoly? Okay, how about over here in front? And uh how about let me look a little farther in back. Okay, over here there and back. Come on down. All right. As these uh volunteers kindly come down to the stage, we're going to ask them in turn to search for specifically the $50

bill that we've hidden in advance. And if uh my colleague Kelly could come on up too because we're going to do this twice. Once searching uh in one with one algorithm and a second time with another. Uh let me go ahead and say hello if you'd like to introduce yourselves to the group.

>> Hey, I'm Jose Garcia. >> Hi, I'm Caitlyn Cow. >> All right, Jose and Caitlyn. Nice to meet you both. come on over and let me go ahead and propose that Jose um the first algorithm that I'd like you to do is to find the number 50 and let's keep it simple. Just start from the left and

work your way to the right. And with each time you open the door, stand over to the side so people can see what's inside and just hold the dollar amount up for the world to see. All right, the floor is yours. Find us the $50 bill. 20. >> Shut it. >> No, that's good. That's good acting,

too. Thank you. No, you can shut it just like the computer. All right. No. Very clear. Thank you. Still no. $10 bill. Next locker. $5 bill. Not going well. Uh $100 bill, but not the one we want. This one. Ah, $1 bill. Still no 50. Of course, you've been sort of set up to

fail, but here, amazing. A round of applause. Jose found the $50 bill. [applause] All right. So, let me ask you, Jose, you found the $50 bill. Um, it clearly took you a long time. Just describe in your own words, what was your algorithm, even though I nudged you along? >> Yeah. So, my algorithm was basically

walk up to the first door available, open it, check if the dollar bill was the dollar bill that I was looking for, and then put it back, and then go to the next one. >> Okay. So, it's very reasonable because if the $50 bill were there, Jose was absolutely going to find it eventually,

if slowly. In the meantime, Kelly's going to kindly reshuffle the numbers behind these doors here. And even though Jose took a long time here, I mean, what if Jose like wouldn't have been smart to start from the other end instead, do you think? >> Um, not necessarily because we don't know if the 50 is going to be at that

end. >> Exactly. So, he could have gotten lucky if he sort of flaunted my advice and didn't start on the left, but instead started on the right. Boom. he would have solved this in one step. But in general, that's not really going to work out. Maybe half the time it will. You'll get lucky, half the time it won't. But

that's not really a fundamental change in the algorithm whether you go left to right, right to left. To Jose's point, if you don't know anything priori about the numbers, the best you can probably do is just go through linearly left to right, or right to left, so long as you're consistent. Now, could you have

jumped around randomly? >> Uh, I guess I could have, but if again, if they weren't in any like specified order, I don't think it would have helped either. Yeah. So, and additionally, if he just jumped around to random order, they might get lucky and it might be in the very first one. Might have taken fewer steps ultimately,

but presumably you're going to have to then keep track of like which locker doors have you opened. So, that's going to take some memory or space. Not a big deal with seven lockers, but if it's 70 lockers, 700 lockers, even random probably isn't going to be the best job. So, let me go ahead and take the mic

away and hand it over to Caitlyn. You can stay on the stage with us. Caitlyn, what I'd like you to do is approach this a little more intelligently by dividing and conquering the problem, but we're going to give you an advantage over Jose. Kelly has kindly sorted the numbers from smallest to largest from

left to right. >> So, accordingly, what's your strategy going to be? >> Start in the middle. >> Okay, please. And go ahead as before and reveal to the audience what you found. Not the 50, the 20. But what do you know, Caitlyn, at this point? >> It'll be in on the left. Left. Correct.

So the 20 is going to be to the left. So where might you go next with this three locker problem? Let me propose that you maybe go to the middle of the three. >> There we go. The middle of the middle. Like that would have been good. But let's >> Oh no. >> Oh no. It's a 100 instead. You failed.

But what do you now know? >> It's in the middle. >> That I should have just let you. But now we have a big round of applause for Kaylin for having found the 50 as well. [applause] Okay. So, the one catch with this particular demo is that because they know presumably what monopoly money

denominations are because we just did this exercise and we had the whole cheat sheet on the board, you probably had some intuition as to like where the 50 was going to be, even though I was trying to get you to play along. But in the general case, if you don't know what the numbers are and that they're the

specific denominations, but you do know that they're going from smallest to largest, going to the middle, then the middle of the middle, then the middle of the middle again and again would have the effect of starting with a big problem and having it, having it, having it, just like the phone book as well.

So, thanks to you both. We have these wonderful parting gifts that we found in Harvard Square. Uh, if you like Monopoly, you'll love the Cambridge edition filled with Harvard Square name spots. So, thank you to you both. And a round of applause for our volunteers here. [applause] All right, so let's see if we can't

formalize a little bit these two algorithms known as linear search in so far as Jose was searching essentially along a line left to right and binary search by implying two because we were having that problem in two again and again and again. So for instance with linear search from left to right or

equivalently right to left we could document our pseudo code as follows. For each door from left to right if the 50 is behind the door well then we're done. Just return true. That's the boolean value which was the goal of this exercise to say yes here is the 50. Otherwise at the very bottom of this

pseudo code we could just say return false. Because if you get all the way through the lockers and you have never once declared true by finding the 50, you might as well default at the very end to saying false. I did not find it. But notice here, just like in week zero when we talked about pseudo code for

searching the phone book, my indentation of all things is actually very intentional. This version of this code would be wrong if I instead used our old friend if else and made this conditional decision. Why is this code now in red wrong in terms of correctness? Yeah, if it's not behind the first door, it will

return false. >> Exactly. Because if the number 50 is not behind the first door, the else is telling you right then and there, return false. But as we've seen in CC code, whenever you return a value, like that's it for the function. It is done doing its work. And so if you return false

right away, not having looked at the other six lockers, you may very well get the answer wrong. So the first version of the code where there wasn't an else but rather this implicit line of code at the very or this explicit line of code at the very end that just says if you

reach this line of code return false that addresses that problem and to be clear even though it's right after an indented return true when you return a value as in C that's it like execution stops at that point at least for the function or in this case the pseudo code in question. All right, so here's a more

computer sciency way of describing the same algorithm. And even though it starts to look a little more arcane, the reality is when you start using variables and sort of standard notation, you can actually express yourself much more clearly and precisely even though it might take a little bit of practice to get used to. Here is how a computer

scientist would express that exact same idea. Instead of saying for each door from left to right, we might throw some numbers on the table. So for i a variable apparently from the value zero on up through the value n minus one is what this shorthand notation means if 50 is behind doors bracket i so to speak.

So now I'm sort of treating the notion of doors as an array using our notation from last week. If 50 is behind doors bracket I return true. Otherwise if you get through the entirety of that array of doors you can still return false. Now notice here n minus one seems a little weird because aren't there n doors? Why

do I want to go from 0 to n minus one instead of 0 to n? Yeah, >> because zero is the first locker. >> Exactly. If you start counting at zero and you have n elements, the last one is going to be addressed as n minus one, not n because if it were n, then you

actually have n + one elements, which is not what we're talking about. So again, just a standard notation and it's a little turser this way. It's a little more succinct and frankly it's a little more adaptable to code. And so what you're going to find is that as our problem sets and programming challenges

that we assign sort of get a little more involved, it's often helpful to write out pseudo code like this using an amalgam of English and C and eventually Python code because then it's way easier after to just translate your pseudo code into actual code if you're operating at this level of detail. All right. So, in

the second algorithm, where Caitlyn kindly searched for 50 again, but Kelly gave her the advantage of sorting the numbers in advance. Now, she doesn't have to just resort to brute force, so to speak, trying all possible doors from left to right. She can be a little more intelligent about it and pick and choose

the locker she opens. And so, with binary search, as we call that, we could implement the same pseudo code. We could implement pseudo code for it as follows. We might say if 50 is behind the middle door, then go ahead and return true. Else if it's not behind the middle door, but 50 is less than that number behind

the middle door, we want to go and search the left half. So that didn't happen in Caitlyn's sense because we ended up going right. So that's just another branch here. Else 50 is greater than what was at the middle door. We want to search the right half. But there's going to be one other condition

here that we should probably consider, which is what is it here? Is it to the left? Or is it to the right? But there's another a corner case that we'd better keep track of. What else could happen? >> If it's not in the array or really like we're out of doors, so we can implement

this in a different way. I left myself some space at the top because I shouldn't do any of this if there are no doors to search for. So, I should have this sort of sanity check whereby if there's no doors left or no doors to begin with, let's just immediately return false. And why is that? Well,

notice that when I say search left half and search right half, this is implicitly telling me just do this again. Just do this again, but with fewer and fewer doors. And this is a technique for solving problems and implementing algorithms that we're going to end today's discussion on. Because what seems very colloquial and very

straightforward, okay, search the left half, search the right half, is actually a very powerful programming technique that's going to enable us to write more elegant code, sometimes less code to solve problems such as this. And more on that in just a little bit. But how can we now formalize this using some of our

array notation? Well, it looks a little more complicated, but it isn't really. Instead of asking questions in English alone, I might say if 50 is behind doors bracket middle, this pseudo code presupposes that I did some math and figured out what the numeric address, the numeric index is of the middle element. And how can I do that? Well, if

I've got seven doors and I divide by two, what's that? 7ide by two, three and a half. Three and a half makes no sense if I'm using integers to address this. So maybe we just round down. So three. So that would be locker number 01 2 3 which indeed if you look at the seven lockers is in fact the

middle. So this is to say using some relatively simple arithmetic I can figure out what the address is the index is of the middle door if I know how many there are and I divide by two and round down. Meanwhile, if I don't find 50 behind the middle door, let's ask the question. If 50 is less than the value

at the middle door, then let's search not the left half per se in the general sense. More specifically, search doors bracket zero through doors bracket middle minus one. Otherwise, if 50 is greater than the value at the middle door, go ahead and search doors bracket middle + one through doors bracket n minus one. Now let's consider these in

turn. So searching the left half as we described this earlier seems to line up with this idea like s start searching from doors bracket zero the very first one. But why are we searching doors bracket middle minus one instead of doors bracket middle. Yeah. >> Yeah. Exactly. We already checked the middle door by asking this previous

question. And so you're just wasting everyone's time if you divide the half and still consider that door as checkable again. And same thing here. We check middle plus one through the end of the lockers array because we already checked the middle one. So same reason even though it just kind of complicates the look of the math, but it's really

just using variables and arithmetic to describe the locations of these same lockers. But let's consider now what we mean by running time. The amount of time it takes for an algorithm to run. and consider which and why one of these algorithms is better than the other. So in general when talking about running

time we can actually use pictures like this. This is not going to be some like very low-level mathematical analysis where we count up lots of values. It's going to be broad strokes so that we can communicate to colleagues uh to other humans generally whether an algorithm is better than another and how you might

compare the two. So here for instance is a pictorial analysis of two different algorithms. the phone book from week zero and then the attendance taking from today itself. And let's generally, as we've done before, sort of label these things. So the very first algorithm took n steps in the very worst case if I had

to search the whole phone book or if I had to count everyone in the room. So the first algorithm took indeed n steps. The second algorithm took half as many plus one maybe, but we'll keep it simple. So we'll call that n /2. And the third and final algorithm both in week zero with the phone book and today with

attendance is technically log base 2 of n. And if you're a little rusty in your logarithms, that's fine. Just take on faith that log base 2 alludes to taking a problem of size n and dividing it in half and half and half as many times as you can until you're left with one

person standing or one page in the phone book. That's how many times you can divide in half a problem of size n. Well, it turns out that we're getting a little more detailed than most computer scientists t care to get uh when describing the efficiency of algorithms. So in fact we're going to start to use

some note comment notation instead of worrying precisely mathematically about how many steps today's and the futures algorithms take we're going to talk in broader strokes about how many steps they are on the order of and we're going to use what's called big O notation which literally is like a big O and then

some parenthesis and you pronounce it big O of such and such. So the first algorithm seems to be in big O of N which means uh it's on the order of N steps give or take some. this algorithm here, you might be inclined to do something similar. Ah, it's on the order of n / two steps and ah, this one's on

the order of log base 2 of n steps. But it turns out what we really care about with algorithms is how the time grows as the problem itself grows in size. So the bigger n gets, the more concerned we are over how efficient our algorithm is. if only because today's computers are so

darn fast. Whether you're crunching a thousand numbers or 2,000 numbers, like it's going to take like a split second no matter what. But if you're crunching a thousand numbers versus a million numbers versus a billion numbers, like that's where things start to actually be noticeable by us humans and we really start to care about these values. So in

general, when using big O notation like this, you ignore lower order terms or equivalently, you only worry about the dominant term in whatever mathematical expression is in question. So big O of N remains big O of N. Big O of N over two. Eh, it's the same thing really as like big O over N. Like it's not really, but

they're both linear in nature. One grows at this rate. One grows at this rate instead, but it's for all intents and purposes the same. They're both growing at a constant rate. This one too, ah, it's on the order of log of n where the base is who cares. In short, what does this really mean? And well, imagine in

your mind's eye that we were about to zoom out on this graph such that instead of going from zero to like a million, maybe now the x-axis is 0 to a billion. And same thing for the y-axis, 0 to a million. Let's zoom out. So you're seeing zero to a billion. Well, in your

mind's eye, you might imagine that as you zoom out, essentially things just get more and more compressed visually because you're zooming out and out and out, but these things still look like straight lines. This thing still looks like curved lines, which is to say as n gets large, clearly this green algorithm, whatever it is, is more

appealing, it would seem, than either of these two algorithms. And if we keep zooming out, like at some point, the ink is going to be so close together that they all for are for all intents and purposes pretty much the same algorithm. So this is to say computer scientists don't care about lower order terms like

divide by two or base 2 or anything like that. We look at the most dominant term that really matters as n gets bigger and bigger. So that then is bigo notation and it's something we'll start to use pretty much recurringly anytime we analyze or speak to how good or how bad some algorithm is. So here's a little

cheat sheet of common running times. So for instance here's our friend big O of N which means uh the algorithm takes on the order of n steps. Uh here is one that takes on the order of log n steps. Here are some others we haven't seen yet. Some algorithms take n times log n

steps. Some algorithms take n squared steps. And some algorithms just take one step maybe or maybe two steps or four steps or 10 but a constant number of steps. So let me ask of the algorithms we've looked at thus far for instance linear search being the very first today what is the running time of linear

search in big O notation that is to say if there's n people if there's n lockers on the stage how many steps might it take us to find a number among those n lockers big O of yeah big O of N in fact is exactly where I would put linear your search. Why? Well,

if you're using linear search in the very worst case, for instance, the number you're looking for, as with Jose, might be all the way at the end. So, you might get lucky. It might not be at the very end, but generally, it's useful to use this big O notation in the context of worst case scenarios because that

really gives you a sense of how badly this algorithm could perform if you just get really unlucky with your data set. So e even though big O really just refers to an upper bound like how many steps might it take it's generally useful to think about it in the context of like the worst case scenario like ah

the number I care about is actually way over here but what about binary search even in the worst case so long as the data is sorted how many steps might binary search take by contrast >> big O of login so binary search we're going to put here which is to say that in general and especially as n gets

large binary search is much faster it takes much less time. Why? Because assuming the numbers are sorted, you will be dividing in half and half and half just like with the phone book in week zero that problem and you will get to your solution much faster. Why should you not use binary search though on an

unsorted array of lockers like a random set of numbers? Yeah, >> you can just get rid of the value because you don't know like what the inequality is going to be. >> Exactly. You're making these decisions based on inequalities, less than or greater than, but based on like no rhyme or reason. You're going left, going

right, but there's no reason to believe that smaller numbers are this way and bigger numbers are that way. So, you're just making incorrect decision after incorrect decision. So, you're probably going to miss the number altogether. So, binary search on an unsorted array is just incorrect. Incorrect usage of the algorithm. But like Kelly did, if you

sort the data in advance or you're handed sorted data, well, then you can in fact apply binary search perfectly and much more efficiently. >> I have a question. Is there ever a case where linear search is more efficient just because the process of sorting the data yourself? >> Absolutely. Is linear search sometimes

more efficient if it's going to take you more time to sort the data and then use binary search? Absolutely. And that's going to be one of the design decisions that underlies any implementation of an algorithm because if it's going to take you some crazy long time not to sort like seven numbers but 70 700 7,000 7

million but you only need to search the data once then what the heck are you doing? Like why are you wasting time sorting the data if you only care about getting an answer once? You might as well just use linear search or heck do it even randomly and hope you get lucky if you don't care about reproducing the

same result. Now in general that's not how much of the world works. For instance, Google's working really hard to make faster and faster algorithms because we are not searching Google once and then never again doing it. we're doing it again and again and again. So they can amvertise, so to speak, the cost of sorting data over lots and lots

of searches, but sometimes it's going to be the opposite. And I think back to graduate school where I was often writing code to analyze large sets of data. And I could have done it the right way, sort of the CS50 way by fine-tuning my algorithm and thinking really hard about my code. But honestly, sometimes

it was easier to just write really bad but correct code, go to sleep for 7 hours, and then my computer would have the answer by morning. The downside, as admittedly happened more than once, is if you have a bug in your code and you go to sleep and then seven hours later you find out that there was a bug,

you've just wasted the entire evening. So there too, a trade-off sometimes when making those resource decisions. But that's entirely what today is about making informed decisions and sometimes maybe it's smarter and wiser to make the more expensive decision, but not unknowingly, at least knowingly. All right, so there might we have our first

two algorithms, but let's consider another way of describing the efficiency of an algorithm. Big O is an upper bound. Sort of how bad can it get in these uh cases where maybe the data is really uh not working to our advantage. Omega, a capital omega symbol here is used for lower bounds. So maybe how

lucky might we get in the best case, if you will. How few steps might an algorithm take? Well, in this case here, here's just a cheat sheet of common runtimes, even though there's an infinite number of others, but we'll generally focus on uh um u functions like these. Let's consider those same algorithms. So with linear search from

left to right, how few steps might that algorithm take? For instance, in like the best case scenario. Yeah. Is this hand about to go up? >> Yeah. So one step. Why? Because maybe Jose could have gotten lucky and opened this door and voila, that was the 50. It didn't play out that way, but it could

have. In the general case, the number you're looking for could very well be at the beginning. So we're going to put linear search at omega of one. So one step and maybe it's technically a few more than that, but it's a fixed number of steps that has nothing to do with the number of lockers. Case in point, if I

gave you not seven but 70 lockers, he could still get lucky and still take just one step. So omega is our lower bound. Big O is our upper bound. Ah, spoiler. What is binary search's lower bound? Well, apparently it's also omega of one, but why? That is in fact correct. Yeah, >> you could just get lucky again.

>> Same reason you could get lucky in the best case and it's just smack dab in the middle of all of the data. So the fewest number of steps binary search might take is also actually one. So this is why we talk about upper bound and lower bound because you get kind of a r a sense of

the range of performance. Sometimes it's going to be super fast which is great but something tells me in the general case we're not going to get lucky every time we use an algorithm. So it's probably going to be closer to those upper bounds the big O. Now, as an aside, there's a third and final uh

symbol that we use in computer science to describe algorithms. That of a capital theta. Capital theta is jargon you can use when big O and omega happen to be the same. And we'll see that today. Not always, but here's a similar cheat sheet. None of the algorithms thus far can be described in this way with

theta notation because they are not all the same with their big O and omega. They differed in both of our analyses. But we'll see at least one example of one where it's like okay we can describe this in theta and that's like saying twice as much information with your words to another computer scientist

rather than giving them both the upper and the lower bounds. The fancy way of describing all of what we're talking about here big O omega and theta is asmmptoic notation and asmmptoic notation refer or asmmptoic uh lee refers to a value getting bigger and bigger and bigger and bigger but not necessarily ever hitting some boundary

as n gets very large in short is what we mean when we deploy this here asmmptoic notation. All right. So, with the first of these things like linear search, let's actually kind of make this a bit more real. Let me actually go over to in just a moment uh my other screen here.

Okay. In VS Code, let me go ahead and create a program called search C. And in search C, let's go ahead and implement a fairly simple version of linear search initially. So, let me go ahead and include, for instance, CS50.h. Let me go ahead and include standard io.h. Then, let me go ahead and do in main void. So,

we're not going to bother with any command line arguments for now. And then let me go ahead and just give myself an array of numbers to play with. And we did this briefly last week in answer to a question, but I'm going to do it now concretely rather than use something uh ma more manual to get all of these

numbers into the array. I'm going to say give me an array called numbers. And the numbers I want to put in this array initially are going to be the exact same denominations we've been playing with. 20 500 10 5 100 1 and 50. Again, this is notation that I alluded to in answer to

a question last week whereby if you want to statically initialize an array, that is give it all of your values up front without having the human type them all in manually, you can use curly braces like this. And the compiler is pretty smart. You don't have to bother telling the compiler how many numbers you want,

1 2 3 4 5 6 7 because it can obviously just count how many numbers are in the curly braces, but you could explicitly say seven there so long as your counting is in fact correct. So on line six, this gives me an array of seven numbers initialized to precisely that list of

numbers from left to right. All right, let's ask the human now what number they want to search for just as I did our two volunteers and say int n equals get int. Then let's just ask the user for the number that they want to search for. Then let's implement linear search. And if I want to implement linear search in

terms of the programming constructs we've seen thus far like what type what uh keyword in C should I use? What programming technique? Yeah. Yeah. So, maybe a for loop or a while loop, but for loop is kind of uh my go-to lately. So, let's do for int i equals 0 because we'll start counting from the left. I is

less than seven, which isn't great to hardcode, but I'm not going to use the seven again. So, I think it's okay in one place for this demo. Then, I ++. Then inside of this array, let's go ahead and ask a question just like Jose was by opening each of the doors by saying if numbers bracket i equals

equals the number we asked about n, well then let's go ahead and print out some informative message like found back slashn and then for good measure like last week let's return zero to signify success. It's sort of equivalent to returning true but in main recall you have to return an int. That's why we

revealed at the end of week two the return type of main is an int because that is what gives the computer its so-called exit status which is zero if all is well or anything other than zero if something went wrong but I think finding the number counts as all is well. But if we get through that whole

loop and we still haven't printed found or return zero, I think we can go ahead and safely say not found back slashn and then let's just return one as our exit status to indicate that we didn't find the actual number. So in short, I think this is linear search. Let me open up my

terminal window again. Let me make search enter. Let me dot slash search enter. And I'll search for as I asked Jose the number 50. And we indeed found it at the end. Let me go ahead and rerun dot slash search. And let's search for the other number at the beginning 20. That then works. And just to get crazy,

let's search for a number we know not to be there like a thousand. And that in fact is not found. So I think we have an implementation then of linear search. But let me pause here and ask if there's any questions with this here code and the translation of algorithm to See yeah in the back

why I did not specify the length of the array. So it is not necessary when declaring an array and setting it equal to some known values in advance to specify in the square brackets how many you have because like the compiler is not an idiot. It can literally count the numbers inside of the curly braces and

just infer that value. You could put it there, but arguably you're opening up the possibility that you're going to miscount and you're going to put seven here, but eight numbers over there or six numbers there. So, it's best not to attempt fate and just let the compiler do its thing instead. A good question.

Other questions on this code so far? All right. If none, let's go ahead and maybe convert this linear search to one that's maybe a little more interesting that involves like searching for strings of text. After all, we started the class in week zero by searching for names in a phone book like John Harvard. Let's see

if we can't adapt our code for searching for strings instead of integers. So, in my code here, let's go ahead and delete everything inside of main just to give myself a clean canvas. Let me go ahead and give me another array. This one called, let's just call it strings because that's the goal of this

exercise. And set them equal to some familiar pieces from the game of Monopoly if you might have played. So, there's like a battleship piece in there. There's a boot in there. There's a cannon in there, an iron, a thimble, and a top hat, though it does vary nowadays based on the addition that you

have. So, kind of a long array, but I have 1 2 3 4 5 six total values in this array of strings. Now, let's ask the user for a string. We'll call it s for short, and say with get string, what string are you looking for among those six? Then I think we can do an a for

loop again for int i= 0 i less than 6 i ++ and then inside of this loop let's do the same thing. If uh let's say uh strings bracket i equals equals the string s that the human typed in. I think we can go ahead and say print found back slashn and then as before

return zero to signify success and if we don't after that whole for loop let's print at print f not found back slashn down here and return one to signify error. So it's really the same thing at the moment except that I'm actually using strings instead of integers. All right, let me go ahead and open up my

terminal window again and clear it. Let me go ahead and recompile this code. Make search.c seems to compile. Okay, let me do dot slash search and let's go ahead and search for the first one. How about battleship enter? Huh, not found. All right. Well, let's maybe I typo maybe. Let me search for

something easier to spell. Boot. Not found. That's weird. Both of those are at the very start of the array. Let's do dot slash search again and search for top hat. Enter. Not found. What is going on? Well, this isn't actually that obvious as to what I'm doing wrong. But it turns out that when we actually

compare strings instead of integers in C, we're actually going to have to use this other library, at least today, that we saw briefly last week. Last week, we introduced it because of a function called sterling, which gives us the length of a string. Turns out that string.h also comes per its documentation with another useful

function called stir comp for string compare. And its purpose in life is to actually compare two strings left and right to make sure they are in fact the same. So for today's purposes, suffice it to say, you cannot use equals equals apparently to compare two strings. Intuitively, why is that? Well, for a

computer, it's super easy to compare two integers because they're either there or they're not in memory. But with a string, it's not just a character and another character. It's like seven, a few characters over here and a few characters over here. Maybe it's a few, maybe it's more. You have to compare each and every character in a string to

make sure they're in fact the same. So stir compare does exactly that. Probably in the implementation of stir comp from like years ago, someone wrote a while loop or a for loop that looks at each string left to right and compares each and every one of the characters therein and then gives us back an answer. So how

do we go about using this? Well, to use stir compare, what I can actually do in VS code here is go and change my code as follows. Instead of using equals equals, I'm going to actually use this function per its documentation. I'm going to call stir compare. Then I'm going to pass in

one of the strings which is in strings bracket I. Then I'm going to pass in the second string which is S. However, having read the documentation and this is a little non-obvious. It turns out that stir comp will return zero if the strings are equal. Otherwise, it's going to return a positive number or a

negative number. So what I care about for now is does the return value of stir comp when given those two strings give me back zero. If so they are equal and I'm going to say quote unquote found. So let's go ahead and open the terminal again. Let me go ahead and clear it and

do make search to recompile my code. And huh I've done something wrong. Let's see. Let me scroll up to the very first line. In line 11, error call to undeclared library function stir comp with type int and something something which gets more complicated after that. Why is line 11 not working despite what

I just preached? Yeah. >> Yeah, I just did something stupid. I didn't include the string.h header library. So all clang, our compiler is doing when invoked by make is it's encountering literally the word stir comp and not knowing what it is because we haven't taught it what it is by simply saying include string.h at the

top. Okay, let me reopen my terminal window. Clear that message away. Do make search again. Now it's compiling. Dot / search enter. Now I'm going to go ahead and search as I did before for battleship. Ah, now it's finding it. Let me run dot / search again. Search for boot. Ah, okay, that's found. Let me go

ahead and search for top hat. That too is in there. Let me go ahead and search for something that's not there like the number 50. Not in fact found. So I think we've actually fixed that there problem. But if we go back to this code for a moment, it's indeed the case per the

documentation that equals equals0 is what I want to do. Why in the world would stir comp be designed to return a positive or a negative number too? It's not returning true or false. It's returning one of three possible values. Zero, negative, or positive. Why might it be useful? Yeah. >> And you could kind of like compare which

of the strings is like greater. >> Yeah. Super clever. So if you're passing in two strings, it's great to know if they're equal. But wouldn't it be nice if this same function could also help us sort these strings ultimately and tell me which one comes first alphabetically. And technically it's not going to be

alphabetically. It's going to be a cute phrase asetically because it's actually going to look at the asky values of the characters and do some quick arithmetic and tell you which one comes first and which one comes later which is enough as we'll eventually see for actually sorting these strings as well. So in

short the documentation will tell me that I should check not only for zero if I care about equality but if I care about inequality that is checking if one comes first or last I should check whether something is less than zero or greater than. But for this demonstration implementing linear search, I don't care

about comparing them uh for inequality. All I care about is that they are in fact the same or not in this case. All right. Well, let's go ahead and do one other example of sort of linear search, but let's make the problem more like that actually in week zero of searching a phone book. So, let me go back to VS

Code here. Close search C and let's make an actual phone book. So, I'm going to say code of phonebook C. And then inside of phonebook C, let's use our same header file. So include cs50.h, include standard io.h, and let's include an advanced string.h. Then let's before, as before, do int main void. No command line arguments

today. Then inside of here, let me give myself first an array of strings. How about some names in the phone book? So I'm going to say string names equals and then three names just to make uh a demonstration. and Kelly and David and say John Harvard here. But if it's a phone book, I need more than just names.

So, let me go ahead and give myself another array. String of numbers, open bracket, close bracket equals, and now the same phone numbers we used in week zero for the three of us. Uh, + 1 617 495 1. Uh, same for both Kelly and me. So, plus 1 617 495 uh 1,000. And then as

before, if you'd like to text or call John directly, you can do so at plus1 949-4682750 and semicolon. So, one question first. I obviously declared our names to be a an array of strings because that's what text is. Why have I also declared phone numbers to be strings and not integers? Because a phone number is like literally

a number in the name of it. Yeah. Yeah. So even though we have phone numbers in the US, even though we have social security numbers and a bunch of other things that we call numbers, if you have other non-digits in those uh in those values, you have to actually use strings because if it's not an actual

integer, but it does have things like pluses or dashes or parentheses or any other form of punctuation as is common in the US and other countries for phone numbers in particular, you're going to actually want to use strings and not numbers. as well as for corner cases like if there are if you're in the habit

back home if you're not from uh say the US and you actually have to dial zero first to make like a local regional call you don't want to have a leading zero in a integer because mathematically as we know from grade school like leading zeros number zeros that come first have no mathematical meaning they're going to

disappear effectively from the computer's memory unless we store them in fact as characters in strings in this way okay with that said let's go ahead and ask the human now after having declared those two arrays for the name they want to look up the number of. So let's say string name equals get string

and let's go ahead and ask the human uh for the name for which to search. Then let's use a for loop as before for int i equals z i less than 3 which again for demonstration purposes I'm just hard coding today i ++ and then in the for loop I'm going to use our new friend

stir comp. If the return value of stir compare passing in names bracket i and the name the human typed in equals equals zero signifying that they are in fact the same. Well that means we found the location i where the person's name is. So let's go ahead and print out found. But just to be fun let's print

out whom we found. So percent s back slashn and then output there the number which is going to be in the corresponding numbers array at that same location i. We'll return zero. And at the very end of this program, let's go ahead and print out not found if we get that far and return one. All right, so a

little more complexity this time, but notice I'm comparing the names just like a normal person would in your iOS app or your Android app when looking for someone's name. But what I care about is getting back the number. So that's why two lines later, I'm printing out the number that I found at location I, not

the name because I already know the name. All right, in my terminal window, let's go ahead and make this phone book dot /phonebook. Let's go ahead and search for John whose number is hopefully indeed exactly that number. So suffice it to say, this code too does work. This is a linear search because

I'm searching left to right. These aren't actually sorted alphabetically by name or let alone number. So I think we're doing well here. But I don't necessarily love this implementation. Even if you're new to programming, what might you not like about how I've implemented a phone book in the computer's memory? Why is this maybe not the best design?

Yeah. >> Like there's a correspond >> Okay. Again, I would say so, uh, you're pointing out that we have this duality. We've got two arrays. They're the exact same length, and it just so happens that location zero's name lines up with location zero's number and location one and location two. But we're kind of on

the honor system here whereby the onus is on us to make sure we don't screw this up and we make sure we always have the same number of names and the same number of numbers and better and moreover that we make get the order exactly right. We are just trusting that when we print out the E number, so to

speak, that it lines up with the E name. So that's fine. And honestly, for three people who really cares, it's fine. But if you think about 30 people, 300, 3 million, well, we're not going to hardcode them all here. But even in some database that we'll store them in later in the course feels like just trusting

that we're not going to screw this up is asking for trouble. And indeed, a lot of programming is just that, like not trusting yourself and definitely not trusting your colleague not to mess something up, but programming a bit more defensively and trying to encapsulate related information a little more tightly together and not just assume as

on the honor system that these two independent arrays will line up. But at this point, we have no means of solving this problem unless we give ourselves just a bit new functionality and syntax. So I used this phrase earlier to kick things off. data structures. It's like how you structure your data in the

computer's memory. Arrays are the simplest of data structures. They just store data back to back to back from left to right continuously in memory. But they all have to be, as we've seen, the same kinds of values. Int int or string string string. There's no mechanism yet for storing an int and a

string together and then another int and another string together or let alone two strings, two strings, two strings that are somehow a little bit different. But it would be nice if C gave us an actual data type to store people in a phone book such that we could create an array called people inside of which is going

to be a whole bunch of persons if you will back to back to back and I want two of them. So wouldn't it be nice if I could literally use this code in C. Well decades ago when se was invented they didn't give us a person data type. All we have is int and float and char and

bool and string and so forth. Person was not among the available data types. But we can invent our own data types it turns out. So in C what we can do if we want persons to exist and every person in the world shall have a name and a phone number for now we can do this

string name string number. Now that's a decent start but it's going to be kind of a stupid implementation if I then just do name uh string name one string name two string name three string name four. We've already started down that road last week and decided arrays were a better solution. But here's an

alternative. When you want to just store related data together, I can use these two keywords and see type defrct which albeit tur just means define a new type that is a data structure. So multiple things together inside the curly braces you literally put the two things you want to relate together string name

string number and then outside the curly braces you specify the name you want to give to this brand new custom type that you have invented. Technically, stylistically, you'll see that style 50 prefers that the name actually be on the same line as the last curly brace, which looks a little weird to me, but that's

what industry tends to do, so so be it. But these several lines together tell C, invent for me a new data type called person, and assume that every person in the world has a string called name and a string called number. And now I can use this new data type in my own code to

solve this problem a little bit better. So, in fact, let me go ahead and do this as follows. I'm going to go back to VS Code here. And at the very top of my code, above main, just to make this available to not only Maine, but maybe any future functions I write, I'm going

to say type defaf strruct as we saw on the screen. Inside of my curly braces, I'm going to say string name and string number. And then I'm going to name this thing person. Now, I'm going to go about using this and I'm going to go ahead and delete my previous honor system approach

of having names and numbers in separate arrays. And I'm instead going to give myself an array of people. Uh, we could call it persons, but I'm trying to be somewhat grammatically correct. So, I'm going to say people bracket three to give myself an array called people inside of which is room for three

persons inside of which is room for a name and number each. So, how do I now initialize these values? So I'm going to hardcode them. That is type them manually. But you can imagine using get string or get or some other function to get this data from the human themselves. I'm going to say go to the people array

at location zero and access the name field. And this is syntax we haven't seen yet, but it's not that hard. You literally use a dot, a single period to say go inside of that structure and access the name field, the name attribute, so to speak. And let's set that equal to Kelly. Then let's go into

that same array location people bracket zero and set the number for the zeroth person to be +1 6174951000. Then let's go ahead and do the same thing for people bracket 1. Set that person's name to for instance mine David. Then let's do people bracket 1 number equals quote unquote same as Kelly cuz we're both in the directory.

So + 1 617495 1,000. And then lastly, people bracket 2.name equals quote unquote John for John Harvard. People bracket 2 number equals plus one uh 949 4 6 8 27 5 0 in this case. And now the rest of the code is almost the same. I'm going to now on the new line 24 still

ask the user what name they want. I'm going to still iterate from 0 to three because there's still three elements in this array even though each has two values within. And I'm going to compare now not names but people bracket i.name to go access the name of that i person and compare it to the name that the

human has typed in. And when I find that person I'm going to go into the people array at location i but print out the number instead. So all we've done here is add this dot notation which allows you to access the inside of a data structure. And all we've done is introduce up here some new C keywords

that let you invent your own data types inside of which you can put most anything you want. I have chosen a string name and a string number. All right, let me go ahead and open my terminal window and clear it from before. Let me do make phone book to make this version. So far so good. Make

phone book. Enter. I'm going to go ahead now and search for say John. And I have again found his number. So this is still correct. But even though this took more minutes in terms of the voice over and it took more lines of code, it's arguably better designed now because at people bracket zero is an actual person

and everything about them. At people bracket one is another person and everything about them and so forth. This is what we mean by encapsulate. You can think of these curly braces as sort of hugging these data types inside of the data structure together so as to keep them together in the computer's memory

as well. All right. Well, just to set the stage, uh, literally as we'll strike the lockers and put something else up, the efficiency of binary search as implemented by Caitlyn was predicated on Kelly having in advance sorted the values up front. But of course, we've only considered now the running time of searching for information using two

algorithms, and there can be many others in the real world, but those are two of the most canonical. We found that binary search was faster than linear search, but it required that we sort the data. So to your question earlier, maybe we should consider just how expensive it is in terms of time, money, space, humans

to sort data, especially a lot of data, and then decide whether or not it's worth using something like binary search or perhaps even something else. So the next problem we'll solve today ultimately is given uh generic input and output. The input to our next problem is going to be unsorted data. So like

numbers out of order, the output of which should be sorted data. So for instance, if we pass in 72541603, I want whatever black box is implementing my sorting algorithm to spit out 0 1 2 3 4 5 6 7. So that's going to be the question we answer. But first, I think it's time for some

delightful hello pandas, chocolate biscuits. Uh let's take a 10-minute break and snacks are now served. All right, we are back. And recall that the cliffhanger on which we left was that how do we go about sorting numbers? Well, here are some numbers. Eight of them, in fact, from 0 to 7, but currently unsorted. Um, we don't quite

have enough Monopoly boards for everyone, but we do have some delightful uh Super Mario Brothers Pez dispensers. If I could get eight volunteers for this final demo up here. Oh, and not a lot of hands. Okay. All right. One, two, three, four, five, six, and let's go farther back. Seven, and eight. How about All

right. Come on up. Hopefully, I counted properly. Come on over. Upon arrival at the stage, go ahead and grab your favorite illuminated number and stand in that same order at the front of the stage if you all could. Welcome to the stage. All right, grab your favorite number. Stand in that same order.

All right, good. And one, two, three, four, five, six. I definitely said one through eight. Who is the number eight then? Okay, we need an eight. Come on down. All right. Well, technically we need a four, but come on down. Yeah. All right, grab the four and let me start from this end first if you want to give a quick

hello and a little something about you. >> Uh, hi, my name is Cameron. I'm a first year and I want to study mechanical engineering. >> Welcome. >> Hi, I'm Charlotte. I'm also first year and I'm in Canada F. >> Welcome. >> Hi, I'm Ella. I'm also a first year and I'm in the

>> Hi, I'm Precious. I'm also a first year. I'm here. >> Hi, I'm Michael. I'm just an Eventbrite guest. >> Yeah. >> Hi, I'm Marie. I'm a first year and I'm in Canada. >> Welcome. >> Hi, I'm Rick. I'm a first year and I'm in whole worthy. >> Welcome. >> Nice. >> I'm Jaden. I'm a first year in Wholey

and I really like free stuff. >> Okay. Well, let's see then uh if we can't award all these Super Mario Brothers Pez dispensers. The first notice, of course, that all eight of our volunteers are completely out of order, but in an ideal world, we would have the smallest number over here. Go over there. Number zero. Wait a

minute. Seven. Let's go over here. Two. Okay. F. Okay. Make yourselves look like that. No pez. It's [laughter] okay. All right. So, 725 41603. Okay. Hey, we won't do the introductions again, but now we have a list of numbers completely out of order. And wouldn't it be nice if zero were eventually over

here? Seven were all the way over there, and everything else was sorted from smallest to largest. Well, if you all could go ahead and sort yourselves from smallest to largest. Go. All right. And Jaden, what was your algorithm for doing that? Um I I I I know that I have the least number

because I don't think there anybody has a number less than zero. So I put myself at the last bottom line. >> Okay. And I assume precious. What was your algorithm? >> I knew I had the largest number. So I just had to be at the end of the >> Okay, fair. So you guys got the easy

ones. Uh number four. How about >> I knew three was before me and five was after me. >> Nice. So number four didn't actually have to move coincidentally, but as for five and three and two and one and six, they probably had to take into account some additional information. Who's to their left, who's to their right, and it

just kind of worked, but it didn't look very algorithmic, if you will. It looked very organic and obviously correct. But I'm not sure that same approach would work well if we had not eight, but 80 or 800 or 8,000 pieces of data. So let's see if we can't formalize this a little bit. Let me take the mic and if you guys

could reset yourselves to those same original positions from seven on the left to three on the right. Let me propose a couple of algorithms, canonical ones if you will, but see if maybe we can't formalize step by step what to do. So the first one I'm going to do given all of these numbers is just

try to select the smallest number. Why? To Jaden's point earlier, I just want to put the smallest number over here. At least that's a problem I can solve. It's very well defined. It's a nice bite out of the problem. So seven. Okay, smallest so far. Two, that's that's smaller. So I'm going to remember that two is the

now smallest number I've seen. Not five, not four. One is even smaller. So, I'm going to remember one, not six, zero. That's pretty good. But I'm going to check the whole list. Maybe there's negative one or something like that. But no, three. So, I'm going to remember that zero was the smallest element I

found. Let's select Jaden and put Jaden over here. But before Precious or anyone else moves, we don't really have room for you. Like, Precious is in the way because if this is an array of eight values for integers, well, we can't just kind of make room over here because if you think back to last week, we might

have uh some garbage values there or something else is going on. We don't want to change data that doesn't belong to us. So what to do with precious? Well, maybe Precious, maybe you can go over there. So just take Jaden's spot and we'll swap these two values accordingly. Now though, Jaden is in the

right space, which is good because now I can move on to the second problem. What's the next smallest element that's presumably greater than zero? Well, at the moment, two is the next smallest element. Not five, not four. Ooh, one is the next smallest element. I'm going to remember that. Not six, not seven, not

three. Okay, so number one, if you could go to the right location, but I'm afraid we're going to have to evict number two to make room. All right, let's do this again. Zero and one are in good shape. So now I think I can ignore them as complete. Five is the current smallest.

Nope. Four now is Nope. Two now is six. No. Seven. No. Three. No. Okay, so two is the next smallest. So let's swap two and five. And now I've solved three out of the eight problems. Let's do this again. Four is at the moment the smallest. Not five, not six, not Oh, three is the now smallest. So, let's

swap three. Four and three, which unfortunately is making the four problem a little worse. Like he belongs there it would seems, but I think we can fix that later. So, now half of the list is sorted. Five is the next smallest. Six and seven. A four. Now, we got to fix the four. So, four goes back there. Now,

I messed up the five, but it will come back to that. All right. Six. Seven. Okay. Five. Let's put you where six is. And now one more mistake to fix. So, seven. Okay. Six and seven need to swap. And now I've solved eight problems in the aggregate. So it's complete. Now to be fair, my approach is clearly way

slower than your approach, but you all were working in parallel, whereas I was doing it more methodically step by step. And I dare say my algorithm is probably going to be more translatable to code. And indeed, what I just acted out is what the world would call selection sort, whereby on each iteration, each

pass in front of the humans, I was selecting the smallest element I could find. All right. What how else could I do this, though? Let's do something that's maybe a little more organic like your approach where you were actually comparing who was next to you. Go ahead and reset yourselves one final time to

this arrangement. Seven on the left, three on the right. And let me propose again to walk through the list again and again, but let me focus more narrowly on the problem right in front of me because I felt like I was taking a lot of steps back and forth, back and forth. Maybe we

can chip away at some of that wasted time. Let's compare seven and two. They're obviously out of order. So, let's just immediately swap you two if we could. All right. Now, seven and five clearly out of order. Let's swap these two. Seven and four out of order. Let's swap these two. Seven and one out of

order. Let's swap these two. Seven and six out of order. Let's swap these two. Seven and zero out of order. Swap these two. Seven and three out of order. Swap these two. So, a lot of work for Precious there. But, I've now indeed solved one of the eight problems. Moreover, I don't need to keep uh

addressing the seven problem because notice that Precious has essentially bubbled her way up to the end of the list. And indeed, that's going to be the operative term here. Another algorithm that computer scientists everywhere know is called bubble sort, whereby the goal is to get the biggest elements to just bubble their way up to the top of or the

end of the list one at a time. Now, am I done? Well, no. Clearly not. There's still stuff out of order, except for precious. Indeed, I have solved one of these eight problems. And now fine, I'll go back and I'm just going to try this same logic again. 2 and 5, good. Five

and four, nope, swap those. Five and 1, nope, swap those. Five and six are good. Six and zero, nope, swap those. Six and three, nope, swap those. And I already know that Precious is where she needs to be. So, I think I'm done with the second of eight problems. And I'll do this a

little faster now. Two and four. Four and one, swap. Four and five are good. Five and zero, swap. Five and three, swap. And now we've solved three problems. Let me reset. Two and one, swap. Two and four are good. Four and zero, swap. Four and three, swap. And now I've solved half of the problems.

Four out of eight. We're almost done. One and two are good. Two and zero, swap. Two and three are good. Okay. And now we're done with five out of the eight problems. One and zero, swap. Uh, one and two are good. Those are all good. And let me just do a final sanity

check. Everything now is sorted. So now I'm done solving all eight of those problems. So, you all were wonderful. We need the numbers back, but Kelly has some delightful Pez dispensers for you on the way out. If you want to head that way, just leave the numbers on the shelves. And a round of applause for our

eight volunteers for helping to act this out. [applause] Thank you. So, let's see if we can't formalize what these volunteers kindly just did with us. Starting with the first of those algorithms. Thank you. Namely, selection sort. Let's see if we can't slap some pseudo code on this. thinking of our humans now as more generically an array.

So we had the first person at location zero and we had the last person at location n minus one. And just for clarity so that you've kind of seen the uh symbology, this obviously is going to be location n minus2. This is location n minus3 and so forth until you sort of dot dot dot you hit the other end that

we've already written out. So that's just how we would refer to all of our eight volunteers locations or in this case 1 2 3 4 5 6 seven locations but dot dot dot in the middle conoting that this can be a much much larger array. So here's some pseudo code for the first

algorithm selection sort for i from 0 to n minus one. So from the first element to the last element find the smallest number between the numbers bracket i and numbers bracket n minus one. In other words, if you're starting I at zero, look at specifically every lighted number between location zero and location n minus one. When you have

found that smallest element, swap it with the number at location i, which starts again at zero. That's how we got I think jaden into place at the very beginning. Then I by nature of how for loops work gets updated from 0 to one. So that we do the same thing. Find the smallest number between numbers bracket

one. So the second element through the eighth element because this number is unchanged. N is the total number of values. So the end point there is not changing. Once we found the second smallest person, we swap them with location I aka one. And that's how we got the number one into position and

then the number two and then the number three and number four. So this then was selection sort in pseudo code form. And that allowed us to actually go through this list again and again and again in order to find the next smallest element. So what was happening a little more methodically if it helps just to map

that symbology of the bracket notation and the eyes. If this is where we started with location I and we did everything between location N minus one. Essentially I traversed this whole list from left to right literally walking in front of our volunteers looking at each element and the first element I saw was

seven. At the moment that was the smallest element I had found and who knows in a different list maybe seven would be the smallest element. So, I kind of stored it in a variable in my mind, but I checked then two and remember no, no, no, two is clearly less than. Now, I'm going to remember two.

Okay, now I'm going to remember one when I find it. Then I'm going to remember zero when I find it. And then what I did once I found Jade in it with the value of zero uh light it up, I moved location, that location to here, and then evicted precious recall and moved

precious over to that location that we had freed up. Why? Why all this sort of back and forth? Well, you have to assume with an array that you're not entitled to the memory over here. You're not entitled to the memory over here. If you've already decided that you have seven lockers or eight people, you have

to commit to the computer in advance. That's why we put the number typically in the square brackets or the compiler infers from the curly brackets how big the array actually is. All right. And suffice it to say, when I went through this again and again and again, I did the same thing over and over. Now, you

might have thought me sort of dumb for having asked the same questions again and again. Like, I was surprised to discover the number one. I was surprised to discover the number to two, even though on my very first pass, I literally looked at all eight of those numbers. But you have to think about

what memory I'm actually using. Now, I certainly could have memorized all of the numbers and where they are, but I proposed that just very simply, I was using like a single variable in my brain just to keep track of the then smallest element. And once I'm done finding that and solving that problem, I moved on to

do it again and again. But that's going to be a trade-off. And this is going to be thematic in the coming weeks whereby well, sure, you could use more memory and I could have been smarter about it and maybe that would have improved or um hurt the running time of the algorithm. There's often going to be a trade-off

between how much memory or how much time you actually use. So we'll discover that over time. So how fast or slow is selection sort? Well, consider when I had eight humans on stage, I first went through uh all n of them, but how many comparisons did I make? Really, I was doing n minus one comparisons because if

I've got n people, I've got to compare the smallest number I found against everyone else. And you compare n people left to right, n minus one times total. So, the first pass I was making I was asking n minus one questions. Is this the smallest? Is this the smallest? Is this the smallest? N minus one times.

Once I solved one problem, when we got Jaden into Jaden's right place, then I had one fewer problem, then one fewer fewer problem and so forth. So it was like n minus one steps plus n minus2 steps plus n minus3 steps plus dot dot dot one final step once I got to the

final of the eight problems. Now if you remember kind of the cheat sheet at the back of your math books, uh say growing up, you'll note that this uh series here can be more simply written as n * n minus one all divided by 2. And if you've not seen that before, just take

on faith that this is identical to this series of numbers up here. So now we can just kind of multiply this out. So that's technically n ^2 minus n all divided by 2, which is great. If we multiply that out, that's n^2 over 2 - n /2. We're getting too into the weeds.

Let's whip out our big O notation now whereby we can wave our hands at the lower order terms only care about the biggest most dominant term which mathematically in this expression if you plug in a really big value of n which is going to matter more the n squ the two the n or the two like the n squ like the

others absolutely contribute to the total value but if you plug in a really big value the dominant force is going to be this n squ because that's really going to blow up the total value so we can say that selection sort when analyzed in this way ah it's on the order of n squared steps because I'm

doing so many comparisons so many times. So if that's the case the question then is um what is indeed not just its upper bound but maybe it's lower bound as we'll eventually see. So for selection sort for now, let's stipulate that it's indeed in big O of N squ. And that's actually the worst of the algorithms

we've seen. Like that's way slower than linear search because at least linear search was big O of N. Selection sort is N squar which of course is N * N which is and will feel much much slower than that. So what if though we consider the lower bound of selection sort? All right, maybe it's bad in the worst case,

but maybe it's really good when the numbers are mostly sorted. Unfortunately, this is the same pseudo code for selection sort. We make no allowance for checking the list to make sure it's already sorted. And in fact, that's kind of a perverse case to consider for any algorithm. What if the problem's already solved? How's your

algorithm going to perform? Like if all of my volunteers, is they kind of almost did accidentally. They started lining up roughly in order. Suppose they literally had been in order from 0 to 7. Well, my stupid algorithm would still have me walking back and forth, back and forth, back and forth. Why? because the code

literally tells me do this this many times and every time I do that find the smallest element. So it's going to be sort of a stupid output because the list is not going to be any changed any any at all changed but my code is not taking into account in any way the original

order of the numbers. So no matter what this is to say that if we consider whether the lockers or the humans the omega notation for this algorithm even in the best case where the data is already sorted is crazily also n squared. Now I could certainly change the pseudo code but selection sort as

the world knows it is more of a demonstrative algorithm or sort of a quick and dirty one. Its running time is going to be in omega of n^ squ. And now we can actually deploy our theta notation because the big O notation is n^ squ and the omega notation is n^ squ and the same. We can also say that

selection sort is in theta of n^ squ which is not great because that's annoyingly slow. So maybe the solution here is don't do that let's use bubble sort instead. The second algorithm where I just compared everyone side by side again and again. Well, here's some pseudo code for bubble sort, which you can assume applies to the same kind of

array from zero on up to n minus one. Here's one way to write bubble sort. Repeat the following n times. For i, from 0 to n minus2, if the number at location i and the number at location i + 1 are out of order, swap them. And there's kind of an elegance to this

algorithm. And that like that's it. And you just assume that when you go through the list, this is how from I from 0 to n minus two, this is how I was effectively comparing elements 0 and 1, one and two, two and three, three and four, dot dot dot, uh 7, 6 and 7. But notice I didn't

say eight. There were eight total people. Why do we go from 0 to n minus2 instead of from 0 to n minus one? Uh yeah. Yeah, >> we already checked the last one. >> Not quite. So, it's not that we've already checked the last one. I'm saying with this line of code here, we never

even go to n minus one. Technically, >> if we have n= i, it's going to compare against i + >> exactly because we're doing this simple arithmetic here. We're checking current location i + 1. You can think of these as my left and right hand. Left hand is pointing at zero. Right hand's pointing

at one. I don't want to do something stupid and have my left hand point at n minus one because then my right hand arithmetically when you add one is going to point at n which does not exist. That's beyond the boundary of the array because the array goes from zero to n minus one. So just a little bit of a

safety check there to make sure we don't walk right off the end of the array. But we do this n times because recall that precious ended up being where uh seven needed to be at the very end of the list. But that didn't mean there weren't seven uh seven more problems still to

solve. Zero through six. So I did it again and I did it again. And per its name, bubble sort, the biggest element bubbled up first, then the next biggest, then the next biggest, then the next business biggest biggest, that is seven, then six, then five, then four, and we got lucky on some of them, but

eventually we finished with zero. So how do we analyze this thing? Well, we could also technically do this n minus one times as an aside. If you're thinking through that, I'm wasting some time because we get one for free. Once we get to uh solving seven problems, you get the eighth one for free because that

person is obviously where they need to go. So when we had these numbers initially and we were comparing them with bubble sort again, left hand, right hand, it's like treat this as I, this is i + one, and we just kept swapping pair-wise numbers if in fact they were out of order. So all this is saying is

what our humans were doing for us organically. So how do we actually analyze the running time of this? Last time I just kind of spitballled that it was n minus one steps plus n minus two steps. Well, you can actually look at pseudo code sometimes and if it's neatly written, you can actually infer from the

pseudo code how many steps each line is going to take. For instance, how many steps does this first line take? I mean like literally n minus one. The answer is right there because it's saying to the computer or to me acting it out, repeat the following n minus one times. All right, so that's helpful. How many

line how many steps does this inner loop induce? Well, you're going from i to n minus2. So that's actually n minus one total steps, not n. And then this question here, if numbers bracket i and numbers i are out of order, it's a single question. It's like our boolean expression. We'll call it one. I mean,

maybe you need to do a bit of more work than that, but it's a constant number of steps. Doesn't matter how big the list is. Comparing two numbers is always going to take the same amount of time. And then swapping them, oh, I don't know. It's going to take like one or two

or three steps, but constant. Doesn't matter which the numbers are. Takes the same amount of work. So let's stipulate, let me rewind, stipulate that the real things that matter are the loops. These constant number of steps, who really cares? But the loops are what are going to add up as n gets large. So this

really then is if this is the outer loop and this is the inner loop. Think about our two-dimensional Mario square from week one. We did something on the outside and then something on the inside to get our rows and columns. This is equivalent to n -1 * n -1. If we do our

little foil method, n^2 - n - n + 1 combine like terms, n^2 - 2 n + 1, who cares? This is ultimately going to be on the order of big O of n^2 only because again, if you ask yourself when I plug in a really big value for n, which of these is really

going to contribute most to the answer? It's obviously going to be n^2 again and we can ignore the lower order terms. So this doesn't seem to have made any progress. Like selection sort was on the order of big O of N was on the order of N squ. Bubble sort based on this

analysis is also on the order of N squed. Maybe we're getting lucky in the lower bound. So on the upper bound for bubble sort it's indeed N squ as was selection sort. But with this pseudo code for bubble sort unfortunately we rather unfortunately we were not doing anything clever to catch that perverse case where maybe the list was

already sorted. After all consider if the list was sorted from 0 to 7. I was still asking all the same darn questions even if I did no work. I was going to repeat that n minus one times back and forth making no swaps but making all of those comparisons. But here's an enhancement to bubble sort that we can

add that selection sort didn't really have room for. I can say after one pass of this inner loop walking from left to right if I made no swaps quit. So put another way if I traverse the list from left to right I make no swaps. I might as well just terminate the algorithm

then because there's no more work clearly to be done. All right. So based on that modification, the lower bound of bubble sorts running time would be said to be an omega then of n because I'm minimally going to need to make one pass through the list. You can't possibly claim that the list is

sorted unless you actually check it once. And if there's n elements, you're going to have to look at all n of them to make sure that it's in order. But after that, if you've done no work and made no swaps, no reason to traverse the list again and again and again. So a

bubble sort can be said to be an omega of n because indeed we can just terminate after that single pass if we've done no work. We can't say anything about theta because they're not one in the same big O and omega. But that does seem to have given us some savings. Unfortunately, it really only

saves us time when the list is already or mostly sorted. But in the average case and in the worst case, odds are they're both going to perform just as bad on the order of n square. In fact, let's take a look at a visualization that'll make this a little clearer than our own humans and voices uh might have

explained. Here is a bunch of vertical purple bars uh made by a friend of ours uh in the real world. And this is an animation that has a bunch of buttons that lets us execute certain algorithms. A small bar represents a small number. A big bar represents a big number. And the goal is to get them from small numbers

or small bars to big numbers or big bars left to right. So I'm going to go ahead and click on selection sort initially. And what you'll see from left to right is in pink the current smallest element that's been discovered, but also in pink the equivalent of my walking across the stage left to right again and again and

again trying to find the next smallest element. And you'll see clearly just like when we put Jaden at the far left, the smallest element ended up over here. But it might take some time for precious for instance or number seven to end up all the way over on the right because with each pass we're really just fixing

one problem at a time and there's n problems total which is giving us on the order of those n squared steps and now the list is getting shorter so we're at least doing some work that you don't have to keep touching the elements you already sorted which just like I was. So now selection sort is complete. Let's

visualize instead bubble sort. So let me rerandomize the array just so we're starting with a random order. Now let's click on bubble sort and you'll see the pink bars work a little differently. It conotes which two numbers are being compared at that moment in time. Just my like my left hand and right hand going

left to right. And you'll see that even though it's not quite as pretty as selection sort where I was getting at least the smallest elements all the way to the left here we're just pair fixing pairwise problems but the biggest elements like precious number seven are indeed bubbling their way up to the top

one after the other. But as you can see, and this is where n squared is sort of visual visualizable. We're touching these elements or looking at them so many times again and again. We are making so many darn comparisons. This is taking frustratingly long. And this is only what a few dozen bars or numbers.

You can imagine how long this might take with hundreds, thousands, or millions of values. I dare say we're going to have to do better than bubble sort and selection sort because we're not done even yet. just trying to give the satisfaction of getting to the end. And now we are. But neither of those

algorithms seems incredibly performant because it's still taking us quite a bit of time to actually get to that there solution. So how can we actually do better than that? Well, we can try taking a fundamentally different approach. And this is one technique that you might have encountered in math or even in the real world even if you

haven't sort of applied this name to it. Recursion is a technique in mathematics and in programming that allows you to take sort of a fundamentally different approach to a problem. And in short, a recursive function is one that's defined in terms of itself. So if you had like f ofx equals f of something on the right

hand side of a mathematical expression, that would be recursive in that the function is dependent on itself. More practically in the world of programming, a recursive function is a function that calls itself. So if you are writing some function in C and in that function you call yourself you actually have a line

of code that says call that same function by the same name. That function is recursive. Now this might feel a little weird because if a function is calling itself it feels like this is the easiest way to get into an infinite loop because why would it ever stop if the function is calling itself calling

itself calling itself calling itself? We're going to have to actually address that kind of problem. But in the real world, we've actually or rather in this class already, we've actually seen implicitly an example of this including today as well as in week zero. So here is that algorithm for searching the doors of the lockers. And recall that

after we did this check at the very top, if there are any doors left, return false. If if uh not, we did these uh conditions. We said if the number is behind the middle door, return true because we found it. But things got interesting here where I said if else if the number is less than the middle door

then search the left half. Else if the number is greater than the middle door then search the right half. Well at that point in time you should be asking me or yourself well how do I sort search the left half? How do I search the right half? Well here you go. Like on the

screen right now is a search algorithm. And even though it says down here search the left half or search the right half which is like well how do I do that? We'll just use the same algorithm again. And this is how in terms of my voice over, you end up searching the left half

of the left half or the right half of the left half or any such combination. This line here, search left half. This line here, search right half, is representative of a recursive call. This is an algorithm or a function that calls itself. But why does it not induce an infinite loop? Like why is it important

that this line and this line are written exactly as they are so as to avoid this thing just forever searching aimlessly? Yeah, >> because there's the condition at which it stops. >> We do have this condition at which it stops. But more importantly, what is happening before I make these recursive calls? >> Exactly. I'm recursing that is calling

myself but I'm handing myself a smaller problem. A smaller problem. a smaller problem. It would be bad if I just handed myself the exact same number of doors and just kept saying, "Search these, search these, search these," because you would never make any progress. But just like our volunteers earlier, so long as we did divide and

conquer and we search smaller and smaller numbers of doors, eventually indeed we're going to bottom out and either find the number we're looking for or we're not. So, generally, we're going to call these kinds of conditions that sort of just ask a very obvious question and want an immediate answer base cases. Base cases are generally conditionals

that ask a question to which the answer is going to be yes or no right then and there. A recursive case by contrast these two down here is when you actually need to do a bit more work to get to your final answer. You call yourself but with a smaller version of the problem.

So we could have in fact in week zero have written this sort of similarly. If you go back to in your mind to week zero we had more of a procedural approach so to speak. When we were searching the phone book, I proposed that this induced what we called loops on line 8 and line

11, which just literally said go back to line three. And that was more of a mechanical way of sort of inducing a loop structure. But if I really wanted to be elegant, I could have said, well, you know what? 7 and 8 together really just mean search the left half. And 10 and 11 together really mean just search

the right half. So let's condense these pairs of lines into shorter instructions. Search the left half of the book. Search the right half of the book. I can then delete two blank lines and now I have a recursive algorithm for searching a phone book. It's a little less obvious because you have to ask

yourself when you get to line seven or nine, wait a minute, how do I search the left half or the right half? And that's when you need to realize you start the same algorithm again but with a problem that's half as large. In week zero, we do the procedural approach where we literally tell you what line of code to

go to, but today we're offering a different formulation, a recursive approach where it's more implicit what you should do. and we'll see now a couple of examples from the real world, so to speak. So, here's a screenshot from Super Mario Brothers 1 on the original Nintendo uh entertainment system. Let me go ahead and get rid of

some of the distraction like the the um ground and the mountains there. And here we have a sort of half pyramid, not unlike that you implemented in problem set one, but this is an interesting realworld physical structure in that you can define it recursively. Like what is a pyramid of height for if you will?

Well, just to be a little uh a little difficult, a pyramid of height four is really just a pyramid of height three plus one more row. Okay. Well, what is a pyramid of height three? Well, a pyramid of height three is really just a pyramid of height 2 plus one more row. Well,

what's a pyramid of height two? Well, a pyramid of height 2 is really just a pyramid of height one plus one more row. Well, what's a pyramid of height one? A single brick on the screen. And I sort of changed my tone with that last remark to convey that this could then be our

base case whereby I just tell you what the thing is without sort of kicking the can and inviting you to think through what a smaller structure is plus one more row. Whereas every other definition I gave you then of a pyramid of some height was defined in terms of that same structure albeit a smaller version

thereof. So we can actually um see this in the real world. Let me go ahead and pull up one thing here. I'm going to go to uh give me one sec before I flip over. Here I am on google.com. If you'd like a little computer science humor here, uh if you ever Google search for

recursion and hit enter, you'll see uh a joke that computer scientists at Google find funny. Haha. One, two laughs. Does anyone see the joke? I did not make a typo, but Google's asking me, did I mean recursion? And if I click on that, I just get the same haha page. Okay. All right. That didn't go over well. Anyhow,

so there are these Easter eggs in the wild everywhere because computer scientists are the ones that implement these things. But let's go ahead and actually um implement for instance a version of this in code. Let me go back over here in a moment to VS Code. And in VS Code, let me propose that in my

terminal window, let me create one of two final programs. This one's going to be called iteration.c C. Just to make clear that this is the iterative that is loopbased version of a program whose purpose in life is to print out a simple Mario pyramid. I'm going to go ahead and include cs50.h at the top as well as

standard io.h. I'm not going to need string.h. I don't need any command line arguments today. So this is going to start off with int main void. And now I'm going to go ahead and ask a question like uh give me a variable called height of type integer and ask the human for the height of this Mario like pyramid.

And then let's assume for the moment that I've already implemented a function called draw whose purpose in life is to draw a pyramid of that height semicolon. So I've abstracted away for the moment the notion of drawing that pyramid. Now let's actually implement draw whose purpose in life again is to print out a

pyramid akin to the one we saw a moment ago like this here on the screen. Well, in order to print out a pyramid of a given height, I think I need to say uh void uh draw int n for instance because I'm not going to bother returning a value. I just want this thing to print

something on the screen. So void is the return type. But I do want to take as input an integer like the height of the thing I want to print. I can call this argument or parameter anything I want. I'll call it n for number. So how can I print out a pyramid that again looks

like this? Well, I'll do this quicker than you might have in problem set one, but seems obvious that like on the first row I want one brick. On the second row, I want two. On the third, I want three. On the fourth, I want four. So, it's actually a little easier than problem

set one in that it's sloped in a different direction. So, let me go ahead and do exactly this in code. Let me say for int i= 0, i less than n the height i ++. So, this is going to be really for each row of the pyramid pyramid. Let me go ahead now and in an inner loop for

int J equals Z, let's do J less than I + 1 for reasons we'll see in a moment. And then J++ and then inside of this loop, let's just print out a single hash. No new line. But at the end of the row, let's print out a single new line to move the cursor to the next line. Now,

why am I doing this? Well, this represents for each column of pyramid. And if you think about it, on the first row, which is row zero, I actually want to print not zero bricks, but one brick. So that's why I want to go ahead here and go from 0 to i + 1. Because if i is

zero, i + 1 is 1. So my inner loop is going to go from 0 to one, which is going to give me one brick. It's a little annoying to think about the math, but this just makes sure that I'm actually getting bricks in the order I want them. And then it's going to give

me two bricks, and then three, and then four. And between each of those rows, it's going to print a new line. So, let's go ahead and do make iteration to compile this code. Ah, I messed up. Why do I have a mistake on line eight of this code? Let me hide my terminal and scroll back up. It seems

clang, my compiler does not like my draw function. Yeah. Yeah, I forgot the prototype. So, this is the one and only time where it seems reasonable to copy paste. Let's grab the prototype of that function up here and go ahead and teach the compiler from the get-go what this function is going to

look like. even though I'm not defining it now until line 13 onward. All right, let's go ahead and make iteration again. Ah, dot slashiteration. Enter. Let's do a height of say four. And voila, now I've got that there pyramid. So, I did it a little quickly and it's certainly to be expected if it took you hours on

problem set one to get the other type of pyramid printed. But the point for today is really to demonstrate how we can print a pyramid like this using indeed what I'd call iteration. Iteration just means using loops to solve some problem. But we can alternatively use recursion by reimplementing our draw function in a

way that's defined in terms of itself. So let me go into my code here and I'm actually going to leave the prototype the same. I'm going to leave main the same. But what I'm going to go ahead and do is delete all of this iterative code that's doing things very procedurally step by step by step with loops. And I'm

instead going to do something like this. Well, if I want to print a pyramid of height n, what did I say earlier? Well, a pyramid of height n is really just a pyramid of height n minus one plus one more row. So, how do I implement in code that idea? Well, let me go back in code

here and say, well, if a pyramid of height n first requires drawing a pyramid of height n minus one, I think I can just write this, which is kind of crazy to look at, but cuz you're calling yourself in yourself, but let's see where this takes us. Once I have drawn a pyramid of height n minus one that is a

height three for instance what remains for me to do is to myself print one more row and so to print one more row I think I can do that really easily with fewer loops I can do four int i= 0 i less than n i ++ and then very simply in this loop

I can print out a single hash one at a time at the end of this loop I can print out a new line but no more nesting of loops what I've done is print one more row. And here I've done print a pyramid of height n minus one. I'm not quite done yet, but I think this

is consistent with my verbal definition that a pyramid of height three is a pyramid of sorry, a pyramid of height four is a pyramid of height three, which I can implement per line 16. Just draw me a pyramid of height n minus one. And then I myself will take the trouble to print the fourth and final row. But

something's missing in this code. Let me go ahead and try running it. Let's see what happens. Make Oh, darn it. I meant to call this something else. So, I'm going to do this. I'm going to close this version here. I'm going to rename iteration C to recursion C to make clear that this version is completely

different. Let me now go ahead and make the recursion version. And huh, Clang is noticing that I have screwed up. On line 14, it says error. All paths through this function will call itself. And Clang doesn't even want to let me compile this code because that would mean literally just forever loop effectively by calling yourself. So

what am I missing in my code here? If I open up what we're now calling recursion C in my editor, what's missing here over here? Yeah, I'm missing a base case. And I can express this in a few different ways. But I would propose that before I do any drawing of anything at all, let's just

ask ourselves if there is anything to draw. So how about if n equals equals zero. Well then don't do anything just return. You don't return a value. When your return value is void, it means you don't return anything. So you just return period or return semicolon. Or just to be super safe, I could actually

do something like this, which is arguably better practice just in case I get into this perverse scenario where someone hands me a negative number. I want to be able to handle that and not print anything either. So just to be safe, I might say less than or equal to zero. I'm not doing one because if I did

do one, then I would want to at least myself print out one brick, which is fine, but I'd have to like re change all of my code a little bit. So I think it's safer if my base case is just if n is less than or equal to zero, you're done. Don't do anything. And this then ensures

that even though thereafter I keep calling draw again and again and again and the problems getting smaller and smaller from four to three to two to one, as soon as I hit zero, the function will finally return. So let's go ahead and open up my terminal. Rerun make recursion to make this version. did compile this time dot

/recursion enter let's type in four cross my fingers and this too prints the exact same thing and even though it doesn't look like fewer lines of code I would offer that there's an elegance to what I've just done whereas with the iterative version with all the loops it was very clunky like step by step just

print this and print that and have a nested loop inside of another but with this especially if we distill it into its essence by getting rid of my comments like this and frankly I can get rid of the unnecessary curly braces only because for single lines in conditionals, you don't need them. Like

this is arguably like a very beautiful implementation of drawing Mario's pyramid even though it's calling itself and arguably because it is calling itself. Questions then on this idea of recursion or this implementation of Mario? Yeah. >> Are there no scope issues involved if you like? >> Good question. Are there any scope issues involved? Short answer, no.

However, the current value of I, for instance, will not be visible to the next time the function is called. It will have its own copy of I, if that's what you mean. And we'll next week talk in more detail about what's going on here. And in fact, I probably can't break this in class very easily. But it

turns out if I use a very large version for heights, let's just hit a lot of zeros and see what happens. That was too many. Let's see what happens. That's also too many. Let's see what happens there. That's the first time at least I in class have encountered this error. You might have encountered this weird bug in

office hours or in your problem set and that's fine if you did. We'll talk about what this means next week too. But this is bad. Like this clearly hints at a problem in my code. However, the iterative version of this program would not have that same error. So this relates to something involving memory

because it turns out as a little teaser for next week, each time I call draw, I'm using a little more memory, a little more memory, a little more memory, a little more memory, and my computer only has so much memory. This program in its current form is using too much memory. There are workarounds to this, but that

is a trade-off to the elegance we're gaining in this solution. So, what's the point of all this? And how do we get all sidetracked by Mario? There's another sorting algorithm. The third and final one that we'll consider today that actually uses recursion to solve the problem not only elegantly arguably, but also way faster somehow than bubble sort

and selection sort. And in essence, it does so by making far fewer comparisons and wasting a lot less work. It doesn't keep comparing the same numbers again and again. Here in its essence is the pseudo code for merge sort. Sort the left half of the numbers, sort the right half of the numbers, then merge the

sorted halves. And this is kind of a weird implementation of an algorithm because I'm not really telling you anything. It seems like you're asking me how do I sort numbers? And I say, well, sort the left half, sort the right half. It's like someone being difficult. And yet implicit in this third line is

apparently some magic. This notion of merging halves that are somehow already sorted is actually going to yield a successful result. As an aside, we're actually going to need one base case here, too. So, if you're only given one number, you might as well quit right away because there's nothing to do. So, we'll toss that in there as well. And

base cases are often for zero or one or some small nums sized problem. In this case, it's a little easier to express it as one because if you have one element, it's indeed already sorted. So, what does it mean to merge two sorted halves? Well, let's actually consider this. I'm going to reuse some of these same

numbers here. I'm going to put my one, my three, my four, and my six on the left. And these together represent a list that is indeed sorted of size four. And then I'm going to put four other numbers on the right there that are similarly sorted as well. And by merging these two lists, I mean start at the

left end of this list, start at the left end of this list, and just decide one step at a time which number is the next smallest. And then I'm going to put it on the top shelf to make clear what is sorted. So if my left hand's pointing at this list, my right hand's pointing at

there, which hand is obviously pointing to the smaller element, left or right? Like the right. So I'm going to grab this and I'm going to use a little more space up top here and put the zero in place. And then I'm going to point to the next element there. So my left hand

has not moved yet. It's still pointing at the one. My right hand is pointing at the two. Which number comes next? Clearly left. So, I'm going to grab the one and put it up there and update where my left hand is pointing. So, now I'm pointing at the three here and the two

there. What comes next? Obviously the two. What comes next? Obviously the three. What comes next? Obviously the four. What comes next? Obviously the five. But notice my hands are not going back and forth, back and forth, back and forth like any of the algorithms thus far. I'm just taking baby steps, moving them only to the right, effectively

pointing at for a final time each number once and only once. What comes next? Six. And now my left hand is done. What comes last? The number seven. So what I just did is what I mean by merge the sorted halves. If you can somehow get into a scenario where you've got a small

list sorted and another small list sorted, it's super easy now to merge them together using that left right approach, which I'll claim only takes n steps. Why? Because every time I asked you a question, I was taking one bite out of the problem. There's eight bytes total. I asked you eight questions or I

would have if I verbalized them all. So, it's n steps total to merge lists of that size. So, what then is merge sort? Merge sort is really all three of these steps together, only one of which we've acted out. Two of which are sort of cyclical in nature. They're recursive by design. So what does this mean? Well,

let's start with this list of eight numbers, which is clearly out of order. 63 41 5270. And let's apply merge sort to this set of numbers. And I'll do it digitally here because it'll take forever to keep moving the numbers up and down physically. So let's move it to the top just to give ourselves a little

bit more room. And let me propose that we apply merge sort. What was the very first step in merge sort? At least that we highlighted the juicy steps. What's the first step in merge sort? >> Sort the left half. Yeah. And then the second step was going to be sort the right half. And then the third step was

going to be merge the sorted halves. So let's see what this means by actually acting it out on these numbers. So here's my eight numbers. Let's go ahead and sort the left half. Well, the left half is obviously going to be the four numbers on the left. And I'm just going to pull them out just to draw our

attention to them over here. Now I have a list of size four and the goal is to sort the left half. How do I sort a list of size four? >> Uh be well. Yes, but just be more pedantic like how do I sort any list using merge sort? >> Sort the left half. So let's do just

that. So of the list of size four, how do I sort this? Well, I'm going to sort the left half. How do I sort a list of size two? >> Sort the left half. All right. Well, I'm just going to write the six here. How do I sort a list of size one?

I just don't. I'm done. That was the so-called base case where I just said return. Like I'm done sorting the list. Okay. So here I here's the story recap. Sort the left half. Sort the left half. Sort the left half. And I just finished sorting this. So what comes next? Sort the right half, which is this. And now

I've sorted the left half of the left half of the left half, which is a big mouthful. But what do I do as a third and final step when sorting this list of size two? Merge them. This part we know how to do. I point left and right. And I now take the smallest element first,

which is the three. Then I take the six. And now this list of size two is sorted. So if you remind in your mind's eye, what step are we on? Well, we have now sorted the left half of the left half. So what comes after the left half is sorted? We sort the right half. So we're

sort of rewinding in time, but that's okay. I'm keeping track of the steps in my mind. I want to now sort this list of size two. How do you sort a list of size two? Well, you divide it into a list of size one. How do you sort this? You're done. You then take the other right half

and you sort it. Done. Now you merge the two sorted halves. So I point at the four and the one. Obviously the one comes first, then the four. Now I have sorted the right half of the uh the right half of the left half of the original numbers. What's the next step now that I have the left and right

halves of this list of s four sorted? Merge those. So same idea but with fewer elements. I'm pointing at the three and the one. Obviously the one comes. Now I'm pointing at the three and the four. Obviously the three comes next. Pointing at the six and the four. The four comes next. And now the six comes last. Now I

have sorted the left half. And it's intentional that 1 3 4 6 is the original arrangement of the lighted numbers I had on the shelves a moment ago. All right, it's a long story it seems. But what comes after you sorting the left half of the original list? You sort the right half. So let's put some uh put those

numbers over here. How do I sort a list of size four? Well, you sort the left half. How do you sort this thing of size two? You sort the left half. You sort the right half. And now you merge those together. How do I now sort the right half of the right half? Well, I sort the

left half. I sort the right half. And then I merge those together. Now I have sorted the left half and the right half of the right half of the original elements. What's next? The merging 0 2 5 and 7. Now we're exactly where we were originally with the lighted numbers. I've got 1 3 4 6. The left half sorted

0257. The right half sorted. What's the third and final step? Merge those two halves. of course 0 1 2 3 4 5 6 and 7 and hopefully even though there's a lot of words that come out of my mouth as acting this out there wasn't a lot of back and forth like I definitely wasn't

like walking back and forth physically and I also wasn't comparing the same numbers again and again. I was doing sort of different work at different conceptual levels but that was like only what like three levels total. It wasn't n levels on the board visually. So where does this get us with merge sorts? Well,

with merge sort, it would seem that we have an algorithm that I claim is doing a lot less work. The catch, though, is that merge sort requires twice as much space, just as we saw when I needed two shelves in order to merge those two lists. So, how much less work is actually going to be possible? Well,

let's consider sort of the analysis of the original list and how we might describe its its running time in terms of this big O notation. Hopefully, it's not going to be as bad as n squ ultimately. So, here are some like breadcrumbs that if I hadn't kept updating the screen and deleting numbers

once we moved them around, here are sort of like traces of every bit of work that we did. We started up here. We did the left half, the left half of the left half, the right half of the right half, and then everything else in between. And you'll see that essentially I took a

list of size eight and I did three different passes through it at this conceptual level, at this conceptual level, and at this one. And each time I did that, I had to merge elements together. And if you kind of think about it here, I pointed at four elements here and four elements here. And in total, I

pointed at eight elements. So there was n steps here for merging. And if you trust me, I'll claim that on this level, conceptually, there were also eight steps. I wasn't merging lists of size four, but I was merging two lists of size two over here and two more lists of size two over there. So if you add those

up, those are n total steps or or merges, if you will. And then down here, this was sort of kind of silly. I was but I was merging ultimately eight single lists alto together into the higher level of con uh of conceptually. So from a list of size eight we sort of had three levels of work and on each

level we did n steps the merging. So where is three? Well it turns out if you have eight elements up here the relationship between 8 and three is actually something formulaic and we can describe it as log base 2 of n. Why? Because if n is 8, if you don't mind doing some logarithms here, log base 2

of 8 is the same thing as log base 2 of 2 to the 3 power. The log 2 and the two cancel itself out, which gives you exactly the number three that I sort of visualized with those traces on the screen. Which is to say irrespective of the specific value of n the big O

running time of merge sort is apparently not n^ squ but it's log n time n or more conventionally n * log n because you're doing n things log n times technically base 2 but we don't care about that generally for big O notation and indeed in big O notation we would say that

merge sort is on the order of n log n that's it big O running time sort of at the upper upper bound. What about the lower order bound? Well, there's no clever optimization in our current implementation as there was for bubble sort. And so it turns out the lower bound would be an omega of n login and

in theta therefore of n login as well because big o and omega are in fact in this case one and the same. And if we actually go back to our visualization from earlier, give me just a moment to pull that up here. In our earlier implementation or an earlier demonstration of these algorithms, we

had a side-by-side comparison of all the comparisons. But here, if I go ahead and randomize it and click merge sort, you'll see a very different and clearly faster algorithm even though the computer speed has not changed. But it's touching these elements so many fewer times. It's wasting a lot less time because of this cleverness where it's

instead dividing and conquering the problem into smaller and smaller and smaller pieces. And to give this a final flourish since that was yes faster but not necessarily obviously faster than other things that we've done. How might we actually compare these things side by side by side? Well, in our final moments together, let's go ahead and

dramatically and for no real reason just dim the lights so that I'll hit play on a visualization that at the top is going to show you selection sort with a bunch of random data. On the bottom is going to show you show you bubble sort with a bunch of random data. And in the middle

is going to show you merge sort. And the takeaway ultimately for today is the appreciable feel of difference between big O of N squ and now big O of N log N.

[music]

Heat. Heat. [music]

Heat. Heat. [music]

All right, the music just makes sorting more fun. But that's it for today. We will see you next time. [applause]

>> [music]