[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:07.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:07.00,0:00:10.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:10.00,0:00:27.00,Default,,0000,0000,0000,,This presentation is delivered by the Stanford Center for Professional Development.
Dialogue: 0,0:00:27.00,0:00:30.00,Default,,0000,0000,0000,,Good afternoon. Apparently, Winter Quarter is over and it's now Spring.
Dialogue: 0,0:00:30.00,0:00:34.00,Default,,0000,0000,0000,,I don't know what happened to the weather, but I'm pretty happy about it. I hope you are too. Let's see. Where
Dialogue: 0,0:00:34.00,0:00:39.00,Default,,0000,0000,0000,,are we at? We are picking back up with the text. Looking at Chapter 7. Chapter 7 is gonna
Dialogue: 0,0:00:39.00,0:00:43.00,Default,,0000,0000,0000,,be the theme for pretty much the whole week. Talking about algorithms and
Dialogue: 0,0:00:43.00,0:00:46.00,Default,,0000,0000,0000,,different ways of analyzing them, formalizing their
Dialogue: 0,0:00:46.00,0:00:50.00,Default,,0000,0000,0000,,performance, and then talking about sorting as an example problem to kind of
Dialogue: 0,0:00:50.00,0:00:55.00,Default,,0000,0000,0000,,discuss in terms of algorithms and options for solving that problem.
Dialogue: 0,0:00:55.00,0:00:57.00,Default,,0000,0000,0000,,Okay. So let's talk about algorithms. Algorithm is
Dialogue: 0,0:00:57.00,0:01:03.00,Default,,0000,0000,0000,,one of the most interesting things to think about from a CS perspective. Kind of one of the most
Dialogue: 0,0:01:03.00,0:01:04.00,Default,,0000,0000,0000,,intellectually
Dialogue: 0,0:01:04.00,0:01:08.00,Default,,0000,0000,0000,,interesting areas to think about things is that often, right? We're trying to solve a particular
Dialogue: 0,0:01:08.00,0:01:08.00,Default,,0000,0000,0000,,problem.
Dialogue: 0,0:01:08.00,0:01:09.00,Default,,0000,0000,0000,,We want to
Dialogue: 0,0:01:09.00,0:01:13.00,Default,,0000,0000,0000,,put this data into sorted order. We want to count these scores and place them into a
Dialogue: 0,0:01:13.00,0:01:14.00,Default,,0000,0000,0000,,histogram.
Dialogue: 0,0:01:14.00,0:01:19.00,Default,,0000,0000,0000,,We want to search a maze to find a path from the start to the goal.
Dialogue: 0,0:01:19.00,0:01:20.00,Default,,0000,0000,0000,,For any of those tasks,
Dialogue: 0,0:01:20.00,0:01:24.00,Default,,0000,0000,0000,,right? There may be multiple ways we could go about solving that problem
Dialogue: 0,0:01:24.00,0:01:28.00,Default,,0000,0000,0000,,that approach it from different angles, using different kinds of data structure, solving
Dialogue: 0,0:01:28.00,0:01:31.00,Default,,0000,0000,0000,,it in forward versus solving it in reverse, is it easier to get from
Dialogue: 0,0:01:31.00,0:01:35.00,Default,,0000,0000,0000,,the goal back to the start? In the end the path is invertible, so maybe it doesn't matter which
Dialogue: 0,0:01:35.00,0:01:36.00,Default,,0000,0000,0000,,end we start from.
Dialogue: 0,0:01:36.00,0:01:39.00,Default,,0000,0000,0000,,Would it be better to use an array for this or a vector? Would a set help us
Dialogue: 0,0:01:39.00,0:01:41.00,Default,,0000,0000,0000,,out? Could we use a map?
Dialogue: 0,0:01:41.00,0:01:45.00,Default,,0000,0000,0000,,Could I use iteration? Could I use recursion? Lots of different ways we could do this. Often sometimes the
Dialogue: 0,0:01:45.00,0:01:47.00,Default,,0000,0000,0000,,decision-making will be about, well,
Dialogue: 0,0:01:47.00,0:01:52.00,Default,,0000,0000,0000,,do I need to get the perfect best answer? Am I willing to take some approximation? Some estimation
Dialogue: 0,0:01:52.00,0:01:54.00,Default,,0000,0000,0000,,of a good answer
Dialogue: 0,0:01:54.00,0:01:58.00,Default,,0000,0000,0000,,that gives me a rough count of something that might be faster to do than doing a real
Dialogue: 0,0:01:58.00,0:01:59.00,Default,,0000,0000,0000,,precise count?
Dialogue: 0,0:01:59.00,0:02:03.00,Default,,0000,0000,0000,,So what we're gonna be looking at, right? Is taking a particular problem, sorting is gonna be the one
Dialogue: 0,0:02:03.00,0:02:05.00,Default,,0000,0000,0000,,that we spend the most time on,
Dialogue: 0,0:02:05.00,0:02:08.00,Default,,0000,0000,0000,,and think about, well, some of the different ways we can go about putting
Dialogue: 0,0:02:08.00,0:02:09.00,Default,,0000,0000,0000,,data in sorted order
Dialogue: 0,0:02:09.00,0:02:13.00,Default,,0000,0000,0000,,and then talk about what the strengths and weaknesses of those algorithms are compared
Dialogue: 0,0:02:13.00,0:02:14.00,Default,,0000,0000,0000,,to one another.
Dialogue: 0,0:02:14.00,0:02:16.00,Default,,0000,0000,0000,,Do they differ in how much
Dialogue: 0,0:02:16.00,0:02:21.00,Default,,0000,0000,0000,,time it will take to sort a particular data set? Does it matter if the data is almost sorted?
Dialogue: 0,0:02:21.00,0:02:22.00,Default,,0000,0000,0000,,Does it actually
Dialogue: 0,0:02:22.00,0:02:26.00,Default,,0000,0000,0000,,affect the performance of the algorithm? What happens if the data set is very large? How much memory is
Dialogue: 0,0:02:26.00,0:02:28.00,Default,,0000,0000,0000,,gonna be used by it?
Dialogue: 0,0:02:28.00,0:02:30.00,Default,,0000,0000,0000,,And we'll be thinking about as we do this, right? Is often
Dialogue: 0,0:02:30.00,0:02:34.00,Default,,0000,0000,0000,,that probably the most important thing is how does it run? How much time does it take?
Dialogue: 0,0:02:34.00,0:02:37.00,Default,,0000,0000,0000,,How much memory does it use? How accurate is its answer?
Dialogue: 0,0:02:37.00,0:02:38.00,Default,,0000,0000,0000,,But also
Dialogue: 0,0:02:38.00,0:02:41.00,Default,,0000,0000,0000,,given that brainpower is often in short supply,
Dialogue: 0,0:02:41.00,0:02:45.00,Default,,0000,0000,0000,,it's worth thinking about, well, is the code easy to develop, to write, to get correct, and kind
Dialogue: 0,0:02:45.00,0:02:46.00,Default,,0000,0000,0000,,of debug?
Dialogue: 0,0:02:46.00,0:02:49.00,Default,,0000,0000,0000,,It may be that a simpler algorithm
Dialogue: 0,0:02:49.00,0:02:53.00,Default,,0000,0000,0000,,that doesn't run as fast, but that's really easy to get working, might actually be the one you
Dialogue: 0,0:02:53.00,0:02:57.00,Default,,0000,0000,0000,,need to solve this particular problem and save the fancy thing for some day when really
Dialogue: 0,0:02:57.00,0:03:00.00,Default,,0000,0000,0000,,you needed that extra speed boost.
Dialogue: 0,0:03:00.00,0:03:04.00,Default,,0000,0000,0000,,So I'm gonna do a little brainstorming exercise with you. Just to kind of get you thinking about
Dialogue: 0,0:03:04.00,0:03:08.00,Default,,0000,0000,0000,,there's lots of different ways to solve what seems like the same problem.
Dialogue: 0,0:03:08.00,0:03:12.00,Default,,0000,0000,0000,,All right. I'd like to know how many students are sitting in this room right now.
Dialogue: 0,0:03:12.00,0:03:14.00,Default,,0000,0000,0000,,All right. I look around.
Dialogue: 0,0:03:14.00,0:03:17.00,Default,,0000,0000,0000,,Michelle,
Dialogue: 0,0:03:17.00,0:03:18.00,Default,,0000,0000,0000,,what's the easiest way
Dialogue: 0,0:03:18.00,0:03:20.00,Default,,0000,0000,0000,,and most reliable way
Dialogue: 0,0:03:20.00,0:03:28.00,Default,,0000,0000,0000,,to just get a count, an accurate count, of everybody in this room? Start by identifying what kind of
Dialogue: 0,0:03:28.00,0:03:31.00,Default,,0000,0000,0000,,[inaudible]. Yeah. Just have a strategy. Some people will use the front row. And I see one,
Dialogue: 0,0:03:31.00,0:03:35.00,Default,,0000,0000,0000,,two, three, four, five and then I go back and I just work my way through the room
Dialogue: 0,0:03:35.00,0:03:37.00,Default,,0000,0000,0000,,all the way to the end, right?
Dialogue: 0,0:03:37.00,0:03:41.00,Default,,0000,0000,0000,,What I've done, if I actually remember my grade school counting, right? Then I should have
Dialogue: 0,0:03:41.00,0:03:42.00,Default,,0000,0000,0000,,come up with a number
Dialogue: 0,0:03:42.00,0:03:45.00,Default,,0000,0000,0000,,that matched the number of people in the room
Dialogue: 0,0:03:45.00,0:03:48.00,Default,,0000,0000,0000,,and tells me, okay, there's 100 people, let's say, that are here.
Dialogue: 0,0:03:48.00,0:03:52.00,Default,,0000,0000,0000,,So that will definitely work. That's the easiest most ways to, sort of, likely approach you'd think
Dialogue: 0,0:03:52.00,0:03:54.00,Default,,0000,0000,0000,,of. You need to count something, well, then count them, right?
Dialogue: 0,0:03:54.00,0:03:56.00,Default,,0000,0000,0000,,Now, I'm gonna talk about ways that we could do it
Dialogue: 0,0:03:56.00,0:04:00.00,Default,,0000,0000,0000,,that maybe aren't so obvious, but that might have different properties
Dialogue: 0,0:04:00.00,0:04:05.00,Default,,0000,0000,0000,,in terms of trading it off. Let's say that the goal was to count all of the people in Stanford Stadium,
Dialogue: 0,0:04:05.00,0:04:08.00,Default,,0000,0000,0000,,right? And so I've got a whole bunch of people sitting there.
Dialogue: 0,0:04:08.00,0:04:11.00,Default,,0000,0000,0000,,The count in turn walking around the stadium doesn't
Dialogue: 0,0:04:11.00,0:04:13.00,Default,,0000,0000,0000,,scale that well.
Dialogue: 0,0:04:13.00,0:04:16.00,Default,,0000,0000,0000,,However long it took me to work my way through the rows in this room, right?
Dialogue: 0,0:04:16.00,0:04:20.00,Default,,0000,0000,0000,,When you multiple it by the size of the Stanford Stadium is gonna take a long
Dialogue: 0,0:04:20.00,0:04:23.00,Default,,0000,0000,0000,,time and as people get up and go the bathroom and move around and whatnot I might
Dialogue: 0,0:04:23.00,0:04:25.00,Default,,0000,0000,0000,,lose track of where I'm at and
Dialogue: 0,0:04:25.00,0:04:29.00,Default,,0000,0000,0000,,all sorts of complications that doesn't really work well in the large.
Dialogue: 0,0:04:29.00,0:04:31.00,Default,,0000,0000,0000,,So here's another option. Anyone
Dialogue: 0,0:04:31.00,0:04:35.00,Default,,0000,0000,0000,,else want to give me just another way of thinking about this? Yeah? Multiply
Dialogue: 0,0:04:35.00,0:04:36.00,Default,,0000,0000,0000,,yourself
Dialogue: 0,0:04:36.00,0:04:38.00,Default,,0000,0000,0000,,into more Julies.
Dialogue: 0,0:04:38.00,0:04:40.00,Default,,0000,0000,0000,,Because we can only ? one Julie's not really enough, right? So
Dialogue: 0,0:04:40.00,0:04:44.00,Default,,0000,0000,0000,,recursion. Can recursion help us out here, right? Can I do some delegating,
Dialogue: 0,0:04:44.00,0:04:47.00,Default,,0000,0000,0000,,right? Some subcounting to other people?
Dialogue: 0,0:04:47.00,0:04:50.00,Default,,0000,0000,0000,,So in the case of this room, it might be that I pick somebody to count the left side, somebody to count
Dialogue: 0,0:04:50.00,0:04:56.00,Default,,0000,0000,0000,,the right side, and somebody to count the middle. And maybe even they themselves decide to use a little delegation in
Dialogue: 0,0:04:56.00,0:04:57.00,Default,,0000,0000,0000,,their work and say, well, how about I
Dialogue: 0,0:04:57.00,0:05:02.00,Default,,0000,0000,0000,,get some volunteers on each row? That's sort of idea would work extremely well in the Stanford Stadium
Dialogue: 0,0:05:02.00,0:05:05.00,Default,,0000,0000,0000,,as well because you just divide it up even further. You say, well, here's this row, this
Dialogue: 0,0:05:05.00,0:05:06.00,Default,,0000,0000,0000,,row,
Dialogue: 0,0:05:06.00,0:05:11.00,Default,,0000,0000,0000,,that row and kind of having all of these delegates working in parallel to count the stadium, right? Getting recursion to kind of
Dialogue: 0,0:05:11.00,0:05:14.00,Default,,0000,0000,0000,,solve that same problem.
Dialogue: 0,0:05:14.00,0:05:15.00,Default,,0000,0000,0000,,What if I wanted
Dialogue: 0,0:05:15.00,0:05:18.00,Default,,0000,0000,0000,,? I was willing to tolerate a little bit of inaccuracy?
Dialogue: 0,0:05:18.00,0:05:22.00,Default,,0000,0000,0000,,What if I wanted an estimate of the people that were in this room and I was willing
Dialogue: 0,0:05:22.00,0:05:24.00,Default,,0000,0000,0000,,to accept a little bit of sampling or
Dialogue: 0,0:05:24.00,0:05:27.00,Default,,0000,0000,0000,,estimation error? Maybe you could take,
Dialogue: 0,0:05:27.00,0:05:29.00,Default,,0000,0000,0000,,like, a
Dialogue: 0,0:05:29.00,0:05:35.00,Default,,0000,0000,0000,,little area of seats and count how many people are in those seats and then multiply it by how many of
Dialogue: 0,0:05:35.00,0:05:36.00,Default,,0000,0000,0000,,those areas are in the room?
Dialogue: 0,0:05:36.00,0:05:40.00,Default,,0000,0000,0000,,Yeah. So it's like this capacity. Somewhere there's a sign, right? On one of the doors here that
Dialogue: 0,0:05:40.00,0:05:43.00,Default,,0000,0000,0000,,will say, oh, this room seats 180 people.
Dialogue: 0,0:05:43.00,0:05:46.00,Default,,0000,0000,0000,,So I know that there are 180 seats without doing any counting.
Dialogue: 0,0:05:46.00,0:05:48.00,Default,,0000,0000,0000,,So if I took a section.
Dialogue: 0,0:05:48.00,0:05:50.00,Default,,0000,0000,0000,,So I take ten seats, let's say,
Dialogue: 0,0:05:50.00,0:05:55.00,Default,,0000,0000,0000,,or 18 seats for that matter. I take 18 seats and I count those 18 seats how many are occupied
Dialogue: 0,0:05:55.00,0:05:59.00,Default,,0000,0000,0000,,and let's say half of them of the 18 that I look at were occupied then I can say, well, the room's
Dialogue: 0,0:05:59.00,0:06:04.00,Default,,0000,0000,0000,,about half full, right? And then I say, well, okay, 180 seats, half of them, right? Means 90 people are here.
Dialogue: 0,0:06:04.00,0:06:07.00,Default,,0000,0000,0000,,So in that case it's not guaranteed to be accurate, right? If I happen to pick a particularly
Dialogue: 0,0:06:07.00,0:06:11.00,Default,,0000,0000,0000,,dense or sparsely populated section, right? I'd be getting some sampling error based on
Dialogue: 0,0:06:11.00,0:06:14.00,Default,,0000,0000,0000,,that, but that would also work in the Stanford Stadium, right? We know how many seats are in the Stanford
Dialogue: 0,0:06:14.00,0:06:17.00,Default,,0000,0000,0000,,Stadium, right? You pick a section
Dialogue: 0,0:06:17.00,0:06:20.00,Default,,0000,0000,0000,,and you count it. You count 100 seats worth to get a percentage of how full
Dialogue: 0,0:06:20.00,0:06:24.00,Default,,0000,0000,0000,,it is and then just multiply it out to see what you get.
Dialogue: 0,0:06:24.00,0:06:28.00,Default,,0000,0000,0000,,There's a variation on that that's kind of a ? maybe not the first thing that would occur to you, right? Is just that
Dialogue: 0,0:06:28.00,0:06:31.00,Default,,0000,0000,0000,,the idea of counting some subsections is kind of interesting
Dialogue: 0,0:06:31.00,0:06:35.00,Default,,0000,0000,0000,,as a way to kind of divide the problem and then say, well, in the small can I do some
Dialogue: 0,0:06:35.00,0:06:37.00,Default,,0000,0000,0000,,counting that will then scale up?
Dialogue: 0,0:06:37.00,0:06:39.00,Default,,0000,0000,0000,,So, for example, if I had everybody in this room and I said, okay, think of
Dialogue: 0,0:06:39.00,0:06:43.00,Default,,0000,0000,0000,,a number between one and ten. Everybody just think of a number independently on your own. Okay.
Dialogue: 0,0:06:43.00,0:06:47.00,Default,,0000,0000,0000,,If you were thinking of the number four, raise your hand.
Dialogue: 0,0:06:47.00,0:06:51.00,Default,,0000,0000,0000,,I got one, two, three, four, five, six, seven. Seven people. And said, okay, well, if I figure that everybody
Dialogue: 0,0:06:51.00,0:06:55.00,Default,,0000,0000,0000,,was just as likely to pick a number between one and ten as four,
Dialogue: 0,0:06:55.00,0:06:56.00,Default,,0000,0000,0000,,then those seven people, right?
Dialogue: 0,0:06:56.00,0:07:01.00,Default,,0000,0000,0000,,Represent 10 percent of the population. So maybe there were 70 of you. Again, totally based on randomness
Dialogue: 0,0:07:01.00,0:07:05.00,Default,,0000,0000,0000,,and sampling error, right? If I happen to pick a number that's very unpopular with my crowd, right?
Dialogue: 0,0:07:05.00,0:07:08.00,Default,,0000,0000,0000,,Or very popular, I get kind of an artificial estimate.
Dialogue: 0,0:07:08.00,0:07:11.00,Default,,0000,0000,0000,,But it does tell you a little bit about the nature of just solving this
Dialogue: 0,0:07:11.00,0:07:15.00,Default,,0000,0000,0000,,problem. It's like how much error am I willing to tolerate and how much time I'm willing to invest in it, how big
Dialogue: 0,0:07:15.00,0:07:17.00,Default,,0000,0000,0000,,is the problem I'm trying to solve?
Dialogue: 0,0:07:17.00,0:07:19.00,Default,,0000,0000,0000,,What kind of things can I do that might,
Dialogue: 0,0:07:19.00,0:07:22.00,Default,,0000,0000,0000,,in the end, give me some estimate
Dialogue: 0,0:07:22.00,0:07:25.00,Default,,0000,0000,0000,,or accurate count, right? Depending on what I'm willing to invest in the time
Dialogue: 0,0:07:25.00,0:07:28.00,Default,,0000,0000,0000,,spent.
Dialogue: 0,0:07:28.00,0:07:31.00,Default,,0000,0000,0000,,So random thought for you. Here's another one. I can take the access
Dialogue: 0,0:07:31.00,0:07:33.00,Default,,0000,0000,0000,,class list, right?
Dialogue: 0,0:07:33.00,0:07:35.00,Default,,0000,0000,0000,,And I can take the first ten people
Dialogue: 0,0:07:35.00,0:07:37.00,Default,,0000,0000,0000,,and call out their names and find out if they're here
Dialogue: 0,0:07:37.00,0:07:40.00,Default,,0000,0000,0000,,and on that, right? I would get this estimate of, well, what percentage of my students actually
Dialogue: 0,0:07:40.00,0:07:41.00,Default,,0000,0000,0000,,come?
Dialogue: 0,0:07:41.00,0:07:44.00,Default,,0000,0000,0000,,So if my class list says that there's 220 students, which it does because where are
Dialogue: 0,0:07:44.00,0:07:45.00,Default,,0000,0000,0000,,they?
Dialogue: 0,0:07:45.00,0:07:48.00,Default,,0000,0000,0000,,And I take the first of ten students, right? And I call them out and I discover three of them are
Dialogue: 0,0:07:48.00,0:07:52.00,Default,,0000,0000,0000,,here I can say, oh, about 30 percent of my 220 students
Dialogue: 0,0:07:52.00,0:07:54.00,Default,,0000,0000,0000,,come, 66 of you.
Dialogue: 0,0:07:54.00,0:07:57.00,Default,,0000,0000,0000,,And then I would also have the advantage of knowing who was a slacker and I could write it
Dialogue: 0,0:07:57.00,0:07:59.00,Default,,0000,0000,0000,,down in my book.
Dialogue: 0,0:07:59.00,0:08:05.00,Default,,0000,0000,0000,,No, no, no. I'm sure you guys are all at home watching in your bunny slippers. All right. So
Dialogue: 0,0:08:05.00,0:08:07.00,Default,,0000,0000,0000,,let's talk about in terms of computer things. Like
Dialogue: 0,0:08:07.00,0:08:12.00,Default,,0000,0000,0000,,that the situation often is you have a problem to solve, right? You need to do this thing.
Dialogue: 0,0:08:12.00,0:08:14.00,Default,,0000,0000,0000,,You need to solve this maze or
Dialogue: 0,0:08:14.00,0:08:15.00,Default,,0000,0000,0000,,
Dialogue: 0,0:08:15.00,0:08:20.00,Default,,0000,0000,0000,,compute this histogram or find the mode score in your class or something like that
Dialogue: 0,0:08:20.00,0:08:23.00,Default,,0000,0000,0000,,and you have these different options about how you might proceed. Which data structure you use
Dialogue: 0,0:08:23.00,0:08:25.00,Default,,0000,0000,0000,,and how you're gonna approach it and stuff like that.
Dialogue: 0,0:08:25.00,0:08:29.00,Default,,0000,0000,0000,,Certainly one way to do it, and not a very practical way to do it, would be to say, well, I'll
Dialogue: 0,0:08:29.00,0:08:32.00,Default,,0000,0000,0000,,just go implement the five different ways I could do this. For example, when I was running your
Dialogue: 0,0:08:32.00,0:08:36.00,Default,,0000,0000,0000,,maze assignment that's what I did. I wrote, like, ten different maze solvers until I decided which one I was
Dialogue: 0,0:08:36.00,0:08:37.00,Default,,0000,0000,0000,,gonna give you.
Dialogue: 0,0:08:37.00,0:08:41.00,Default,,0000,0000,0000,,That's not very practical, right? If your boss said to you, you know, you need to solve task A
Dialogue: 0,0:08:41.00,0:08:45.00,Default,,0000,0000,0000,,and you're response was I'll solve it ten different ways and then I'll come back to you with the
Dialogue: 0,0:08:45.00,0:08:46.00,Default,,0000,0000,0000,,best one.
Dialogue: 0,0:08:46.00,0:08:48.00,Default,,0000,0000,0000,,That might take more time than you've got.
Dialogue: 0,0:08:48.00,0:08:49.00,Default,,0000,0000,0000,,
Dialogue: 0,0:08:49.00,0:08:52.00,Default,,0000,0000,0000,,So you would have to write it, you'd debug it, you'd test it, and then you could kind of time it using
Dialogue: 0,0:08:52.00,0:08:56.00,Default,,0000,0000,0000,,your stopwatch to find out how good did it do on these data sets.
Dialogue: 0,0:08:56.00,0:09:00.00,Default,,0000,0000,0000,,Yeah. Well, there's some issues with that. First of all, you have to go do it, right?
Dialogue: 0,0:09:00.00,0:09:01.00,Default,,0000,0000,0000,,Which is kind of a hassle.
Dialogue: 0,0:09:01.00,0:09:04.00,Default,,0000,0000,0000,,And then also it's subject to these variations, like, well, what computer were you running on? What
Dialogue: 0,0:09:04.00,0:09:07.00,Default,,0000,0000,0000,,OS were you running? What other tasks were running? Like did it ?
Dialogue: 0,0:09:07.00,0:09:10.00,Default,,0000,0000,0000,,it may not be completely reliable whatever results you saw.
Dialogue: 0,0:09:10.00,0:09:14.00,Default,,0000,0000,0000,,What we're gonna be more interested in is doing it in a more formal abstract way, which is just analyzing
Dialogue: 0,0:09:14.00,0:09:18.00,Default,,0000,0000,0000,,the algorithm from a pseudocode standpoint. Knowing what the code does and the steps that
Dialogue: 0,0:09:18.00,0:09:19.00,Default,,0000,0000,0000,,it takes, right?
Dialogue: 0,0:09:19.00,0:09:24.00,Default,,0000,0000,0000,,What can we predict about how that algorithm will behave? What situations will it
Dialogue: 0,0:09:24.00,0:09:28.00,Default,,0000,0000,0000,,do well? What situations will it do poorly? When will it get the accurate answer or an estimate?
Dialogue: 0,0:09:28.00,0:09:31.00,Default,,0000,0000,0000,,How much time and space can we
Dialogue: 0,0:09:31.00,0:09:34.00,Default,,0000,0000,0000,,predict it will use based on the size of its input?
Dialogue: 0,0:09:34.00,0:09:37.00,Default,,0000,0000,0000,,That would tell us based on just some descriptions of the algorithm
Dialogue: 0,0:09:37.00,0:09:41.00,Default,,0000,0000,0000,,which one might be the best one that's gonna work out in practice. Then we can go off and really implement
Dialogue: 0,0:09:41.00,0:09:44.00,Default,,0000,0000,0000,,the one that we've chosen.
Dialogue: 0,0:09:44.00,0:09:49.00,Default,,0000,0000,0000,,So this is actually working more the mathematical sense, less on the stopwatch sense. But
Dialogue: 0,0:09:49.00,0:09:55.00,Default,,0000,0000,0000,,helps us to analyze things before we've gone through all the process of writing the code. So what I'm gonna do
Dialogue: 0,0:09:55.00,0:10:04.00,Default,,0000,0000,0000,,with you today is a little bit of just analysis of some code we didn't write to talk about how it behaves and then we're gonna go on and talk about the sorting problem and some of the options for that.
Dialogue: 0,0:10:04.00,0:10:09.00,Default,,0000,0000,0000,,So this one is a function that converts the temperature. You give it a temperature in Celsius and
Dialogue: 0,0:10:09.00,0:10:11.00,Default,,0000,0000,0000,,it converts it to the Fahrenheit equivalent by
Dialogue: 0,0:10:11.00,0:10:14.00,Default,,0000,0000,0000,,doing the multiplication and addition.
Dialogue: 0,0:10:14.00,0:10:19.00,Default,,0000,0000,0000,,So the basic, sort of, underpitting of kind of looking at it formally is to basically realize
Dialogue: 0,0:10:19.00,0:10:22.00,Default,,0000,0000,0000,,that we're gonna count the statements that are executed.
Dialogue: 0,0:10:22.00,0:10:25.00,Default,,0000,0000,0000,,Assuming, right? In this very gross overgeneralization
Dialogue: 0,0:10:25.00,0:10:26.00,Default,,0000,0000,0000,,that each
Dialogue: 0,0:10:26.00,0:10:29.00,Default,,0000,0000,0000,,action that you take costs the same amount.
Dialogue: 0,0:10:29.00,0:10:33.00,Default,,0000,0000,0000,,That doing the multiply and the divide and the addition and a return, that
Dialogue: 0,0:10:33.00,0:10:35.00,Default,,0000,0000,0000,,all those things are, like, one unit. In this
Dialogue: 0,0:10:35.00,0:10:37.00,Default,,0000,0000,0000,,case, I'm gonna call it a penny, right?
Dialogue: 0,0:10:37.00,0:10:39.00,Default,,0000,0000,0000,,It took a penny to do each of those operations.
Dialogue: 0,0:10:39.00,0:10:43.00,Default,,0000,0000,0000,,That's not really accurate to be fair. There's some operations that are more expensive at the
Dialogue: 0,0:10:43.00,0:10:47.00,Default,,0000,0000,0000,,low level than others, but we're gonna be pretty rough about our estimate
Dialogue: 0,0:10:47.00,0:10:48.00,Default,,0000,0000,0000,,here
Dialogue: 0,0:10:48.00,0:10:50.00,Default,,0000,0000,0000,,in this first step here.
Dialogue: 0,0:10:50.00,0:10:54.00,Default,,0000,0000,0000,,So there's a multiply, there's a divide, there's an add, there's a return, right? And so I have, like, four statements
Dialogue: 0,0:10:54.00,0:10:59.00,Default,,0000,0000,0000,,worth of stuff that goes into asking a temperature to be converted.
Dialogue: 0,0:10:59.00,0:11:01.00,Default,,0000,0000,0000,,The other thing you'll note is that, does it
Dialogue: 0,0:11:01.00,0:11:03.00,Default,,0000,0000,0000,,matter if the temperature is high or low? If
Dialogue: 0,0:11:03.00,0:11:07.00,Default,,0000,0000,0000,,we ask it to convert Celsius of zero, Celsius of 100, Celsius of 50
Dialogue: 0,0:11:07.00,0:11:09.00,Default,,0000,0000,0000,,it does the same amount of work no matter what.
Dialogue: 0,0:11:09.00,0:11:13.00,Default,,0000,0000,0000,,So actually that the ? for whatever inputs, right? You give it this function pretty much
Dialogue: 0,0:11:13.00,0:11:16.00,Default,,0000,0000,0000,,will take the same amount of time.
Dialogue: 0,0:11:16.00,0:11:19.00,Default,,0000,0000,0000,,That's good to know, right? There's certain functions that will be like that.
Dialogue: 0,0:11:19.00,0:11:22.00,Default,,0000,0000,0000,,So we would call this a constant time function. It's, like, no matter what you ask it to convert
Dialogue: 0,0:11:22.00,0:11:24.00,Default,,0000,0000,0000,,it takes about the same amount of time.
Dialogue: 0,0:11:24.00,0:11:30.00,Default,,0000,0000,0000,,That doesn't mean that it takes no time, but it is a reliable performer of
Dialogue: 0,0:11:30.00,0:11:33.00,Default,,0000,0000,0000,,relative inputs.
Dialogue: 0,0:11:33.00,0:11:35.00,Default,,0000,0000,0000,,So let's look at this guy.
Dialogue: 0,0:11:35.00,0:11:38.00,Default,,0000,0000,0000,,This is one that takes in a vector
Dialogue: 0,0:11:38.00,0:11:40.00,Default,,0000,0000,0000,,and then it sums all the values in the vector
Dialogue: 0,0:11:40.00,0:11:46.00,Default,,0000,0000,0000,,and then divides that sum by the total number of elements to compute its average. Okay.
Dialogue: 0,0:11:46.00,0:11:50.00,Default,,0000,0000,0000,,So, again, kind of using this idea that will everything you do cost you a penny?
Dialogue: 0,0:11:50.00,0:11:52.00,Default,,0000,0000,0000,,How much is it gonna cost you
Dialogue: 0,0:11:52.00,0:11:56.00,Default,,0000,0000,0000,,to make a call to the average function? Well, this
Dialogue: 0,0:11:56.00,0:11:59.00,Default,,0000,0000,0000,,is a little tricky because, in fact, there's a loop in here, right? That's executed a variable
Dialogue: 0,0:11:59.00,0:12:02.00,Default,,0000,0000,0000,,number of times depending on the size of the input.
Dialogue: 0,0:12:02.00,0:12:05.00,Default,,0000,0000,0000,,So first let's look at the things that are outside the loop, right? Outside the loop we do things
Dialogue: 0,0:12:05.00,0:12:07.00,Default,,0000,0000,0000,,like initialize the sum,
Dialogue: 0,0:12:07.00,0:12:10.00,Default,,0000,0000,0000,,we initialize I before we enter the loop, right?
Dialogue: 0,0:12:10.00,0:12:14.00,Default,,0000,0000,0000,,We do this division here at the bottom and this returns. There are about four things we do
Dialogue: 0,0:12:14.00,0:12:19.00,Default,,0000,0000,0000,,outside of getting into and then iterating in the loops. So just four things we pay no
Dialogue: 0,0:12:19.00,0:12:20.00,Default,,0000,0000,0000,,matter what.
Dialogue: 0,0:12:20.00,0:12:23.00,Default,,0000,0000,0000,,Then we get into this loop body
Dialogue: 0,0:12:23.00,0:12:28.00,Default,,0000,0000,0000,,and each iteration through the loop body does a test against the I of the size to make sure that we're in
Dialogue: 0,0:12:28.00,0:12:29.00,Default,,0000,0000,0000,,range, right?
Dialogue: 0,0:12:29.00,0:12:31.00,Default,,0000,0000,0000,,Does this addition into the sum
Dialogue: 0,0:12:31.00,0:12:33.00,Default,,0000,0000,0000,,and then increments I.
Dialogue: 0,0:12:33.00,0:12:36.00,Default,,0000,0000,0000,,So every iteration has kind of three statements that happen
Dialogue: 0,0:12:36.00,0:12:41.00,Default,,0000,0000,0000,,for every element in the vector. Zero, one, two, three, and whatnot.
Dialogue: 0,0:12:41.00,0:12:42.00,Default,,0000,0000,0000,,So what we get here is
Dialogue: 0,0:12:42.00,0:12:45.00,Default,,0000,0000,0000,,a little bit of constant work that's done no matter what
Dialogue: 0,0:12:45.00,0:12:49.00,Default,,0000,0000,0000,,and then another term that varies with the size of the input. If the vector has ten elements,
Dialogue: 0,0:12:49.00,0:12:50.00,Default,,0000,0000,0000,,right? We'll do
Dialogue: 0,0:12:50.00,0:12:52.00,Default,,0000,0000,0000,,30 steps worth of stuff inside the loop.
Dialogue: 0,0:12:52.00,0:12:55.00,Default,,0000,0000,0000,,If it has 100 elements we do
Dialogue: 0,0:12:55.00,0:12:56.00,Default,,0000,0000,0000,,300.
Dialogue: 0,0:12:56.00,0:12:57.00,Default,,0000,0000,0000,,In this case, right?
Dialogue: 0,0:12:57.00,0:13:05.00,Default,,0000,0000,0000,,For different inputs, right? We would expect the average to take a different amount of time.
Dialogue: 0,0:13:05.00,0:13:07.00,Default,,0000,0000,0000,,Yeah? If n, the vector size
Dialogue: 0,0:13:07.00,0:13:08.00,Default,,0000,0000,0000,,MP though we still initialize I?
Dialogue: 0,0:13:08.00,0:13:12.00,Default,,0000,0000,0000,,We still initialize I. So I was actually counted in here, right? The init I, right? That was in there.
Dialogue: 0,0:13:12.00,0:13:16.00,Default,,0000,0000,0000,,We actually have one more test though. We do a test and then we don't enter the loop body. So there's
Dialogue: 0,0:13:16.00,0:13:19.00,Default,,0000,0000,0000,,actually one little piece maybe we could say that there's actually like three n plus five. There's one additional
Dialogue: 0,0:13:19.00,0:13:20.00,Default,,0000,0000,0000,,test
Dialogue: 0,0:13:20.00,0:13:22.00,Default,,0000,0000,0000,,that doesn't enter into the loop body.
Dialogue: 0,0:13:22.00,0:13:23.00,Default,,0000,0000,0000,,We're gonna see that actually that
Dialogue: 0,0:13:23.00,0:13:27.00,Default,,0000,0000,0000,,we're gonna be a little bit fast and loose about some of the
Dialogue: 0,0:13:27.00,0:13:31.00,Default,,0000,0000,0000,,things that are in the noise in the end and look more at the big leading term, but you are right.
Dialogue: 0,0:13:31.00,0:13:36.00,Default,,0000,0000,0000,,There is one more test than there are alliterations on the loop. That last test that has to fail.
Dialogue: 0,0:13:36.00,0:13:38.00,Default,,0000,0000,0000,,The idea of being that, right? We have
Dialogue: 0,0:13:38.00,0:13:42.00,Default,,0000,0000,0000,,three statements per thing. A little bit of extra stuff tacked onto it if we double the size of
Dialogue: 0,0:13:42.00,0:13:47.00,Default,,0000,0000,0000,,the vectors. So if we compute the average of the vector that has 100 elements and it took us two seconds.
Dialogue: 0,0:13:47.00,0:13:50.00,Default,,0000,0000,0000,,If we put in a vector that's 200 elements
Dialogue: 0,0:13:50.00,0:13:51.00,Default,,0000,0000,0000,,long,
Dialogue: 0,0:13:51.00,0:13:53.00,Default,,0000,0000,0000,,we expect that it should about double, right?
Dialogue: 0,0:13:53.00,0:13:56.00,Default,,0000,0000,0000,,If it took two seconds to do this half-sized vector,
Dialogue: 0,0:13:56.00,0:14:00.00,Default,,0000,0000,0000,,then if we'd have to do a vector that's twice as long we expect it's gonna take about
Dialogue: 0,0:14:00.00,0:14:01.00,Default,,0000,0000,0000,,four seconds.
Dialogue: 0,0:14:01.00,0:14:04.00,Default,,0000,0000,0000,,And that prediction is actually at the heart of what we're looking at today.
Dialogue: 0,0:14:04.00,0:14:06.00,Default,,0000,0000,0000,,Is trying to get this idea of,
Dialogue: 0,0:14:06.00,0:14:10.00,Default,,0000,0000,0000,,well, if we know something about how it performs relative to its input
Dialogue: 0,0:14:10.00,0:14:14.00,Default,,0000,0000,0000,,can we describe if we were to change the size of that input to make the maze much bigger or to make the
Dialogue: 0,0:14:14.00,0:14:16.00,Default,,0000,0000,0000,,vector much smaller?
Dialogue: 0,0:14:16.00,0:14:19.00,Default,,0000,0000,0000,,What can we predict or estimate about
Dialogue: 0,0:14:19.00,0:14:28.00,Default,,0000,0000,0000,,how much time and memory will be used to solve the problem using this algorithm?
Dialogue: 0,0:14:28.00,0:14:33.00,Default,,0000,0000,0000,,So here is one that given a vector computes the min and the max of the vector and it does it
Dialogue: 0,0:14:33.00,0:14:34.00,Default,,0000,0000,0000,,with two loops, right?
Dialogue: 0,0:14:34.00,0:14:35.00,Default,,0000,0000,0000,,One
Dialogue: 0,0:14:35.00,0:14:40.00,Default,,0000,0000,0000,,loop that goes through and checks each element to see if it's greater than the max it seems
Dialogue: 0,0:14:40.00,0:14:40.00,Default,,0000,0000,0000,,so far
Dialogue: 0,0:14:40.00,0:14:42.00,Default,,0000,0000,0000,,and if so it updates the max.
Dialogue: 0,0:14:42.00,0:14:46.00,Default,,0000,0000,0000,,And similarly almost identical loop here at the bottom
Dialogue: 0,0:14:46.00,0:14:50.00,Default,,0000,0000,0000,,that then checks to see if any successive element is smaller than the min it's seen so far and it
Dialogue: 0,0:14:50.00,0:14:53.00,Default,,0000,0000,0000,,updates the min to that one. Okay.
Dialogue: 0,0:14:53.00,0:14:55.00,Default,,0000,0000,0000,,So a little bit of stuff that happens
Dialogue: 0,0:14:55.00,0:14:59.00,Default,,0000,0000,0000,,outside the loop, right? We init I two times. We init the min and the max,
Dialogue: 0,0:14:59.00,0:15:02.00,Default,,0000,0000,0000,,so we've got, like, four statements that happen outside.
Dialogue: 0,0:15:02.00,0:15:04.00,Default,,0000,0000,0000,,And then inside the loop, right? We've got a test and
Dialogue: 0,0:15:04.00,0:15:08.00,Default,,0000,0000,0000,,an assignment, a comparison, an increment,
Dialogue: 0,0:15:08.00,0:15:10.00,Default,,0000,0000,0000,,and we have two of those loops, right?
Dialogue: 0,0:15:10.00,0:15:12.00,Default,,0000,0000,0000,,And so we have a
Dialogue: 0,0:15:12.00,0:15:13.00,Default,,0000,0000,0000,,little bit of stuff outside the loops,
Dialogue: 0,0:15:13.00,0:15:17.00,Default,,0000,0000,0000,,about eight instructions worth that happens per every element. So we look at it once to
Dialogue: 0,0:15:17.00,0:15:21.00,Default,,0000,0000,0000,,see if it's greater than the max. We actually look at everything again, right? To see if it's the
Dialogue: 0,0:15:21.00,0:15:22.00,Default,,0000,0000,0000,,min.
Dialogue: 0,0:15:22.00,0:15:24.00,Default,,0000,0000,0000,,I'm gonna use this actually
Dialogue: 0,0:15:24.00,0:15:28.00,Default,,0000,0000,0000,,as written, right? You might think, well, I could make this better, right? I could make
Dialogue: 0,0:15:28.00,0:15:29.00,Default,,0000,0000,0000,,this better by
Dialogue: 0,0:15:29.00,0:15:34.00,Default,,0000,0000,0000,,doing these two things together, right? Inside that loop, right? So that while I'm looking at each element
Dialogue: 0,0:15:34.00,0:15:38.00,Default,,0000,0000,0000,,I can say, well, if it's the max or if it's the min, right?
Dialogue: 0,0:15:38.00,0:15:42.00,Default,,0000,0000,0000,,If I look at it just once I can actually kind of do both those comparisons inside
Dialogue: 0,0:15:42.00,0:15:43.00,Default,,0000,0000,0000,,the loop
Dialogue: 0,0:15:43.00,0:15:46.00,Default,,0000,0000,0000,,and what we're gonna see is that in terms of kind of this analysis
Dialogue: 0,0:15:46.00,0:15:48.00,Default,,0000,0000,0000,,that's really not gonna make any difference.
Dialogue: 0,0:15:48.00,0:15:52.00,Default,,0000,0000,0000,,That whether we do a loop over the vector once and then we go back and loop over it again or whether we do
Dialogue: 0,0:15:52.00,0:15:56.00,Default,,0000,0000,0000,,twice as much stuff to each element inside one
Dialogue: 0,0:15:56.00,0:15:58.00,Default,,0000,0000,0000,,loop, it's for the purposes of the analysis we're looking at
Dialogue: 0,0:15:58.00,0:16:01.00,Default,,0000,0000,0000,,it ends up coming down to the same things.
Dialogue: 0,0:16:01.00,0:16:04.00,Default,,0000,0000,0000,,Which is, yeah, there is something that depends on the size of the input directly.
Dialogue: 0,0:16:04.00,0:16:07.00,Default,,0000,0000,0000,,Which is to say that if it were
Dialogue: 0,0:16:07.00,0:16:12.00,Default,,0000,0000,0000,,it will increase linearly with the change in size.
Dialogue: 0,0:16:12.00,0:16:16.00,Default,,0000,0000,0000,,So I have these numbers, like, four statements for the Celsius to Fahrenheit. Three n plus
Dialogue: 0,0:16:16.00,0:16:18.00,Default,,0000,0000,0000,,four. Eight n plus four.
Dialogue: 0,0:16:18.00,0:16:19.00,Default,,0000,0000,0000,,
Dialogue: 0,0:16:19.00,0:16:23.00,Default,,0000,0000,0000,,These tell us a little bit about, well, will get extremes always take more time than average
Dialogue: 0,0:16:23.00,0:16:24.00,Default,,0000,0000,0000,,or C to F?
Dialogue: 0,0:16:24.00,0:16:25.00,Default,,0000,0000,0000,,
Dialogue: 0,0:16:25.00,0:16:28.00,Default,,0000,0000,0000,,That given the way those numbers look it looks like, well, if you plugged in the same value of n
Dialogue: 0,0:16:28.00,0:16:30.00,Default,,0000,0000,0000,,you'd have the same size vector.
Dialogue: 0,0:16:30.00,0:16:32.00,Default,,0000,0000,0000,,That it should take more time
Dialogue: 0,0:16:32.00,0:16:35.00,Default,,0000,0000,0000,,to compute get extremes versus compute the average.
Dialogue: 0,0:16:35.00,0:16:39.00,Default,,0000,0000,0000,,We're gonna discover that, actually, we're not gonna, actually, try to make that guarantee.
Dialogue: 0,0:16:39.00,0:16:44.00,Default,,0000,0000,0000,,That what we're ? we're not really so much interested in comparing two algorithms
Dialogue: 0,0:16:44.00,0:16:46.00,Default,,0000,0000,0000,,and their constant factors to decide
Dialogue: 0,0:16:46.00,0:16:50.00,Default,,0000,0000,0000,,which of these two that kind of look about the same might be a little bit faster. What we're gonna try and
Dialogue: 0,0:16:50.00,0:16:55.00,Default,,0000,0000,0000,,look at it is giving you kind of a rough idea of the class an algorithm fits in. What its growth
Dialogue: 0,0:16:55.00,0:16:56.00,Default,,0000,0000,0000,,term, the kind of
Dialogue: 0,0:16:56.00,0:17:00.00,Default,,0000,0000,0000,,prediction of its growth, is. In this case, both averaging get extremes in terms of
Dialogue: 0,0:17:00.00,0:17:05.00,Default,,0000,0000,0000,,growth, both have a leading term that depends on n with some other noise and a little bit
Dialogue: 0,0:17:05.00,0:17:06.00,Default,,0000,0000,0000,,of a constant thrown in the front.
Dialogue: 0,0:17:06.00,0:17:09.00,Default,,0000,0000,0000,,That means that both of them, right? We'd expect to grow linearly
Dialogue: 0,0:17:09.00,0:17:14.00,Default,,0000,0000,0000,,in a straight line based on the change in n. So if you doubled the size of the thing
Dialogue: 0,0:17:14.00,0:17:19.00,Default,,0000,0000,0000,,then average would take twice as long as it previously did. So should get extremes. But the
Dialogue: 0,0:17:19.00,0:17:23.00,Default,,0000,0000,0000,,data point for does average of a vector of 100 elements take the same amount of time
Dialogue: 0,0:17:23.00,0:17:26.00,Default,,0000,0000,0000,,as get extremes of 100 is not what we're looking at predicting,
Dialogue: 0,0:17:26.00,0:17:29.00,Default,,0000,0000,0000,,right? We're trying to just tell you things about average against itself
Dialogue: 0,0:17:29.00,0:17:31.00,Default,,0000,0000,0000,,over different ranges of inputs.
Dialogue: 0,0:17:31.00,0:17:36.00,Default,,0000,0000,0000,,So if we know that average takes two milliseconds for a 1,000 elements. If we double the
Dialogue: 0,0:17:36.00,0:17:40.00,Default,,0000,0000,0000,,size of that we expect it to take twice as long, four milliseconds. If we increase it by a factor
Dialogue: 0,0:17:40.00,0:17:45.00,Default,,0000,0000,0000,,of ten we expect to increase the time by a factor of ten, right? So it should go up to 20 milliseconds. Get
Dialogue: 0,0:17:45.00,0:17:45.00,Default,,0000,0000,0000,,extremes
Dialogue: 0,0:17:45.00,0:17:48.00,Default,,0000,0000,0000,,might take more or less for a particular element.
Dialogue: 0,0:17:48.00,0:17:50.00,Default,,0000,0000,0000,,We expect it probably will take more
Dialogue: 0,0:17:50.00,0:17:53.00,Default,,0000,0000,0000,,because it does a little bit more work per element, but
Dialogue: 0,0:17:53.00,0:17:54.00,Default,,0000,0000,0000,,
Dialogue: 0,0:17:54.00,0:18:01.00,Default,,0000,0000,0000,,we really want to time it to be confident about that rather than making any estimation here. So in
Dialogue: 0,0:18:01.00,0:18:04.00,Default,,0000,0000,0000,,terms of what's called big O notation
Dialogue: 0,0:18:04.00,0:18:05.00,Default,,0000,0000,0000,,we're gonna see that we're going to
Dialogue: 0,0:18:05.00,0:18:06.00,Default,,0000,0000,0000,,
Dialogue: 0,0:18:06.00,0:18:10.00,Default,,0000,0000,0000,,kind of take those statement counts and we're gonna summarize them.
Dialogue: 0,0:18:10.00,0:18:11.00,Default,,0000,0000,0000,,
Dialogue: 0,0:18:11.00,0:18:15.00,Default,,0000,0000,0000,,That we can do a little bit of niggling to figure out what those numbers are, but what we're
Dialogue: 0,0:18:15.00,0:18:16.00,Default,,0000,0000,0000,,gonna then
Dialogue: 0,0:18:16.00,0:18:16.00,Default,,0000,0000,0000,,
Dialogue: 0,0:18:16.00,0:18:22.00,Default,,0000,0000,0000,,do is take the leading term, the largest term with the largest coeff ? value of the input number,
Dialogue: 0,0:18:22.00,0:18:24.00,Default,,0000,0000,0000,,in this case n.
Dialogue: 0,0:18:24.00,0:18:26.00,Default,,0000,0000,0000,,Ignore any smaller terms
Dialogue: 0,0:18:26.00,0:18:28.00,Default,,0000,0000,0000,,and then drop all the constants,
Dialogue: 0,0:18:28.00,0:18:31.00,Default,,0000,0000,0000,,all the coefficients, right? If you know it takes n over 2,
Dialogue: 0,0:18:31.00,0:18:32.00,Default,,0000,0000,0000,,it's just gonna be n.
Dialogue: 0,0:18:32.00,0:18:34.00,Default,,0000,0000,0000,,If you know that it takes
Dialogue: 0,0:18:34.00,0:18:37.00,Default,,0000,0000,0000,,ten statements, then it's gonna just be constant if there's no term of n in there. If it
Dialogue: 0,0:18:37.00,0:18:43.00,Default,,0000,0000,0000,,takes 10n then it's still n. 10n and 2n and 25n and 1/15n
Dialogue: 0,0:18:43.00,0:18:44.00,Default,,0000,0000,0000,,all end up just being n.
Dialogue: 0,0:18:44.00,0:18:47.00,Default,,0000,0000,0000,,So we might have this idea that we've estimated the time
Dialogue: 0,0:18:47.00,0:18:51.00,Default,,0000,0000,0000,,using n and having those constants in. Well, when it comes time to describe it in terms of big
Dialogue: 0,0:18:51.00,0:18:52.00,Default,,0000,0000,0000,,O,
Dialogue: 0,0:18:52.00,0:18:54.00,Default,,0000,0000,0000,,we focus on
Dialogue: 0,0:18:54.00,0:18:55.00,Default,,0000,0000,0000,,what's the ?
Dialogue: 0,0:18:55.00,0:18:57.00,Default,,0000,0000,0000,,oh, that,
Dialogue: 0,0:18:57.00,0:19:00.00,Default,,0000,0000,0000,,the subscript got lost on that. And that just makes no sense as it is right there. I will fix it
Dialogue: 0,0:19:00.00,0:19:01.00,Default,,0000,0000,0000,,in a second.
Dialogue: 0,0:19:01.00,0:19:05.00,Default,,0000,0000,0000,,So the 3n plus 5, right? The leading term is n, the coefficient 3
Dialogue: 0,0:19:05.00,0:19:07.00,Default,,0000,0000,0000,,gets dropped. It's just linear.
Dialogue: 0,0:19:07.00,0:19:09.00,Default,,0000,0000,0000,,We expect that as we change the input
Dialogue: 0,0:19:09.00,0:19:13.00,Default,,0000,0000,0000,,the time will change linearly with that change.
Dialogue: 0,0:19:13.00,0:19:15.00,Default,,0000,0000,0000,,The 10n minus
Dialogue: 0,0:19:15.00,0:19:16.00,Default,,0000,0000,0000,,2,
Dialogue: 0,0:19:16.00,0:19:20.00,Default,,0000,0000,0000,,same class. O of n. Even though it didn't have kind of the same constants coming into it, right? It has the
Dialogue: 0,0:19:20.00,0:19:23.00,Default,,0000,0000,0000,,same growth pattern that they both are lines.
Dialogue: 0,0:19:23.00,0:19:26.00,Default,,0000,0000,0000,,The slope of them might be slightly different, but
Dialogue: 0,0:19:26.00,0:19:28.00,Default,,0000,0000,0000,,in terms of big O we're being
Dialogue: 0,0:19:28.00,0:19:31.00,Default,,0000,0000,0000,,pretty loose about what fits into this class.
Dialogue: 0,0:19:31.00,0:19:34.00,Default,,0000,0000,0000,,1/2n squared minus
Dialogue: 0,0:19:34.00,0:19:36.00,Default,,0000,0000,0000,,n, the leading term here is the n squared.
Dialogue: 0,0:19:36.00,0:19:40.00,Default,,0000,0000,0000,,The n, subtract it off. When n is small n squared and n are actually kind of in range
Dialogue: 0,0:19:40.00,0:19:41.00,Default,,0000,0000,0000,,of each other,
Dialogue: 0,0:19:41.00,0:19:45.00,Default,,0000,0000,0000,,but then what we're looking at is in the limit. As n gets very, very large, n gets
Dialogue: 0,0:19:45.00,0:19:49.00,Default,,0000,0000,0000,,to be 1,000, n gets to be ? n squared is a much bigger number, right? When
Dialogue: 0,0:19:49.00,0:19:52.00,Default,,0000,0000,0000,,n is a million
Dialogue: 0,0:19:52.00,0:19:56.00,Default,,0000,0000,0000,,then n itself was and so as we get to these larger points kind of out into the limit this
Dialogue: 0,0:19:56.00,0:20:00.00,Default,,0000,0000,0000,,term is the only one that matters and this is just a little bit of the noise attached to it.
Dialogue: 0,0:20:00.00,0:20:03.00,Default,,0000,0000,0000,,So that's why we're gonna summarize down to that.
Dialogue: 0,0:20:03.00,0:20:07.00,Default,,0000,0000,0000,,What this one is supposed to say, and it actually is incorrect here, it just should be two to the n and n
Dialogue: 0,0:20:07.00,0:20:12.00,Default,,0000,0000,0000,,to the third power, which summarizes to two to the n. Two to the n grows much, much more
Dialogue: 0,0:20:12.00,0:20:17.00,Default,,0000,0000,0000,,rapidly than n cubed does and so as n gets to be a very large number. Even a fairly small number,
Dialogue: 0,0:20:17.00,0:20:20.00,Default,,0000,0000,0000,,you know, two to the tenth, right? Is
Dialogue: 0,0:20:20.00,0:20:23.00,Default,,0000,0000,0000,,all ready 1,000. Two to the 20th is a million,
Dialogue: 0,0:20:23.00,0:20:24.00,Default,,0000,0000,0000,,which is
Dialogue: 0,0:20:24.00,0:20:28.00,Default,,0000,0000,0000,,much bigger than these guys over here. So as we get to the long run it
Dialogue: 0,0:20:28.00,0:20:31.00,Default,,0000,0000,0000,,must be much bigger. I'm gonna put
Dialogue: 0,0:20:31.00,0:20:38.00,Default,,0000,0000,0000,,a note to myself though to fix that before I put that on the web. It should be O to the 2n? Yeah. It should
Dialogue: 0,0:20:38.00,0:20:41.00,Default,,0000,0000,0000,,be O to the 2n. So that should be two to the
Dialogue: 0,0:20:41.00,0:20:43.00,Default,,0000,0000,0000,,n, n to the third, and my two
Dialogue: 0,0:20:43.00,0:20:46.00,Default,,0000,0000,0000,,to the n there. My subscripts got blasted out of that.
Dialogue: 0,0:20:46.00,0:20:47.00,Default,,0000,0000,0000,,And so we're trying to
Dialogue: 0,0:20:47.00,0:20:51.00,Default,,0000,0000,0000,,describe this growth curve, like, in the limit, right? We're avoiding the details when they don't matter and they don't
Dialogue: 0,0:20:51.00,0:20:53.00,Default,,0000,0000,0000,,matter when n gets big enough, right?
Dialogue: 0,0:20:53.00,0:20:55.00,Default,,0000,0000,0000,,That only the leading term,
Dialogue: 0,0:20:55.00,0:20:59.00,Default,,0000,0000,0000,,right? Is predicting without this other stuff kind of just ignoring it.
Dialogue: 0,0:20:59.00,0:21:01.00,Default,,0000,0000,0000,,So this is very sloppy math,
Dialogue: 0,0:21:01.00,0:21:05.00,Default,,0000,0000,0000,,right? So those of you who are more trained in the, sort of, mathematical sciences may find this
Dialogue: 0,0:21:05.00,0:21:09.00,Default,,0000,0000,0000,,a little bit alarming. Which is just how kind of fast and loose we're gonna be. The only way all these terms left and
Dialogue: 0,0:21:09.00,0:21:13.00,Default,,0000,0000,0000,,right just kind of summarizing down to, okay, here's this leading term and how it relates to n.
Dialogue: 0,0:21:13.00,0:21:14.00,Default,,0000,0000,0000,,Everything else, right?
Dialogue: 0,0:21:14.00,0:21:19.00,Default,,0000,0000,0000,,Totally uninteresting. We could have a function, for example, that did 1,000 conversions of Celsius to
Dialogue: 0,0:21:19.00,0:21:20.00,Default,,0000,0000,0000,,Fahrenheit,
Dialogue: 0,0:21:20.00,0:21:24.00,Default,,0000,0000,0000,,but if every time you call it does 1,000 conversions that means no matter
Dialogue: 0,0:21:24.00,0:21:28.00,Default,,0000,0000,0000,,what input you give to it doesn't change. That's considered O of one or a constant
Dialogue: 0,0:21:28.00,0:21:31.00,Default,,0000,0000,0000,,time. Similarly, right? For doing average. If we did an average that somehow
Dialogue: 0,0:21:31.00,0:21:32.00,Default,,0000,0000,0000,,
Dialogue: 0,0:21:32.00,0:21:36.00,Default,,0000,0000,0000,,operated over the vector one time and another one that did it ten times or 20 times
Dialogue: 0,0:21:36.00,0:21:39.00,Default,,0000,0000,0000,,looked at each element 20 times, right?
Dialogue: 0,0:21:39.00,0:21:42.00,Default,,0000,0000,0000,,They would still both be O of n. Whatever time they took,
Dialogue: 0,0:21:42.00,0:21:47.00,Default,,0000,0000,0000,,right? On a vector of a certain length we double that length. We'd expect to double the time.
Dialogue: 0,0:21:47.00,0:21:50.00,Default,,0000,0000,0000,,More formally, right? In terms of what the math really means
Dialogue: 0,0:21:50.00,0:21:55.00,Default,,0000,0000,0000,,is that we say that O of F of n, so O, if it's big O of some function,
Dialogue: 0,0:21:55.00,0:22:00.00,Default,,0000,0000,0000,,it describes an upper bound on the time required. Meaning that
Dialogue: 0,0:22:00.00,0:22:02.00,Default,,0000,0000,0000,,for sufficiently large
Dialogue: 0,0:22:02.00,0:22:03.00,Default,,0000,0000,0000,,values of n
Dialogue: 0,0:22:03.00,0:22:06.00,Default,,0000,0000,0000,,and some constant C that we get to pick that
Dialogue: 0,0:22:06.00,0:22:10.00,Default,,0000,0000,0000,,that would bound the curves. So if you imagine what the real curve looks like, it grows and
Dialogue: 0,0:22:10.00,0:22:13.00,Default,,0000,0000,0000,,maybe it flattens out or maybe it goes up very sharply.
Dialogue: 0,0:22:13.00,0:22:17.00,Default,,0000,0000,0000,,That what C of F of n gives you kind of some upper bound of that. A curve that stays above it
Dialogue: 0,0:22:17.00,0:22:20.00,Default,,0000,0000,0000,,at ? for at some point of n and the limit, right?
Dialogue: 0,0:22:20.00,0:22:22.00,Default,,0000,0000,0000,,Will dominate it from there to affinity.
Dialogue: 0,0:22:22.00,0:22:26.00,Default,,0000,0000,0000,,So describing kind of where it's gonna hit at that upper bound gives us some measure
Dialogue: 0,0:22:26.00,0:22:32.00,Default,,0000,0000,0000,,of what's going on. Okay.
Dialogue: 0,0:22:32.00,0:22:34.00,Default,,0000,0000,0000,,So we can use this to predict times.
Dialogue: 0,0:22:34.00,0:22:37.00,Default,,0000,0000,0000,,That's probably what's most valuable to us about it is knowing that
Dialogue: 0,0:22:37.00,0:22:41.00,Default,,0000,0000,0000,,I have an n ? a linear algorithm. So an O of n algorithm we'll call linear.
Dialogue: 0,0:22:41.00,0:22:46.00,Default,,0000,0000,0000,,And n squared algorithm I'll call quadratic. N to the third I'll called cubic, right?
Dialogue: 0,0:22:46.00,0:22:50.00,Default,,0000,0000,0000,,That's gonna tell us that those curves, right? You know what a line looks like. Well, you know what a parabola
Dialogue: 0,0:22:50.00,0:22:54.00,Default,,0000,0000,0000,,looks like coming out of an n squared where it's growing much more sharply and early kind of
Dialogue: 0,0:22:54.00,0:22:57.00,Default,,0000,0000,0000,,making the decision. So
Dialogue: 0,0:22:57.00,0:22:58.00,Default,,0000,0000,0000,,it might be, right? That
Dialogue: 0,0:22:58.00,0:23:02.00,Default,,0000,0000,0000,,if I know that it takes three seconds to do something for 5,000 elements then I have a linear
Dialogue: 0,0:23:02.00,0:23:03.00,Default,,0000,0000,0000,,algorithm.
Dialogue: 0,0:23:03.00,0:23:07.00,Default,,0000,0000,0000,,That 10,000 elements, right? Should take twice as long. 20,000 should take another,
Dialogue: 0,0:23:07.00,0:23:10.00,Default,,0000,0000,0000,,a factor of two on that. So 12 seconds worth. That
Dialogue: 0,0:23:10.00,0:23:12.00,Default,,0000,0000,0000,,I may have an n squared algorithm.
Dialogue: 0,0:23:12.00,0:23:17.00,Default,,0000,0000,0000,,So one that I expect to actually perform more poorly in the long run, right? This n squared
Dialogue: 0,0:23:17.00,0:23:21.00,Default,,0000,0000,0000,,versus n tells you that it's gonna more sharply grow. That
Dialogue: 0,0:23:21.00,0:23:25.00,Default,,0000,0000,0000,,for some values of n in simply 5,000 is the case where the n squared algorithm
Dialogue: 0,0:23:25.00,0:23:26.00,Default,,0000,0000,0000,,actually outperforms
Dialogue: 0,0:23:26.00,0:23:31.00,Default,,0000,0000,0000,,it in a small case. That's not uncommon actually.
Dialogue: 0,0:23:31.00,0:23:32.00,Default,,0000,0000,0000,,But, right?
Dialogue: 0,0:23:32.00,0:23:36.00,Default,,0000,0000,0000,,As it grows, right? As I get to larger and larger values of n
Dialogue: 0,0:23:36.00,0:23:40.00,Default,,0000,0000,0000,,the fact that it is going by factor of four, right? The square of
Dialogue: 0,0:23:40.00,0:23:40.00,Default,,0000,0000,0000,,the doubling
Dialogue: 0,0:23:40.00,0:23:45.00,Default,,0000,0000,0000,,as opposed to linear means it's gonna quickly take off. And so I take my 5,000 elements that
Dialogue: 0,0:23:45.00,0:23:47.00,Default,,0000,0000,0000,,took two and a half seconds.
Dialogue: 0,0:23:47.00,0:23:50.00,Default,,0000,0000,0000,,I put an input that's twice as large into it.
Dialogue: 0,0:23:50.00,0:23:52.00,Default,,0000,0000,0000,,It's gonna take a factor of four,
Dialogue: 0,0:23:52.00,0:23:53.00,Default,,0000,0000,0000,,right? From there.
Dialogue: 0,0:23:53.00,0:23:56.00,Default,,0000,0000,0000,,And if I go from 10,000 to 20,000 another factor of four is gonna bring that up
Dialogue: 0,0:23:56.00,0:23:57.00,Default,,0000,0000,0000,,to
Dialogue: 0,0:23:57.00,0:23:58.00,Default,,0000,0000,0000,,40 seconds or so
Dialogue: 0,0:23:58.00,0:24:02.00,Default,,0000,0000,0000,,compared to my more modestly growing linear algorithm there.
Dialogue: 0,0:24:02.00,0:24:07.00,Default,,0000,0000,0000,,So if I was facing some task, right? Where I had an option between a linear algorithm and a
Dialogue: 0,0:24:07.00,0:24:09.00,Default,,0000,0000,0000,,quadratic algorithm
Dialogue: 0,0:24:09.00,0:24:12.00,Default,,0000,0000,0000,,it's telling me that in the long run the quadratic algorithm
Dialogue: 0,0:24:12.00,0:24:15.00,Default,,0000,0000,0000,,for sufficiently large inputs, right?
Dialogue: 0,0:24:15.00,0:24:18.00,Default,,0000,0000,0000,,Is going to bog down in a way that the linear one
Dialogue: 0,0:24:18.00,0:24:26.00,Default,,0000,0000,0000,,will be our kind of strong performer in the larger cases.
Dialogue: 0,0:24:26.00,0:24:27.00,Default,,0000,0000,0000,,So some algorithms
Dialogue: 0,0:24:27.00,0:24:30.00,Default,,0000,0000,0000,,actually have a variable
Dialogue: 0,0:24:30.00,0:24:32.00,Default,,0000,0000,0000,,run time expectation
Dialogue: 0,0:24:32.00,0:24:34.00,Default,,0000,0000,0000,,that you cannot say
Dialogue: 0,0:24:34.00,0:24:35.00,Default,,0000,0000,0000,,
Dialogue: 0,0:24:35.00,0:24:39.00,Default,,0000,0000,0000,,with all assuredness how much time it will take because actually depending on the input and
Dialogue: 0,0:24:39.00,0:24:43.00,Default,,0000,0000,0000,,the characteristics of the input it may do more or less work. So average looks at every
Dialogue: 0,0:24:43.00,0:24:47.00,Default,,0000,0000,0000,,element in the vector and sums them all up and does the division. It doesn't matter what elements
Dialogue: 0,0:24:47.00,0:24:48.00,Default,,0000,0000,0000,,are in there.
Dialogue: 0,0:24:48.00,0:24:50.00,Default,,0000,0000,0000,,It's very reliable in that sense.
Dialogue: 0,0:24:50.00,0:24:54.00,Default,,0000,0000,0000,,Something like search. So this is a linear search function that given a vector of names
Dialogue: 0,0:24:54.00,0:24:56.00,Default,,0000,0000,0000,,and a particular key
Dialogue: 0,0:24:56.00,0:24:58.00,Default,,0000,0000,0000,,just walks the vector looking for a match. If
Dialogue: 0,0:24:58.00,0:25:02.00,Default,,0000,0000,0000,,it finds it, it returns true. If it exhaustively searched the whole thing and didn't find it, it returns
Dialogue: 0,0:25:02.00,0:25:04.00,Default,,0000,0000,0000,,false. Okay.
Dialogue: 0,0:25:04.00,0:25:06.00,Default,,0000,0000,0000,,So we've got what looks like
Dialogue: 0,0:25:06.00,0:25:08.00,Default,,0000,0000,0000,,an O of n loop
Dialogue: 0,0:25:08.00,0:25:09.00,Default,,0000,0000,0000,,that we'll look at the things,
Dialogue: 0,0:25:09.00,0:25:11.00,Default,,0000,0000,0000,,but there are some cases, right?
Dialogue: 0,0:25:11.00,0:25:15.00,Default,,0000,0000,0000,,Where it just doesn't do very much work at all. For example, if it finds the key in the very
Dialogue: 0,0:25:15.00,0:25:16.00,Default,,0000,0000,0000,,first spot,
Dialogue: 0,0:25:16.00,0:25:18.00,Default,,0000,0000,0000,,right? If I'm looking for
Dialogue: 0,0:25:18.00,0:25:22.00,Default,,0000,0000,0000,,Bob and Bob is the first thing in there, then I immediately return true and I do no more work.
Dialogue: 0,0:25:22.00,0:25:26.00,Default,,0000,0000,0000,,And so it doesn't matter whether Bob was followed by a million more names or ten more names, right?
Dialogue: 0,0:25:26.00,0:25:31.00,Default,,0000,0000,0000,,That, in fact, it is a constant time operation to just access that first element and return it.
Dialogue: 0,0:25:31.00,0:25:34.00,Default,,0000,0000,0000,,Similarly for other things that are close to the front. It looks at a few of them and
Dialogue: 0,0:25:34.00,0:25:35.00,Default,,0000,0000,0000,,it's done.
Dialogue: 0,0:25:35.00,0:25:39.00,Default,,0000,0000,0000,,And so we would call those the best case of the algorithm. So we can divide this into things. It's like,
Dialogue: 0,0:25:39.00,0:25:41.00,Default,,0000,0000,0000,,well, what of the
Dialogue: 0,0:25:41.00,0:25:45.00,Default,,0000,0000,0000,,best case input, right? What can we expect out of the performance? Well, the best-case input would
Dialogue: 0,0:25:45.00,0:25:46.00,Default,,0000,0000,0000,,be
Dialogue: 0,0:25:46.00,0:25:48.00,Default,,0000,0000,0000,,it's found in the first few members.
Dialogue: 0,0:25:48.00,0:25:49.00,Default,,0000,0000,0000,,In which case
Dialogue: 0,0:25:49.00,0:25:52.00,Default,,0000,0000,0000,,it's an O of one algorithm for those situations.
Dialogue: 0,0:25:52.00,0:25:56.00,Default,,0000,0000,0000,,That's not often very interesting to say, well, here's a particular input that causes it to immediately
Dialogue: 0,0:25:56.00,0:25:58.00,Default,,0000,0000,0000,,be able to calculate something in return.
Dialogue: 0,0:25:58.00,0:26:02.00,Default,,0000,0000,0000,,Yeah. Not so interesting. So it's worth knowing that such a thing exists, but it turns out it's
Dialogue: 0,0:26:02.00,0:26:03.00,Default,,0000,0000,0000,,not
Dialogue: 0,0:26:03.00,0:26:04.00,Default,,0000,0000,0000,,
Dialogue: 0,0:26:04.00,0:26:08.00,Default,,0000,0000,0000,,likely to tell us a lot about the general performance of this algorithm.
Dialogue: 0,0:26:08.00,0:26:11.00,Default,,0000,0000,0000,,If it's in the middle or it's in the last slot, right? We're
Dialogue: 0,0:26:11.00,0:26:15.00,Default,,0000,0000,0000,,gonna be looking at a lot of the elements to decide that it's there or not.
Dialogue: 0,0:26:15.00,0:26:18.00,Default,,0000,0000,0000,,In the absolute worst case,
Dialogue: 0,0:26:18.00,0:26:21.00,Default,,0000,0000,0000,,right? So what's the input that causes it to do the most amount of work
Dialogue: 0,0:26:21.00,0:26:23.00,Default,,0000,0000,0000,,is the one where it doesn't find it at all. Where
Dialogue: 0,0:26:23.00,0:26:28.00,Default,,0000,0000,0000,,it looks at every single element, never finding the match, and then comes out and returns that false.
Dialogue: 0,0:26:28.00,0:26:31.00,Default,,0000,0000,0000,,And the worst case, in this case, is a fairly likely thing to happen, right?
Dialogue: 0,0:26:31.00,0:26:34.00,Default,,0000,0000,0000,,We're searching because we happen to believe it might not be there
Dialogue: 0,0:26:34.00,0:26:35.00,Default,,0000,0000,0000,,and that gives us this upper bound on
Dialogue: 0,0:26:35.00,0:26:40.00,Default,,0000,0000,0000,,how bad it gets. So in the worst case it looks at everything and it is definitely O of
Dialogue: 0,0:26:40.00,0:26:43.00,Default,,0000,0000,0000,,n. So we have this kind of constant best case,
Dialogue: 0,0:26:43.00,0:26:44.00,Default,,0000,0000,0000,,an O of n worst case,
Dialogue: 0,0:26:44.00,0:26:47.00,Default,,0000,0000,0000,,and then our average case is gonna be somewhere in the middle there.
Dialogue: 0,0:26:47.00,0:26:52.00,Default,,0000,0000,0000,,This actually is a little bit harder to predict or to compute precisely in most
Dialogue: 0,0:26:52.00,0:26:57.00,Default,,0000,0000,0000,,situations because you have to know things about, well, what are the likely range of inputs?
Dialogue: 0,0:26:57.00,0:27:01.00,Default,,0000,0000,0000,,So typically the definition is that it's averaged over all the possible inputs.
Dialogue: 0,0:27:01.00,0:27:06.00,Default,,0000,0000,0000,,Well, given the search it's pretty hard to say what are all the possible inputs for it? It's
Dialogue: 0,0:27:06.00,0:27:10.00,Default,,0000,0000,0000,,like you can make some assumptions, like, well, all in ? all permutations of the list
Dialogue: 0,0:27:10.00,0:27:12.00,Default,,0000,0000,0000,,are equally likely
Dialogue: 0,0:27:12.00,0:27:17.00,Default,,0000,0000,0000,,and the name is in the list about half the time, let's say. You can just ? you have
Dialogue: 0,0:27:17.00,0:27:22.00,Default,,0000,0000,0000,,to make up some parameters that describe what you believe to be the likely inputs
Dialogue: 0,0:27:22.00,0:27:26.00,Default,,0000,0000,0000,,and then you can say, well, if it were in the list, if it's equally likely to be
Dialogue: 0,0:27:26.00,0:27:27.00,Default,,0000,0000,0000,,in the front as in the back,
Dialogue: 0,0:27:27.00,0:27:30.00,Default,,0000,0000,0000,,then on average it's gonna look at n over two.
Dialogue: 0,0:27:30.00,0:27:35.00,Default,,0000,0000,0000,,It's just as likely to be in all the front slots. So, let's say, if you were gonna call it n times
Dialogue: 0,0:27:35.00,0:27:36.00,Default,,0000,0000,0000,,and
Dialogue: 0,0:27:36.00,0:27:40.00,Default,,0000,0000,0000,,the name you were looking for was going to be in each individual slot exactly one
Dialogue: 0,0:27:40.00,0:27:41.00,Default,,0000,0000,0000,,time, then the total random
Dialogue: 0,0:27:41.00,0:27:43.00,Default,,0000,0000,0000,,perfect permutation case.
Dialogue: 0,0:27:43.00,0:27:46.00,Default,,0000,0000,0000,,So then it would have looked at n over two of them. Sometimes it looked at one, sometimes it looked
Dialogue: 0,0:27:46.00,0:27:48.00,Default,,0000,0000,0000,,at n minus one, sometimes as it looked at n
Dialogue: 0,0:27:48.00,0:27:52.00,Default,,0000,0000,0000,,over two, sometimes n over two plus one, and whatnot. That over all of them it looked at
Dialogue: 0,0:27:52.00,0:27:53.00,Default,,0000,0000,0000,,about half.
Dialogue: 0,0:27:53.00,0:27:57.00,Default,,0000,0000,0000,,And then if there was another set of calls to search for it, right? Where it never found it, it would be looking
Dialogue: 0,0:27:57.00,0:27:58.00,Default,,0000,0000,0000,,at
Dialogue: 0,0:27:58.00,0:27:59.00,Default,,0000,0000,0000,,n, right? And so
Dialogue: 0,0:27:59.00,0:28:02.00,Default,,0000,0000,0000,,you can say, well, sometimes we look at n over two, sometimes we look at n.
Dialogue: 0,0:28:02.00,0:28:04.00,Default,,0000,0000,0000,,On average we're looking at about three-quarters of them, right?
Dialogue: 0,0:28:04.00,0:28:07.00,Default,,0000,0000,0000,,In big O, since we get to be a bit sloppy here,
Dialogue: 0,0:28:07.00,0:28:10.00,Default,,0000,0000,0000,,we can say, well, this all just boils down to being linear. That O
Dialogue: 0,0:28:10.00,0:28:14.00,Default,,0000,0000,0000,,of n still described to the growth in the average case,
Dialogue: 0,0:28:14.00,0:28:16.00,Default,,0000,0000,0000,,
Dialogue: 0,0:28:16.00,0:28:20.00,Default,,0000,0000,0000,,which is the same number we got for the worst case. So this is a little
Dialogue: 0,0:28:20.00,0:28:23.00,Default,,0000,0000,0000,,bit tricky, but this is actually the one that's probably the most interesting, right? Which is just in
Dialogue: 0,0:28:23.00,0:28:28.00,Default,,0000,0000,0000,,normal practice, how is this thing gonna behave?
Dialogue: 0,0:28:28.00,0:28:31.00,Default,,0000,0000,0000,,So the last little thing I need to
Dialogue: 0,0:28:31.00,0:28:34.00,Default,,0000,0000,0000,,complete before we can go on and start applying this to do something interesting, is to talk
Dialogue: 0,0:28:34.00,0:28:39.00,Default,,0000,0000,0000,,a little bit about how we do recursive algorithms because they're a little bit trickier than the standard iteration
Dialogue: 0,0:28:39.00,0:28:40.00,Default,,0000,0000,0000,,and counting.
Dialogue: 0,0:28:40.00,0:28:44.00,Default,,0000,0000,0000,,So the counting statements are kind of saying, oh, I've got this loop followed by this loop and this thing
Dialogue: 0,0:28:44.00,0:28:45.00,Default,,0000,0000,0000,,happening, right?
Dialogue: 0,0:28:45.00,0:28:49.00,Default,,0000,0000,0000,,Will get you through the simple cases. Well, what do we do when we have a recursive algorithm, right? Well,
Dialogue: 0,0:28:49.00,0:28:53.00,Default,,0000,0000,0000,,we're trying to compute the time spent in solving something
Dialogue: 0,0:28:53.00,0:28:57.00,Default,,0000,0000,0000,,that, in affect, is making a call to the same algorithm and so we're gonna likely have
Dialogue: 0,0:28:57.00,0:29:00.00,Default,,0000,0000,0000,,some recursive definition we need to work through.
Dialogue: 0,0:29:00.00,0:29:02.00,Default,,0000,0000,0000,,So this is the factorial function.
Dialogue: 0,0:29:02.00,0:29:06.00,Default,,0000,0000,0000,,If n equals zero, return one, otherwise return n times the factorial n minus one.
Dialogue: 0,0:29:06.00,0:29:08.00,Default,,0000,0000,0000,,We're interested in doing kind of the statement counts or kind
Dialogue: 0,0:29:08.00,0:29:11.00,Default,,0000,0000,0000,,of summarizing the time for an input
Dialogue: 0,0:29:11.00,0:29:13.00,Default,,0000,0000,0000,,whose value is n.
Dialogue: 0,0:29:13.00,0:29:17.00,Default,,0000,0000,0000,,And so what we write down is what's called a recurrence relation
Dialogue: 0,0:29:17.00,0:29:20.00,Default,,0000,0000,0000,,that largely matches the code in terms of saying
Dialogue: 0,0:29:20.00,0:29:21.00,Default,,0000,0000,0000,,how much work is done
Dialogue: 0,0:29:21.00,0:29:25.00,Default,,0000,0000,0000,,in the base case? In the different cases that are being handled? Typically there is a base case
Dialogue: 0,0:29:25.00,0:29:29.00,Default,,0000,0000,0000,,or two where you say, well, if it's in these cases, right? We do these easy things.
Dialogue: 0,0:29:29.00,0:29:31.00,Default,,0000,0000,0000,,So if n is exactly zero
Dialogue: 0,0:29:31.00,0:29:36.00,Default,,0000,0000,0000,,then we do O of one worth of work, right? We do a little bit of constant work here. We
Dialogue: 0,0:29:36.00,0:29:38.00,Default,,0000,0000,0000,,do a comparison and a return.
Dialogue: 0,0:29:38.00,0:29:42.00,Default,,0000,0000,0000,,In the otherwise case when it is not zero,
Dialogue: 0,0:29:42.00,0:29:46.00,Default,,0000,0000,0000,,then we do a little bit of work. In this case, a return, a multiply, a little bit of constant work
Dialogue: 0,0:29:46.00,0:29:48.00,Default,,0000,0000,0000,,plus whatever time it takes to compute
Dialogue: 0,0:29:48.00,0:29:51.00,Default,,0000,0000,0000,,the factorial of n minus one.
Dialogue: 0,0:29:51.00,0:29:54.00,Default,,0000,0000,0000,,So we have T of n defined in terms of
Dialogue: 0,0:29:54.00,0:29:58.00,Default,,0000,0000,0000,,T of n of something else, right? Which is exactly what we'd expect in a recursive function.
Dialogue: 0,0:29:58.00,0:30:00.00,Default,,0000,0000,0000,,This is called a recurrence relation, so that
Dialogue: 0,0:30:00.00,0:30:03.00,Default,,0000,0000,0000,,solving for T of
Dialogue: 0,0:30:03.00,0:30:05.00,Default,,0000,0000,0000,,n means working with
Dialogue: 0,0:30:05.00,0:30:09.00,Default,,0000,0000,0000,,a side that refers back to that same T, but on a smaller version of the problem
Dialogue: 0,0:30:09.00,0:30:15.00,Default,,0000,0000,0000,,in n over two and n minus one. Some other variation of that recursive call.
Dialogue: 0,0:30:15.00,0:30:19.00,Default,,0000,0000,0000,,So let me show you how we make that go into closed form.
Dialogue: 0,0:30:19.00,0:30:23.00,Default,,0000,0000,0000,,The idea ? and actually I'm just gonna do this on the board because I think it's easier if I just write what's
Dialogue: 0,0:30:23.00,0:30:26.00,Default,,0000,0000,0000,,going on and you can watch me develop it.
Dialogue: 0,0:30:26.00,0:30:28.00,Default,,0000,0000,0000,,So I have this recurrence relation.
Dialogue: 0,0:30:28.00,0:30:29.00,Default,,0000,0000,0000,,Even
Dialogue: 0,0:30:29.00,0:30:31.00,Default,,0000,0000,0000,,equals one if
Dialogue: 0,0:30:31.00,0:30:33.00,Default,,0000,0000,0000,,n equals zero
Dialogue: 0,0:30:33.00,0:30:39.00,Default,,0000,0000,0000,,and then it's one plus T of n minus one otherwise. So I'm trying to
Dialogue: 0,0:30:39.00,0:30:41.00,Default,,0000,0000,0000,,solve for T of n
Dialogue: 0,0:30:41.00,0:30:45.00,Default,,0000,0000,0000,,into a closed form. So I'm gonna start with
Dialogue: 0,0:30:45.00,0:30:50.00,Default,,0000,0000,0000,,it's non-recur ? the non-base case form. So the recursive step. And then what I'm gonna do
Dialogue: 0,0:30:50.00,0:30:54.00,Default,,0000,0000,0000,,is I'm actually just gonna reply repeated substitution
Dialogue: 0,0:30:54.00,0:30:56.00,Default,,0000,0000,0000,,to take this term and expand it out.
Dialogue: 0,0:30:56.00,0:31:00.00,Default,,0000,0000,0000,,So I know it's one plus whatever it takes to do T of n minus one.
Dialogue: 0,0:31:00.00,0:31:02.00,Default,,0000,0000,0000,,So if I go back over here and I say, well, T of
Dialogue: 0,0:31:02.00,0:31:03.00,Default,,0000,0000,0000,,n minus one
Dialogue: 0,0:31:03.00,0:31:04.00,Default,,0000,0000,0000,,must be
Dialogue: 0,0:31:04.00,0:31:06.00,Default,,0000,0000,0000,,
Dialogue: 0,0:31:06.00,0:31:08.00,Default,,0000,0000,0000,,one if n minus one equals zero or it's
Dialogue: 0,0:31:08.00,0:31:11.00,Default,,0000,0000,0000,,one plus T of n minus two. So
Dialogue: 0,0:31:11.00,0:31:13.00,Default,,0000,0000,0000,,kind
Dialogue: 0,0:31:13.00,0:31:17.00,Default,,0000,0000,0000,,of plugging it into the original formula and getting the expansion one layer in.
Dialogue: 0,0:31:17.00,0:31:19.00,Default,,0000,0000,0000,,So I can say, well, this is
Dialogue: 0,0:31:19.00,0:31:20.00,Default,,0000,0000,0000,,one plus
Dialogue: 0,0:31:20.00,0:31:23.00,Default,,0000,0000,0000,,one plus T of n minus two. And if I apply
Dialogue: 0,0:31:23.00,0:31:25.00,Default,,0000,0000,0000,,that again,
Dialogue: 0,0:31:25.00,0:31:27.00,Default,,0000,0000,0000,,right? I should get another term of
Dialogue: 0,0:31:27.00,0:31:35.00,Default,,0000,0000,0000,,
Dialogue: 0,0:31:35.00,0:31:44.00,Default,,0000,0000,0000,,one. So after I have done this I times
Dialogue: 0,0:31:44.00,0:31:46.00,Default,,0000,0000,0000,,then I will have a bunch of ones added up together
Dialogue: 0,0:31:46.00,0:31:49.00,Default,,0000,0000,0000,,and I will have subtracted an I from T
Dialogue: 0,0:31:49.00,0:31:51.00,Default,,0000,0000,0000,,
Dialogue: 0,0:31:51.00,0:31:52.00,Default,,0000,0000,0000,,down to some term. So I'm just gonna ? each of
Dialogue: 0,0:31:52.00,0:31:54.00,Default,,0000,0000,0000,,these represents kind of like
Dialogue: 0,0:31:54.00,0:31:57.00,Default,,0000,0000,0000,,this is a little bit of work from the n, which does the n minus one, which brings the quality of my two.
Dialogue: 0,0:31:57.00,0:32:01.00,Default,,0000,0000,0000,,So each of the cul's kind of in the stack frame has a little bit of a
Dialogue: 0,0:32:01.00,0:32:03.00,Default,,0000,0000,0000,,contribution to add to the whole thing
Dialogue: 0,0:32:03.00,0:32:04.00,Default,,0000,0000,0000,,and then what we're looking at is
Dialogue: 0,0:32:04.00,0:32:08.00,Default,,0000,0000,0000,,how many times do we have to do that expansion and substitution, right?
Dialogue: 0,0:32:08.00,0:32:10.00,Default,,0000,0000,0000,,Before we hit this base case, right?
Dialogue: 0,0:32:10.00,0:32:12.00,Default,,0000,0000,0000,,Where T of n exactly equals one.
Dialogue: 0,0:32:12.00,0:32:15.00,Default,,0000,0000,0000,,So we're looking for the case where n
Dialogue: 0,0:32:15.00,0:32:18.00,Default,,0000,0000,0000,,actually it's n equals zero. So
Dialogue: 0,0:32:18.00,0:32:20.00,Default,,0000,0000,0000,,where n
Dialogue: 0,0:32:20.00,0:32:23.00,Default,,0000,0000,0000,,so I want to do this until n minus I equals equals zero.
Dialogue: 0,0:32:23.00,0:32:27.00,Default,,0000,0000,0000,,Okay. So I need to have done this I times where I is n.
Dialogue: 0,0:32:27.00,0:32:32.00,Default,,0000,0000,0000,,So if I say I set I equaled to
Dialogue: 0,0:32:32.00,0:32:34.00,Default,,0000,0000,0000,,n, then I'll have one plus one plus one
Dialogue: 0,0:32:34.00,0:32:37.00,Default,,0000,0000,0000,,n times,
Dialogue: 0,0:32:37.00,0:32:39.00,Default,,0000,0000,0000,,and then I have plus
Dialogue: 0,0:32:39.00,0:32:41.00,Default,,0000,0000,0000,,T of the n minus n over here,
Dialogue: 0,0:32:41.00,0:32:43.00,Default,,0000,0000,0000,,which is my T subzero.
Dialogue: 0,0:32:43.00,0:32:47.00,Default,,0000,0000,0000,,T subzero, right? Immediately plugs into that base case and says, well, there's just one more thing
Dialogue: 0,0:32:47.00,0:32:48.00,Default,,0000,0000,0000,,to do when you get to that
Dialogue: 0,0:32:48.00,0:32:52.00,Default,,0000,0000,0000,,and so what I basically have here is n plus one.
Dialogue: 0,0:32:52.00,0:33:00.00,Default,,0000,0000,0000,,So n multiplications plus one little tack on for the base case, which in terms of big O
Dialogue: 0,0:33:00.00,0:33:03.00,Default,,0000,0000,0000,,is just linear. A little bit
Dialogue: 0,0:33:03.00,0:33:05.00,Default,,0000,0000,0000,,of extra work in the noise there, but
Dialogue: 0,0:33:05.00,0:33:10.00,Default,,0000,0000,0000,,that means that kind of as it seems more predictable, right? That factorial over particular input,
Dialogue: 0,0:33:10.00,0:33:11.00,Default,,0000,0000,0000,,right? Is linear
Dialogue: 0,0:33:11.00,0:33:17.00,Default,,0000,0000,0000,,in the number you ask to compute the factorial. The factorial of ten takes ten
Dialogue: 0,0:33:17.00,0:33:20.00,Default,,0000,0000,0000,,multiplications, right? The factorial of 20 takes 20 multiplications.
Dialogue: 0,0:33:20.00,0:33:24.00,Default,,0000,0000,0000,,So if you change the size of your input, right? You double it; it should take twice as long. However much
Dialogue: 0,0:33:24.00,0:33:28.00,Default,,0000,0000,0000,,time it cost you to compute the factorial of ten is gonna take twice as much time to compute
Dialogue: 0,0:33:28.00,0:33:32.00,Default,,0000,0000,0000,,the factorial of 20. Okay. That kind of
Dialogue: 0,0:33:32.00,0:33:36.00,Default,,0000,0000,0000,,makes sense, but it's good to know kind of how I can do this math,
Dialogue: 0,0:33:36.00,0:33:38.00,Default,,0000,0000,0000,,right? To work this out, right? So this idea of
Dialogue: 0,0:33:38.00,0:33:45.00,Default,,0000,0000,0000,,taking the term, repeatedly substituting and expanding, generalizing my pattern, and say, well, after I substitutions
Dialogue: 0,0:33:45.00,0:33:46.00,Default,,0000,0000,0000,,worth where am I at?
Dialogue: 0,0:33:46.00,0:33:48.00,Default,,0000,0000,0000,,And these correspond and kind of thinking about
Dialogue: 0,0:33:48.00,0:33:53.00,Default,,0000,0000,0000,,the recursion tree. What calls are made and then how deep does the recursion
Dialogue: 0,0:33:53.00,0:33:55.00,Default,,0000,0000,0000,,go before I hit the base case
Dialogue: 0,0:33:55.00,0:33:58.00,Default,,0000,0000,0000,,and that tells me how to
Dialogue: 0,0:33:58.00,0:34:08.00,Default,,0000,0000,0000,,stop that expanding and then substitute back in for the base case to compute my total result. I'm gonna do another one, so
Dialogue: 0,0:34:08.00,0:34:10.00,Default,,0000,0000,0000,,if you want to just
Dialogue: 0,0:34:10.00,0:34:12.00,Default,,0000,0000,0000,,watch and we'll do
Dialogue: 0,0:34:12.00,0:34:13.00,Default,,0000,0000,0000,,the math for this together, too.
Dialogue: 0,0:34:13.00,0:34:17.00,Default,,0000,0000,0000,,This is the Towers of Hanoi example
Dialogue: 0,0:34:17.00,0:34:18.00,Default,,0000,0000,0000,,that moves the
Dialogue: 0,0:34:18.00,0:34:20.00,Default,,0000,0000,0000,,tower away of n minus one off,
Dialogue: 0,0:34:20.00,0:34:25.00,Default,,0000,0000,0000,,moves the single disk on the bottom and then moves that tower back on.
Dialogue: 0,0:34:25.00,0:34:37.00,Default,,0000,0000,0000,,And so the recurrence that we're working with
Dialogue: 0,0:34:37.00,0:34:42.00,Default,,0000,0000,0000,,is one when n equals zero. So when n equals zero, right? We have a zero height tower to move and we
Dialogue: 0,0:34:42.00,0:34:46.00,Default,,0000,0000,0000,,actually do no work in the function, right? We just do that test and return, so if n equals zero
Dialogue: 0,0:34:46.00,0:34:47.00,Default,,0000,0000,0000,,there's no work to be done.
Dialogue: 0,0:34:47.00,0:34:50.00,Default,,0000,0000,0000,,So that's the easy case for us, right? Is
Dialogue: 0,0:34:50.00,0:34:53.00,Default,,0000,0000,0000,,when it's zero
Dialogue: 0,0:34:53.00,0:34:54.00,Default,,0000,0000,0000,,do no work.
Dialogue: 0,0:34:54.00,0:34:55.00,Default,,0000,0000,0000,,Otherwise,
Dialogue: 0,0:34:55.00,0:34:57.00,Default,,0000,0000,0000,,right? We move the bottom most disk.
Dialogue: 0,0:34:57.00,0:35:01.00,Default,,0000,0000,0000,,So we do a little testing and moving of that disk. We'll call that the constant amount of work that's in the function
Dialogue: 0,0:35:01.00,0:35:02.00,Default,,0000,0000,0000,,itself.
Dialogue: 0,0:35:02.00,0:35:04.00,Default,,0000,0000,0000,,And it makes two recursive calls
Dialogue: 0,0:35:04.00,0:35:05.00,Default,,0000,0000,0000,,each of a tower
Dialogue: 0,0:35:05.00,0:35:10.00,Default,,0000,0000,0000,,of height n minus one.
Dialogue: 0,0:35:10.00,0:35:12.00,Default,,0000,0000,0000,,So otherwise, right?
Dialogue: 0,0:35:12.00,0:35:15.00,Default,,0000,0000,0000,,Two calls, which gives a little clue to what the tree looks like. It'll branch twice
Dialogue: 0,0:35:15.00,0:35:20.00,Default,,0000,0000,0000,,at each stop and then it's one closer to that base case gives us a sense that the recursion
Dialogue: 0,0:35:20.00,0:35:21.00,Default,,0000,0000,0000,,depth
Dialogue: 0,0:35:21.00,0:35:24.00,Default,,0000,0000,0000,,is likely to be linear here.
Dialogue: 0,0:35:24.00,0:35:26.00,Default,,0000,0000,0000,,So let me go through the process of making this work.
Dialogue: 0,0:35:26.00,0:35:30.00,Default,,0000,0000,0000,,I've got T of
Dialogue: 0,0:35:30.00,0:35:33.00,Default,,0000,0000,0000,,n equals one plus two, T to the n minus one. So then
Dialogue: 0,0:35:33.00,0:35:35.00,Default,,0000,0000,0000,,I
Dialogue: 0,0:35:35.00,0:35:37.00,Default,,0000,0000,0000,,take T to the n minus one
Dialogue: 0,0:35:37.00,0:35:39.00,Default,,0000,0000,0000,,and I plug it in over here
Dialogue: 0,0:35:39.00,0:35:42.00,Default,,0000,0000,0000,,to get one plus two
Dialogue: 0,0:35:42.00,0:35:44.00,Default,,0000,0000,0000,,T to the n minus two.
Dialogue: 0,0:35:44.00,0:35:47.00,Default,,0000,0000,0000,,This whole thing is in a -
Dialogue: 0,0:35:47.00,0:35:51.00,Default,,0000,0000,0000,,multiplied by two though because I have two of those, right? From the original call
Dialogue: 0,0:35:51.00,0:35:53.00,Default,,0000,0000,0000,,which then itself made two. So, in fact, if I multiply through,
Dialogue: 0,0:35:53.00,0:35:55.00,Default,,0000,0000,0000,,right? I've got one plus
Dialogue: 0,0:35:55.00,0:35:59.00,Default,,0000,0000,0000,,two plus four
Dialogue: 0,0:35:59.00,0:36:01.00,Default,,0000,0000,0000,,T to the n over two. If
Dialogue: 0,0:36:01.00,0:36:03.00,Default,,0000,0000,0000,,I apply my substitution again, one plus two plus
Dialogue: 0,0:36:03.00,0:36:06.00,Default,,0000,0000,0000,,four times T to
Dialogue: 0,0:36:06.00,0:36:09.00,Default,,0000,0000,0000,,the n minus two is one plus two, T
Dialogue: 0,0:36:09.00,0:36:12.00,Default,,0000,0000,0000,,to the n minus three,
Dialogue: 0,0:36:12.00,0:36:13.00,Default,,0000,0000,0000,,and then let the
Dialogue: 0,0:36:13.00,0:36:21.00,Default,,0000,0000,0000,,multiplication go through again. One plus two plus four plus eight T to the n
Dialogue: 0,0:36:21.00,0:36:22.00,Default,,0000,0000,0000,,minus three.
Dialogue: 0,0:36:22.00,0:36:26.00,Default,,0000,0000,0000,,And so each expansion of this, right? Is causing the number of towers
Dialogue: 0,0:36:26.00,0:36:31.00,Default,,0000,0000,0000,,that are being moved around to go up by a factor of two. So each time I do this,
Dialogue: 0,0:36:31.00,0:36:32.00,Default,,0000,0000,0000,,right? I went from
Dialogue: 0,0:36:32.00,0:36:36.00,Default,,0000,0000,0000,,two towers to move to four towers to eight towers, but those towers each got one shorter
Dialogue: 0,0:36:36.00,0:36:41.00,Default,,0000,0000,0000,,in the process. So kind of telling us a little bit about what the recursion tree looks like, right?
Dialogue: 0,0:36:41.00,0:36:42.00,Default,,0000,0000,0000,,Is there is a
Dialogue: 0,0:36:42.00,0:36:48.00,Default,,0000,0000,0000,,branching factor of two all the way down and that
Dialogue: 0,0:36:48.00,0:36:50.00,Default,,0000,0000,0000,,the depth of this thing
Dialogue: 0,0:36:50.00,0:36:51.00,Default,,0000,0000,0000,,is gonna bottom out linearly
Dialogue: 0,0:36:51.00,0:36:57.00,Default,,0000,0000,0000,,because this was a tower by ten, nine, eight, seven, and so on down to the bottom.
Dialogue: 0,0:36:57.00,0:36:59.00,Default,,0000,0000,0000,,So if I imagined this happened I times,
Dialogue: 0,0:36:59.00,0:37:03.00,Default,,0000,0000,0000,,so to generalize my pattern. I've got one plus two
Dialogue: 0,0:37:03.00,0:37:06.00,Default,,0000,0000,0000,,plus four plus two
Dialogue: 0,0:37:06.00,0:37:09.00,Default,,0000,0000,0000,,to the I. So after I've done this
Dialogue: 0,0:37:09.00,0:37:12.00,Default,,0000,0000,0000,,that number of times, right? Actually it's two I minus one plus two to
Dialogue: 0,0:37:12.00,0:37:17.00,Default,,0000,0000,0000,,the I, T n minus I.
Dialogue: 0,0:37:17.00,0:37:22.00,Default,,0000,0000,0000,,So I have subtracted I off the heights of the tower.
Dialogue: 0,0:37:22.00,0:37:26.00,Default,,0000,0000,0000,,I have gone up by a factor of two each time I did that and then I have these sums in the front,
Dialogue: 0,0:37:26.00,0:37:30.00,Default,,0000,0000,0000,,which represent kind of the single disk that got moved in there. One plus two plus four
Dialogue: 0,0:37:30.00,0:37:32.00,Default,,0000,0000,0000,,plus eight plus so on
Dialogue: 0,0:37:32.00,0:37:33.00,Default,,0000,0000,0000,,down to there.
Dialogue: 0,0:37:33.00,0:37:37.00,Default,,0000,0000,0000,,And so the place I want to get to, right? Is where n equals zero.
Dialogue: 0,0:37:37.00,0:37:39.00,Default,,0000,0000,0000,,So I actually want to set
Dialogue: 0,0:37:39.00,0:37:44.00,Default,,0000,0000,0000,,n, I equal to n here. I wrote that backwards, let's say I equals n. I plug that in I've
Dialogue: 0,0:37:44.00,0:37:49.00,Default,,0000,0000,0000,,got one plus two plus four plus all the powers of two
Dialogue: 0,0:37:49.00,0:37:52.00,Default,,0000,0000,0000,,to the n minus one plus
Dialogue: 0,0:37:52.00,0:37:54.00,Default,,0000,0000,0000,,two to the n, T to the n minus
Dialogue: 0,0:37:54.00,0:37:55.00,Default,,0000,0000,0000,,n, which is T to the zero,
Dialogue: 0,0:37:55.00,0:37:58.00,Default,,0000,0000,0000,,which is just one.
Dialogue: 0,0:37:58.00,0:38:05.00,Default,,0000,0000,0000,,So what I've got here
Dialogue: 0,0:38:05.00,0:38:11.00,Default,,0000,0000,0000,,is following along.
Dialogue: 0,0:38:11.00,0:38:13.00,Default,,0000,0000,0000,,Is T to the n is one plus two plus four
Dialogue: 0,0:38:13.00,0:38:14.00,Default,,0000,0000,0000,,plus two to the n, right?
Dialogue: 0,0:38:14.00,0:38:18.00,Default,,0000,0000,0000,,So two
Dialogue: 0,0:38:18.00,0:38:19.00,Default,,0000,0000,0000,,to the n
Dialogue: 0,0:38:19.00,0:38:20.00,Default,,0000,0000,0000,,minus
Dialogue: 0,0:38:20.00,0:38:23.00,Default,,0000,0000,0000,,one plus two to the n times one.
Dialogue: 0,0:38:23.00,0:38:25.00,Default,,0000,0000,0000,,So I've got the geometric sum here.
Dialogue: 0,0:38:25.00,0:38:26.00,Default,,0000,0000,0000,,You may or may not
Dialogue: 0,0:38:26.00,0:38:30.00,Default,,0000,0000,0000,,all ready know how to solve this one, but I'm just gonna go ahead and
Dialogue: 0,0:38:30.00,0:38:34.00,Default,,0000,0000,0000,,solve it in front of you to remind you of how the process works. I've got the powers of two.
Dialogue: 0,0:38:34.00,0:38:36.00,Default,,0000,0000,0000,,One plus two plus up to the n.
Dialogue: 0,0:38:36.00,0:38:39.00,Default,,0000,0000,0000,,So that's the term I'm looking for. I want to call this A
Dialogue: 0,0:38:39.00,0:38:40.00,Default,,0000,0000,0000,,just to mark it.
Dialogue: 0,0:38:40.00,0:38:45.00,Default,,0000,0000,0000,,And then what I'm gonna compute for you is what two times A is
Dialogue: 0,0:38:45.00,0:38:50.00,Default,,0000,0000,0000,,and I'm gonna write it underneath. So if I multiply this by two I have one times two, which is two.
Dialogue: 0,0:38:50.00,0:38:52.00,Default,,0000,0000,0000,,Two times two, which is four,
Dialogue: 0,0:38:52.00,0:38:53.00,Default,,0000,0000,0000,,right? Four times four
Dialogue: 0,0:38:53.00,0:38:55.00,Default,,0000,0000,0000,,at two, which is eight.
Dialogue: 0,0:38:55.00,0:38:56.00,Default,,0000,0000,0000,,And so on.
Dialogue: 0,0:38:56.00,0:38:59.00,Default,,0000,0000,0000,,And so I should get
Dialogue: 0,0:38:59.00,0:39:02.00,Default,,0000,0000,0000,,basically the same sequence of terms, but shifted over by one.
Dialogue: 0,0:39:02.00,0:39:04.00,Default,,0000,0000,0000,,I don't have the factor of one
Dialogue: 0,0:39:04.00,0:39:06.00,Default,,0000,0000,0000,,and I do have an additional factor of two to the
Dialogue: 0,0:39:06.00,0:39:11.00,Default,,0000,0000,0000,,n times another power of two at the end. So I've got the whole term kind of shifted
Dialogue: 0,0:39:11.00,0:39:15.00,Default,,0000,0000,0000,,over by one. That's my two A so that's the same thing I'm looking for, but doubled.
Dialogue: 0,0:39:15.00,0:39:17.00,Default,,0000,0000,0000,,And then I'm gonna basically take this thing
Dialogue: 0,0:39:17.00,0:39:19.00,Default,,0000,0000,0000,,and I'm gonna
Dialogue: 0,0:39:19.00,0:39:23.00,Default,,0000,0000,0000,,add negative A to two A. So subtracting A off of two A
Dialogue: 0,0:39:23.00,0:39:24.00,Default,,0000,0000,0000,,so that all these terms
Dialogue: 0,0:39:24.00,0:39:28.00,Default,,0000,0000,0000,,will go away. If I have this minus this, this minus this all the way across, right?
Dialogue: 0,0:39:28.00,0:39:30.00,Default,,0000,0000,0000,,The terms I'll be left with
Dialogue: 0,0:39:30.00,0:39:32.00,Default,,0000,0000,0000,,is two to the n plus one
Dialogue: 0,0:39:32.00,0:39:35.00,Default,,0000,0000,0000,,minus one is
Dialogue: 0,0:39:35.00,0:39:37.00,Default,,0000,0000,0000,,A subtracted from two A so the
Dialogue: 0,0:39:37.00,0:39:38.00,Default,,0000,0000,0000,,two to the T to
Dialogue: 0,0:39:38.00,0:39:41.00,Default,,0000,0000,0000,,the n that I'm looking for
Dialogue: 0,0:39:41.00,0:39:43.00,Default,,0000,0000,0000,,is two to the n plus one minus one.
Dialogue: 0,0:39:43.00,0:39:45.00,Default,,0000,0000,0000,,That's my term there. And
Dialogue: 0,0:39:45.00,0:39:51.00,Default,,0000,0000,0000,,if I summarize in my big O way,
Dialogue: 0,0:39:51.00,0:39:56.00,Default,,0000,0000,0000,,ignoring the constants, throwing away these little parts of the terms, right? That are in the noise. That
Dialogue: 0,0:39:56.00,0:39:58.00,Default,,0000,0000,0000,,what we really have here is something that grows,
Dialogue: 0,0:39:58.00,0:40:00.00,Default,,0000,0000,0000,,right? Exponentially
Dialogue: 0,0:40:00.00,0:40:04.00,Default,,0000,0000,0000,,by about a factor of two for each additional
Dialogue: 0,0:40:04.00,0:40:05.00,Default,,0000,0000,0000,,
Dialogue: 0,0:40:05.00,0:40:07.00,Default,,0000,0000,0000,,disk added to the tower.
Dialogue: 0,0:40:07.00,0:40:10.00,Default,,0000,0000,0000,,So however much time it took to move a tower of height ten,
Dialogue: 0,0:40:10.00,0:40:15.00,Default,,0000,0000,0000,,right? A tower of height 11 we expect to take twice as long. So not growing linearly at all, right?
Dialogue: 0,0:40:15.00,0:40:18.00,Default,,0000,0000,0000,,Much, much, much sharply growing, right? What exponential
Dialogue: 0,0:40:18.00,0:40:19.00,Default,,0000,0000,0000,,growth looks like.
Dialogue: 0,0:40:19.00,0:40:22.00,Default,,0000,0000,0000,,Two to the n, right? Even for small values of n.
Dialogue: 0,0:40:22.00,0:40:27.00,Default,,0000,0000,0000,,Ten, 20, right? Is up into the millions all ready in terms of disks that need to be
Dialogue: 0,0:40:27.00,0:40:30.00,Default,,0000,0000,0000,,moved. So
Dialogue: 0,0:40:30.00,0:40:33.00,Default,,0000,0000,0000,,this sort of strategy, right? Is good to know. When you're looking at this recursive things, right?
Dialogue: 0,0:40:33.00,0:40:37.00,Default,,0000,0000,0000,,Kind of having this analysis. It says, okay, well, where did I start from?
Dialogue: 0,0:40:37.00,0:40:41.00,Default,,0000,0000,0000,,What's the time? And then just being pretty mechanical. Sometimes you can get to something here that
Dialogue: 0,0:40:41.00,0:40:45.00,Default,,0000,0000,0000,,requires a little bit of algebra to work out, but the most common patterns, right?
Dialogue: 0,0:40:45.00,0:40:48.00,Default,,0000,0000,0000,,You'll start to recognize over and again, right?
Dialogue: 0,0:40:48.00,0:40:51.00,Default,,0000,0000,0000,,And this one, right? The fact that it's branching by a factor of two
Dialogue: 0,0:40:51.00,0:41:03.00,Default,,0000,0000,0000,,telling you that at the kind of base case, right? You're gonna expect to see a two to the n expansion.
Dialogue: 0,0:41:03.00,0:41:05.00,Default,,0000,0000,0000,,So just to give you
Dialogue: 0,0:41:05.00,0:41:09.00,Default,,0000,0000,0000,,a little bit of some idea that you can use big O to predict things
Dialogue: 0,0:41:09.00,0:41:13.00,Default,,0000,0000,0000,,based on getting some run time performance for some small values of n
Dialogue: 0,0:41:13.00,0:41:16.00,Default,,0000,0000,0000,,and then what you'd expect to see for larger values.
Dialogue: 0,0:41:16.00,0:41:17.00,Default,,0000,0000,0000,,So I have
Dialogue: 0,0:41:17.00,0:41:19.00,Default,,0000,0000,0000,,three different algorithms here.
Dialogue: 0,0:41:19.00,0:41:20.00,Default,,0000,0000,0000,,One that was
Dialogue: 0,0:41:20.00,0:41:24.00,Default,,0000,0000,0000,,just logarithmic in terms of n, so it should divide the input in half and kind of
Dialogue: 0,0:41:24.00,0:41:27.00,Default,,0000,0000,0000,,work on it. Something like binary search actually fits that profile.
Dialogue: 0,0:41:27.00,0:41:31.00,Default,,0000,0000,0000,,Something that's linear. Something that's n log n and something that's n squared.
Dialogue: 0,0:41:31.00,0:41:35.00,Default,,0000,0000,0000,,Then for different values of n I've plugged in actually the first ones I ran and then actually
Dialogue: 0,0:41:35.00,0:41:39.00,Default,,0000,0000,0000,,I - some of the other ones I had to estimate because they were taking way too long to finish.
Dialogue: 0,0:41:39.00,0:41:43.00,Default,,0000,0000,0000,,So that for an input of size ten, all of them are imperceptible. These are in terms of seconds
Dialogue: 0,0:41:43.00,0:41:44.00,Default,,0000,0000,0000,,here.
Dialogue: 0,0:41:44.00,0:41:48.00,Default,,0000,0000,0000,,Taking fractions of seconds. This is on my machine that is running at a couple gigahertz, so it's
Dialogue: 0,0:41:48.00,0:41:50.00,Default,,0000,0000,0000,,got about a million instructions per second.
Dialogue: 0,0:41:50.00,0:41:53.00,Default,,0000,0000,0000,,You up that by a factor of ten, right?
Dialogue: 0,0:41:53.00,0:41:56.00,Default,,0000,0000,0000,,And they're still kind of in the subsecond range, but you can see that from the
Dialogue: 0,0:41:56.00,0:41:59.00,Default,,0000,0000,0000,,n squared algorithm
Dialogue: 0,0:41:59.00,0:42:00.00,Default,,0000,0000,0000,,took a bigger jump,
Dialogue: 0,0:42:00.00,0:42:04.00,Default,,0000,0000,0000,,let's say, than the linear algorithm did, which went up by a factor of ten almost
Dialogue: 0,0:42:04.00,0:42:05.00,Default,,0000,0000,0000,,exactly.
Dialogue: 0,0:42:05.00,0:42:07.00,Default,,0000,0000,0000,,Going up by another factor of ten
Dialogue: 0,0:42:07.00,0:42:08.00,Default,,0000,0000,0000,,and,
Dialogue: 0,0:42:08.00,0:42:13.00,Default,,0000,0000,0000,,again, sort of climbing, right? 10,000, 100,000, a million, a trillion. You
Dialogue: 0,0:42:13.00,0:42:15.00,Default,,0000,0000,0000,,get to something that's like 100,000, right?
Dialogue: 0,0:42:15.00,0:42:20.00,Default,,0000,0000,0000,,And an algorithm that's linear, right? Is still taking a fraction of a second. But something
Dialogue: 0,0:42:20.00,0:42:24.00,Default,,0000,0000,0000,,that was quadratic now has climbed up to take several hours.
Dialogue: 0,0:42:24.00,0:42:28.00,Default,,0000,0000,0000,,So even for inputs that don't seem particularly huge, right? The difference between having an
Dialogue: 0,0:42:28.00,0:42:33.00,Default,,0000,0000,0000,,algorithm that's gonna operate in linear time versus quadratic is gonna be felt very profoundly. And
Dialogue: 0,0:42:33.00,0:42:37.00,Default,,0000,0000,0000,,as you move to these larger numbers you have things that you just can't do,
Dialogue: 0,0:42:37.00,0:42:40.00,Default,,0000,0000,0000,,right? You cannot run an n squared algorithm on a trillion pieces of data
Dialogue: 0,0:42:40.00,0:42:42.00,Default,,0000,0000,0000,,in your lifetime.
Dialogue: 0,0:42:42.00,0:42:43.00,Default,,0000,0000,0000,,
Dialogue: 0,0:42:43.00,0:42:48.00,Default,,0000,0000,0000,,It's just too much work for what the input is. Clinton? Yeah. How did it go down for a
Dialogue: 0,0:42:48.00,0:42:51.00,Default,,0000,0000,0000,,billion from
Dialogue: 0,0:42:51.00,0:42:53.00,Default,,0000,0000,0000,,like a million?
Dialogue: 0,0:42:53.00,0:42:55.00,Default,,0000,0000,0000,,From - Oh, you know what,
Dialogue: 0,0:42:55.00,0:42:59.00,Default,,0000,0000,0000,,that just must be wrong. You're totally right. That should definitely be over some. Yeah.
Dialogue: 0,0:42:59.00,0:43:02.00,Default,,0000,0000,0000,,Well log n should really be - I think that
Dialogue: 0,0:43:02.00,0:43:05.00,Default,,0000,0000,0000,,when I copied and pasted from these terminal window. So, of course, I must have just made a mistake when I
Dialogue: 0,0:43:05.00,0:43:08.00,Default,,0000,0000,0000,,was moving something across, but you're totally right.
Dialogue: 0,0:43:08.00,0:43:09.00,Default,,0000,0000,0000,,This should be going up,
Dialogue: 0,0:43:09.00,0:43:13.00,Default,,0000,0000,0000,,right? Ever so slightly, right? This algorithms going very, very slowly logarithmic function,
Dialogue: 0,0:43:13.00,0:43:16.00,Default,,0000,0000,0000,,right? Almost a flat line, but that definitely should be up a little bit, right? From
Dialogue: 0,0:43:16.00,0:43:18.00,Default,,0000,0000,0000,,where it is.
Dialogue: 0,0:43:18.00,0:43:19.00,Default,,0000,0000,0000,,When you get to a trillion, right?
Dialogue: 0,0:43:19.00,0:43:24.00,Default,,0000,0000,0000,,Even the linear algorithm is starting to actually take some noticeable time, right?
Dialogue: 0,0:43:24.00,0:43:28.00,Default,,0000,0000,0000,,But things that are logarithmic still running very, very slowly. So this is an example of
Dialogue: 0,0:43:28.00,0:43:32.00,Default,,0000,0000,0000,,binary search. Binary search operating on a million or trillion items is still just
Dialogue: 0,0:43:32.00,0:43:33.00,Default,,0000,0000,0000,,in a
Dialogue: 0,0:43:33.00,0:43:35.00,Default,,0000,0000,0000,,flash, right? Telling you whether it found it or not.
Dialogue: 0,0:43:35.00,0:43:37.00,Default,,0000,0000,0000,,Doing a linear search
Dialogue: 0,0:43:37.00,0:43:38.00,Default,,0000,0000,0000,,on a trillion or billion
Dialogue: 0,0:43:38.00,0:43:40.00,Default,,0000,0000,0000,,is
Dialogue: 0,0:43:40.00,0:43:41.00,Default,,0000,0000,0000,,several minutes' worth of
Dialogue: 0,0:43:41.00,0:43:45.00,Default,,0000,0000,0000,,my old computers
Dialogue: 0,0:43:45.00,0:43:48.00,Default,,0000,0000,0000,,time. And so just another way to look at them, right? Is to think about what those things look
Dialogue: 0,0:43:48.00,0:43:51.00,Default,,0000,0000,0000,,like in terms of graphed on the Cartesian plane
Dialogue: 0,0:43:51.00,0:43:55.00,Default,,0000,0000,0000,,that a constant algorithm is just a flat line. It takes the same amount of time no matter how big the input is.
Dialogue: 0,0:43:55.00,0:43:56.00,Default,,0000,0000,0000,,It's
Dialogue: 0,0:43:56.00,0:44:00.00,Default,,0000,0000,0000,,pretty small values of n down here, so it just shows the early stages, right? But logarithmic, right?
Dialogue: 0,0:44:00.00,0:44:03.00,Default,,0000,0000,0000,,Almost a flat line itself. A little bit above
Dialogue: 0,0:44:03.00,0:44:06.00,Default,,0000,0000,0000,,constant, but very, very slowly growing.
Dialogue: 0,0:44:06.00,0:44:07.00,Default,,0000,0000,0000,,The
Dialogue: 0,0:44:07.00,0:44:09.00,Default,,0000,0000,0000,,linear scale, right? Showing the lines and then the
Dialogue: 0,0:44:09.00,0:44:13.00,Default,,0000,0000,0000,,n squared and to the n showing you that they're kind of heading to the hills very
Dialogue: 0,0:44:13.00,0:44:15.00,Default,,0000,0000,0000,,quickly here. So even for small values of n
Dialogue: 0,0:44:15.00,0:44:16.00,Default,,0000,0000,0000,,
Dialogue: 0,0:44:16.00,0:44:18.00,Default,,0000,0000,0000,,they are reaching into the
Dialogue: 0,0:44:18.00,0:44:23.00,Default,,0000,0000,0000,,high regions and will continue to do so as
Dialogue: 0,0:44:23.00,0:44:31.00,Default,,0000,0000,0000,,that will be more pronounced, right? As you move into the higher and higher values of n. All right. I get to tell
Dialogue: 0,0:44:31.00,0:44:34.00,Default,,0000,0000,0000,,you a little bit about sorting before
Dialogue: 0,0:44:34.00,0:44:36.00,Default,,0000,0000,0000,,we go away. Because some of them I'm just setting the stage for, like,
Dialogue: 0,0:44:36.00,0:44:40.00,Default,,0000,0000,0000,,okay, how can we use this to do something interesting? Knowing about how to compare and then contrast.
Dialogue: 0,0:44:40.00,0:44:41.00,Default,,0000,0000,0000,,That it tells you something.
Dialogue: 0,0:44:41.00,0:44:44.00,Default,,0000,0000,0000,,Let's try to solve a problem, right? That
Dialogue: 0,0:44:44.00,0:44:47.00,Default,,0000,0000,0000,,lends itself to different approaches that have different algorithmic
Dialogue: 0,0:44:47.00,0:44:50.00,Default,,0000,0000,0000,,results to them that are worth thinking about.
Dialogue: 0,0:44:50.00,0:44:54.00,Default,,0000,0000,0000,,So sorting turns out to be one of the best problems to study for this because it turns out sorting
Dialogue: 0,0:44:54.00,0:44:55.00,Default,,0000,0000,0000,,is
Dialogue: 0,0:44:55.00,0:44:58.00,Default,,0000,0000,0000,,one of the things that computers do a lot of.
Dialogue: 0,0:44:58.00,0:45:02.00,Default,,0000,0000,0000,,That it's very, very common that you need to keep data in sorted order. It makes it easier to
Dialogue: 0,0:45:02.00,0:45:06.00,Default,,0000,0000,0000,,search. It makes it easier to find the minimum, the maximum, and find duplicates. All these sort of things, right?
Dialogue: 0,0:45:06.00,0:45:09.00,Default,,0000,0000,0000,,Like by having, keeping it inserted or it tends to be more convenient to access that way.
Dialogue: 0,0:45:09.00,0:45:11.00,Default,,0000,0000,0000,,It also makes a bunch of other things,
Dialogue: 0,0:45:11.00,0:45:14.00,Default,,0000,0000,0000,,other properties about the data, easy to do.
Dialogue: 0,0:45:14.00,0:45:18.00,Default,,0000,0000,0000,,If you want to find the top ten percent, right? You can just pick them off, right? If they've all ready
Dialogue: 0,0:45:18.00,0:45:19.00,Default,,0000,0000,0000,,
Dialogue: 0,0:45:19.00,0:45:20.00,Default,,0000,0000,0000,,been sorted. You want to
Dialogue: 0,0:45:20.00,0:45:23.00,Default,,0000,0000,0000,,group them into buckets for histograming, right? All these things actually are
Dialogue: 0,0:45:23.00,0:45:24.00,Default,,0000,0000,0000,,enabled by having them
Dialogue: 0,0:45:24.00,0:45:28.00,Default,,0000,0000,0000,,all ready be in sorted order. So it turns out that a lot of times that data that you get
Dialogue: 0,0:45:28.00,0:45:31.00,Default,,0000,0000,0000,,from other sources tends to first need to be put in sorted order before you start doing
Dialogue: 0,0:45:31.00,0:45:33.00,Default,,0000,0000,0000,,stuff on it. Okay.
Dialogue: 0,0:45:33.00,0:45:36.00,Default,,0000,0000,0000,,Well, there's lots of different ways you can sort it.
Dialogue: 0,0:45:36.00,0:45:40.00,Default,,0000,0000,0000,,There are simple ways. There are complicated ways. There are fancy ways. There are ways that
Dialogue: 0,0:45:40.00,0:45:42.00,Default,,0000,0000,0000,,are dumb,
Dialogue: 0,0:45:42.00,0:45:44.00,Default,,0000,0000,0000,,
Dialogue: 0,0:45:44.00,0:45:46.00,Default,,0000,0000,0000,,but easy to write. Ways that are smart, but hard
Dialogue: 0,0:45:46.00,0:45:48.00,Default,,0000,0000,0000,,to write. And everything in between.
Dialogue: 0,0:45:48.00,0:45:52.00,Default,,0000,0000,0000,,So we're gonna be looking at it in terms of sorting vectors because that's probably the most common data structure
Dialogue: 0,0:45:52.00,0:45:53.00,Default,,0000,0000,0000,,that needs the sorting.
Dialogue: 0,0:45:53.00,0:45:57.00,Default,,0000,0000,0000,,But you can also imagine taking the same kind of algorithms and applying them to different kinds of data
Dialogue: 0,0:45:57.00,0:46:00.00,Default,,0000,0000,0000,,structures you have. Like starting a linked list.
Dialogue: 0,0:46:00.00,0:46:04.00,Default,,0000,0000,0000,,Okay. So I'm gonna show you a sorting algorithm.
Dialogue: 0,0:46:04.00,0:46:06.00,Default,,0000,0000,0000,,It's probably the simplest and the easiest to write.
Dialogue: 0,0:46:06.00,0:46:10.00,Default,,0000,0000,0000,,If somebody - if you were stuck on a desert island without a textbook, but you happen to have
Dialogue: 0,0:46:10.00,0:46:11.00,Default,,0000,0000,0000,,a compiler
Dialogue: 0,0:46:11.00,0:46:15.00,Default,,0000,0000,0000,,and you needed to write a sorting algorithm to get your way off the island. It
Dialogue: 0,0:46:15.00,0:46:18.00,Default,,0000,0000,0000,,comes up all the time.
Dialogue: 0,0:46:18.00,0:46:20.00,Default,,0000,0000,0000,,This is probably the algorithm you're gonna use.
Dialogue: 0,0:46:20.00,0:46:23.00,Default,,0000,0000,0000,,It's called selection sort.
Dialogue: 0,0:46:23.00,0:46:24.00,Default,,0000,0000,0000,,And the idea behind selection sort
Dialogue: 0,0:46:24.00,0:46:26.00,Default,,0000,0000,0000,,is that it's going to select
Dialogue: 0,0:46:26.00,0:46:28.00,Default,,0000,0000,0000,,the smallest element
Dialogue: 0,0:46:28.00,0:46:30.00,Default,,0000,0000,0000,,and put it in the front.
Dialogue: 0,0:46:30.00,0:46:33.00,Default,,0000,0000,0000,,So if I have a big stack of test papers
Dialogue: 0,0:46:33.00,0:46:36.00,Default,,0000,0000,0000,,and I want to sort them in order of score,
Dialogue: 0,0:46:36.00,0:46:40.00,Default,,0000,0000,0000,,then I'm gonna go through there and find somebody who got the absolute lowest score. It's said, but
Dialogue: 0,0:46:40.00,0:46:42.00,Default,,0000,0000,0000,,true. Somebody had to be there.
Dialogue: 0,0:46:42.00,0:46:45.00,Default,,0000,0000,0000,,So I kind of work my through it and maybe I hold my finger on the one that I've seen that looks
Dialogue: 0,0:46:45.00,0:46:49.00,Default,,0000,0000,0000,,smallest so far. So this one's a 40, oh,
Dialogue: 0,0:46:49.00,0:46:50.00,Default,,0000,0000,0000,,well, this one's a 38. Okay. Oh, look there's a 35. Oh,
Dialogue: 0,0:46:50.00,0:46:54.00,Default,,0000,0000,0000,,look, there's a 22. Nobody gets these scores in my exams, I'm just kidding.
Dialogue: 0,0:46:54.00,0:46:56.00,Default,,0000,0000,0000,,And then finally get down to the bottom. You say, okay,
Dialogue: 0,0:46:56.00,0:47:00.00,Default,,0000,0000,0000,,that 25, that was the smallest. I have a hold of it, right? And
Dialogue: 0,0:47:00.00,0:47:01.00,Default,,0000,0000,0000,,I'm gonna basically take that
Dialogue: 0,0:47:01.00,0:47:03.00,Default,,0000,0000,0000,,and bring it to the front.
Dialogue: 0,0:47:03.00,0:47:05.00,Default,,0000,0000,0000,,
Dialogue: 0,0:47:05.00,0:47:07.00,Default,,0000,0000,0000,,And in terms of managing a vector
Dialogue: 0,0:47:07.00,0:47:11.00,Default,,0000,0000,0000,,that actually there's a slight efficiency to be had by instead of kind of pulling it out of the
Dialogue: 0,0:47:11.00,0:47:15.00,Default,,0000,0000,0000,,stack and sliding everything down I'm actually just gonna swap it with the one that's in the
Dialogue: 0,0:47:15.00,0:47:18.00,Default,,0000,0000,0000,,very front. So whoever was the current first one is gonna booted
Dialogue: 0,0:47:18.00,0:47:22.00,Default,,0000,0000,0000,,to pull in this one and I'm gonna put them back where this other one came from.
Dialogue: 0,0:47:22.00,0:47:26.00,Default,,0000,0000,0000,,So I have moved the very smallest to the top of the vector.
Dialogue: 0,0:47:26.00,0:47:28.00,Default,,0000,0000,0000,,Then I just do the same thing again,
Dialogue: 0,0:47:28.00,0:47:32.00,Default,,0000,0000,0000,,but now excluding that smallest one. So I've all ready seen that one and kind of set it aside. I start looking
Dialogue: 0,0:47:32.00,0:47:35.00,Default,,0000,0000,0000,,at the remaining n minus one and I do the same thing again.
Dialogue: 0,0:47:35.00,0:47:38.00,Default,,0000,0000,0000,,Find the smallest of what remains, kind of just walking through,
Dialogue: 0,0:47:38.00,0:47:39.00,Default,,0000,0000,0000,,going to find it,
Dialogue: 0,0:47:39.00,0:47:44.00,Default,,0000,0000,0000,,and swap it down into the second slot, and so on.
Dialogue: 0,0:47:44.00,0:47:50.00,Default,,0000,0000,0000,,A little bit of code.
Dialogue: 0,0:47:50.00,0:47:55.00,Default,,0000,0000,0000,,Doing it kind of the way I described it, right? Of tracking the minimum index, right? Looking from
Dialogue: 0,0:47:55.00,0:47:59.00,Default,,0000,0000,0000,,here to the end, so this four loop in the middle here starts at the current position and only considers
Dialogue: 0,0:47:59.00,0:48:01.00,Default,,0000,0000,0000,,from here
Dialogue: 0,0:48:01.00,0:48:02.00,Default,,0000,0000,0000,,to the very end of the
Dialogue: 0,0:48:02.00,0:48:05.00,Default,,0000,0000,0000,,vector and then finds
Dialogue: 0,0:48:05.00,0:48:09.00,Default,,0000,0000,0000,,any element which is smaller than the one I'm kind of currently holding my finger on
Dialogue: 0,0:48:09.00,0:48:13.00,Default,,0000,0000,0000,,and then when I'm done after that inner loop has executed I will know what the min index is
Dialogue: 0,0:48:13.00,0:48:15.00,Default,,0000,0000,0000,,and then there's a spot function here
Dialogue: 0,0:48:15.00,0:48:17.00,Default,,0000,0000,0000,,that just exchanges those two things.
Dialogue: 0,0:48:17.00,0:48:19.00,Default,,0000,0000,0000,,The I slot now gets replaced with the one
Dialogue: 0,0:48:19.00,0:48:22.00,Default,,0000,0000,0000,,at min index and,
Dialogue: 0,0:48:22.00,0:48:25.00,Default,,0000,0000,0000,,again, exchanged in the contents of the array. I just do that
Dialogue: 0,0:48:25.00,0:48:28.00,Default,,0000,0000,0000,,n minus one times and I will have done it all. I'd like to show
Dialogue: 0,0:48:28.00,0:48:32.00,Default,,0000,0000,0000,,you animation, but I guess I'll just wait for that until Wednesday. We will
Dialogue: 0,0:48:32.00,0:48:36.00,Default,,0000,0000,0000,,watch it doing it's kind of thing in progress and you can kind of be thinking about for Wednesday what other
Dialogue: 0,0:48:36.00,0:48:37.00,Default,,0000,0000,0000,,ways you might be able to sort
Dialogue: 0,0:48:37.00,0:48:42.00,Default,,0000,0000,0000,,data than just this strategy.