This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Big O" Lesson
[00:00:00]
>> [MUSIC]
[00:00:04]
>> Brian Holt: Big O, we talk about this first because we refer back throughout the entire course. And Big O’s the way that we analyze how efficient an algorithm is. And it's a mathematical concept that we borrow from computer science, because it's really helpful for us. And I think you'll see a lot of that today, that math and computer science obviously have a lot of crossover.
[00:00:26] But in particular as applied to algorithms, were driving all this from mathematics right. That is to say though that this is the mathiest we get today, so there's no derivatives. There's no integrals. This is just maybe algebra two-ish, maybe algebra one. Anyway, big O. So, big O is talking about the big picture, it's broad strokes.
[00:00:55] It's not the details, right? For example, if we have an algorithm that takes 300 milliseconds versus 330 milliseconds, we don't actually in this particular case, we don't really care that much, right? Cuz they're within a margin of error, a standard deviation right? We actually don't even really care that much if it's 300 versus 500 milliseconds, right?
[00:01:15] What we're actually much more concerned about is that 300 milliseconds or is it 30 seconds. We're caring about orders of magnitude type differences. So that's what Big O does, it basically allows us to suck away all of the minutiae, all the details, and just look at the really big picture here.
[00:01:36] So, I like to think of big O as just like a big vacuum cleaner that just sucks all the other less important information out of it. So again, this is the most math we're gonna get today. Just imagine this equation 3x squared + x + 1, right. So, if you plug in like ten there, right.
[00:01:56] You're gonna get 10 squared, 100, 300 plus 10, 310, 311. We'll just use the math I already have there, so I don't have to do math in my head. 75, if you plug in 5, 5 plus 1, so you gonna come out to like 81, excuse me, [COUGH].
[00:02:18] But as soon as we start plugging in huge numbers here, we're going to get obviously huge numbers, right? So that's going to be millions, billions, trillions. 75 trillion if we plug in the five million. The second's going to be five million and the last is going to be one.
[00:02:32] All this to say that we're demonstrating here is that this x squared is actually really where most of the value is coming from in this equation, right. To the point that we can essentially ignore what's going on here because they're just a flicker, or they're a drop in the huge bucket of the numbers that come out of here.
[00:02:50] So this is what big O does, it basically says I'm going to go ahead and ignore that stuff because it's not really going to affect that much what I'm going to do here.
>> Student: [INAUDIBLE]
>> Brian Holt: Yeah.
>> Brian Holt: So that's what big O is gonna do. It's gonna essentially allow us to ignore these smaller parts of the equation.
[00:03:14] So the big O of this equation would be O n squared because we're actually even going to ignore the 3. We don't actually even really care about the coefficients, right? Like I said, we don't care if it's 300 milliseconds or 600 milliseconds. We care if it's 30 seconds versus 300 milliseconds.
[00:03:30] So that's what big O is going to do for us and that's that's really just it. You're basically going to look for the biggest term which is the thing with the biggest exponent and say, okay that, that's the big O, right. That's essentially what's going on here.
>> Brian Holt: So big O is just absorbing all the other fluff.
[00:03:47] It ends up being just the biggest exponent essentially. Now there's way more that big O does if you go into mathematics, but we don't care, at least not today.
>> Brian Holt: And for the most part, we are gonna be talking about this in terms of time. So 600 milliseconds versus 60 seconds, but you can also use this for spatial analysis.
[00:04:10] So if an algorithm has to take up a bunch more memory, you can also use big O to analyze like this. If I sort this array, it's gonna take up four times as much space to be able to sort everything correctly, that you can also use it for that kind of spatial analysis.
[00:04:27] And we'll touch on that, but we're not gonna focus on it.