Big O is a method for analyzing the efficiency of algorithms. In an equation, Big O may represent an exponential value since it’s the largest term in the equation. All other insignificant coefficients are ignored.
- So, Big O. We talk about this first because we refer back to it throughout the entire course. And Big O is the way that we analyze how efficient an algorithm is, and it's a mathematical concept that we kind of borrow for 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 but in particular as applied to algorithms, we're 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 an algebra two-ish, maybe algebra one, so.
Anyway, Big O. So, Big O is talking about the big picture, it's broad strokes, 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? 'Cause they're within, you know, a margin of error, standard deviation, right? We actually don't even really care that much if it's 300 versus 500 milliseconds, right? What we're actually much more concerned about is it 300 milliseconds or is it 30 seconds, right? We're caring about orders of magnitude type differences, right.
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. So, I like to think of Big O as like 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 you are gonna get today. Just imagine this equation, three X squared plus X plus one, right? So, if you plug in like 10 there, right, you're gonna get 10 squared, 100, 300 plus 10, 310, 311, right? Well, we'll just use the math I already have there so I don't have to do math in my head.
75, right, if you plug in five. Five plus one so you're gonna come out to like 81. Excuse me. But as soon as we start plugging in huge numbers here we're gonna get obviously huge numbers, right? So, that's gonna be millions, billions, trillions, 75 trillion if we plug in five million. The second one's gonna be five million and the last one's gonna be one, so all this is to say that we're demonstrating here is that this X squared is actually really where most of the value is coming from within the equation, right? To the point that we can essentially ignore what's going on here because they just, you know, a flicker or they're a drop in the huge bucket of the numbers that come out of here.
So, this is what Big O does. It basically it says I'm gonna go ahead and ignore that stuff 'cause it's not really gonna affect that much what I'm gonna do here. (man mumbles) Yeah. Right, so that's what Big O is gonna do. It's gonna essentially allow us to ignore the smaller parts of the equation. So, the Big O of this equation would be O N squared because we're actually even going to ignore the three.
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. So, that's what Big O's gonna do for us and that's really just it. You're basically gonna 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. So, Big O is just absorbing all the other fluff, and it ends up being just the biggest exponent essentially.
Now, there's way more than Big O does if you go into mathematics but we don't care, at least not today. And for the most part we're gonna be talking about this in terms of time, right? So, 600 milliseconds versus 60 seconds but you can also use this for spacial analysis, right? So, if an algorithm has to take up a bunch more memory, right, 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 store everything correctly, right? And you can also use it for that kind of spacial analysis, and we'll touch on that but we're not gonna focus on it.
Note: This course was created by Frontend Masters. It was originally released on 07/12/2016. We're pleased to host this training in our library.
- Big O
- Sort: Bubble, insertion, and merge,
- Median values
- Set, map, stack, and queue
- Array lists and linked lists
- Binary search tree
- AVL tree
- Single rotation and double rotation
- Hash table
- Functional programming
- Map, reduce, and filter