This course has been updated into a 4 part series! We now recommend you take the A Practical Guide to Algorithms with JavaScript course.
Transcript from the "Understanding Big-O" Lesson
[00:00:00]
>> Bianca Gandolfo: Here's a number of operations, so for the first one, we have n squared. We have two nested loops, where we're comparing all numbers to each other, yeah?
>> Bianca Gandolfo: Second one, we have 2n, where we just find the minimum and maximum, we loop through it once, and have two operations.
[00:00:29]
>> Bianca Gandolfo: So, n times n equals 2n, or equals n,
>> Bianca Gandolfo: Squared, thank you, 2n equals n2.
>> Bianca Gandolfo: So it's just n, so 2n is 2 times n and n squared is n times n, that's the difference, yeah.
>> Bianca Gandolfo: Cool.
>> Speaker 2: Somebody's asking you to explain 2n one more time?
[00:01:05]
>> Bianca Gandolfo: Yeah, sure so I can explain 2n one more time. So, let's go to that slide.
>> Bianca Gandolfo: So here, as we're looping through, we can write out some code.
>> Bianca Gandolfo: Right, something like this, I'm not gonna type out the whole thing. We have to loop through it, and then you have to say something like if,
[00:01:43]
>> Bianca Gandolfo: Let's just say like, is max, something like that, is min.
>> Bianca Gandolfo: So as we're looping through, so i is the length of the hotels, right? That's our n, it's also the number of columns that we have here.
>> Bianca Gandolfo: As we're going through we're doing two operations per loop.
[00:02:16] So per hotel, we're doing two operations.
>> Bianca Gandolfo: So for example, if we have,
>> Bianca Gandolfo: 10 hotels in our list, we're doing a total of 20 operations.
>> Bianca Gandolfo: And so that's 2n. And you can check that by expanding out this graph or this table. And counting or multiplying the number of boxes in here.
[00:02:48]
>> Bianca Gandolfo: So for every time we add one more unit to our hotels, 2n, it's gonna give us two more things that we have to do.
>> Bianca Gandolfo: Yeah, okay.
>> Bianca Gandolfo: Good, anymore questions about that?
>> Bianca Gandolfo: So here we're just thinking about, how does the work increase as our input grows.
[00:03:19] That is the speed of our algorithm.
>> Bianca Gandolfo: Cool, great,
>> Bianca Gandolfo: Awesome. So 2n we're just looping through when we're checking for the minimum or maximum.
>> Bianca Gandolfo: This should be 2, we have a sorted list, and we'll find the first and last.
>> Bianca Gandolfo: Cool?
>> Bianca Gandolfo: So what does that mean in computer science terms?
[00:03:50] So we've been talking about big O, big O, big O, you might have seen them in some of the solutions, what is this? So anything that is like a nested for loop or has any sort of n squared time complexity, is gonna be quadratic time or O of n squared.
[00:04:10] And that's the notation, that's how we talk about it. Cool, and then for 2n we call that O of n, and we call that linear time. We drop any non significant digits, so if it's 2n it's just n we just drop it and these are estimations. Right we're not calculating the exact time complexity.
[00:04:33] Anything that doesn't have an n, is gonna be considered constant. So it's the same no matter how your dataset grows, it's gonna be the same amount of operations.
>> Bianca Gandolfo: Cool, awesome. And so here's sort of a range of the different time complexities, with their names and their notation.
[00:04:59] So constant time is gonna be the fastest one, logarithmic time which we'll talk about in a second, this is second fastest, then we have linear, quadratic, and exponential. So exponential is some constant to the n, and that super slow. Anything that's above linear is considered like a bad algorithm.
[00:05:17] Like you don't wanna be in quadratic or exponential time.
>> Bianca Gandolfo: Anything linear below is fine, of course, there's more details to be filled in there depending on your data set and what you need to be doing, right? But that's sort of a generalization. What about O of n log n, we'll get to that later today.
[00:05:49]
>> Speaker 2: Just curious where the O comes from?
>> Bianca Gandolfo: That is a good question, I'm not sure.
>> Speaker 2: Okay. Order?
>> Bianca Gandolfo: What's that?
>> Speaker 2: Order of one?
>> Bianca Gandolfo: No, they're mostly Greek letters. So there's big theta, there's big O, big omega, little theta, there's a bunch of different ones.
[00:06:07] I'm not sure where the O comes from, yeah. I have a link at the end of the slide deck that has more information about the different kinds of notation.
>> Speaker 2: I think it does stand for order the the Greek letters were introduced later by.
>> Bianca Gandolfo: Really, okay, cool, thank you.
[00:06:24]
>> Speaker 2: The O comes from math of course.
>> Bianca Gandolfo: Love to have a mathematician in the audience, that's great, cool. All right, wow is this landing with everyone?
>> Speaker 2: It's good, I've always wanted to know what those things mean.
>> Bianca Gandolfo: Yeah, they sound a lot more scary than what it actually looks like, when you kinda break it down in to a table.
[00:06:53]
>> Bianca Gandolfo: Cool, can someone explain to me in their own words,
>> Bianca Gandolfo: This table.
>> Bianca Gandolfo: Or this part, not the algorithm part.
>> Bianca Gandolfo: Let's see, let me ask. Let me ask Rosie.
>> Bianca Gandolfo: Could you explain to me one of these rows in your own words? Like how does the big O in the name relate to the number of operations?
[00:07:43]
>> Rosie: Going-
>> Bianca Gandolfo: You can phone a friend, if you want.
>> Rosie: [LAUGH] It's going from lots, and lots, and lots operations and probably running really slow too. On a very quantifiable number of operations and run it pretty fast.
>> Bianca Gandolfo: Yeah, absolutely so constant time, every time you add another data point or hundreds or thousands or millions.
[00:08:10] It's always going to have to do three operations, that's it. It's not related to the size of the data set, for linear it's in this case two times, or one time. And then quadratic, exponential, right?
>> Speaker 2: I think it is helpful to think about what happens if you double the size of the input, so for quadratic if you double the input you quadruple the time.
[00:08:40] For linear if you double the input you double the time, and for consonants if you double the input it doesn't matter.
>> Bianca Gandolfo: Yeah, yeah absolutely I like that, I like that, awesome. Cool, we're gonna keep rolling, here we are. You guys have probably seen this graph before, have you guys seen this graph before in computer science, whatever?
[00:09:01] This is from bigocheatsheet.com, I highly recommend that website. And so this is time, and just like David was saying, here is the input, or the space taken, depending on what you're doing. So here is constant time, so no matter how the input grows, so we can imagine that this is 1, this is 100, this is 1,000, this is a million, a bajillion is probably over here, roughly.
[00:09:34] As it grows, the amount of work and the amount of time that it takes to complete is going to stay the same, yeah?
>> Bianca Gandolfo: And then when we have linear it's gong to grow exactly proportional to the input size.
>> Bianca Gandolfo: See that? Log in is a pretty interesting one, so as it grows, the difference decreases.
[00:10:07] So obviously the time still gets slower, but the difference between the inputs is decreased. So you can see here, as this curve, it curves, curves, curves really fast and then it kind of starts to level out almost. And so that's a pretty good runtime.
>> Bianca Gandolfo: Depending on where you are.
[00:10:30] Cool, and then n squared, we just yeah and cubed all the way up, and to the n all the way up.
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: Any observations about this graph?
>> Speaker 2: I have one. So for the green one the highest degree, so if you don't have the O(1) and O(n) the green line intersects if the number of data is less than that where they intersects.
[00:11:03] So it's probably better to use the higher order one that the-
>> Bianca Gandolfo: Yeah, that's an awesome observation. So depending on how much data you have,
>> Bianca Gandolfo: Sometimes it's faster to use a slower one, or it doesn't really matter at that point. So whenever people are asking me these questions, you need to make sure that you're not pre-optimizing if you don't even have that much data.
[00:11:30] If you have 10 to 100, or even just 1,000 data points, probably is fine to do any of these, except for maybe this one.
>> Rosie: Is there an example of the logarithmic situation?
>> Bianca Gandolfo: Yeah, we're gonna get to that in a second, yeah, yeah.
>> Rosie: Cuz I can imagine what a quadratic one is or like, an exponential one, linear rate.
[00:11:54] But I don't know what would qualify-
>> Bianca Gandolfo: As logarithmic.
>> Rosie: To be logarithmic.
>> Bianca Gandolfo: Yeah, so logarithmic happens when you cut the problem in half every time. So as it grows, you cut it in half.
>> Rosie: Yeah, okay.
>> Speaker 2: Research.
>> Bianca Gandolfo: Yep.
>> Speaker 2: Is the green line still considered quadratic?
[00:12:15]
>> Bianca Gandolfo: This one?
>> Speaker 2: Yeah.
>> Bianca Gandolfo: I'm not quite sure about that one, that's a funky one. Mathematician, what say you?
>> Speaker 2: It's the inverse of a quadratic function, but it's not quadratic. Is it like n to the negative 2?
>> Speaker 4: Into the one-half.
>> Speaker 2: Into the one-half.
>> Bianca Gandolfo: Okay yeah, so that would be exponential.
[00:12:40]
>> Bianca Gandolfo: Cool.
>> Speaker 2: Does it not have any negative?
>> Speaker 4: It's a power, but it's a power, linear is n to the 1. Square root is n to the one-half, and then quadratic is n to the 2, right?
>> Bianca Gandolfo: Got it.
>> Speaker 2: So the bigger the exponent they're the faster.
[00:12:53]
>> Bianca Gandolfo: Yeah, cool you won't really see that very often.