Brian demonstrates how to calculate Big O on a few functions. When a loop is present, the Big O value is typically related to the number of iterations required by the loop or the number of nested loops. If a function simply returns a value without any iteration, the function would have a Big O value of 1 or “constant time."
(upbeat music) - So we have this function called the cross add. So if I have an array of like... Oh come on. Of like one, two, three, right? It's basically going to reverse the array and add it to itself. So it's gonna end up being something like, one plus three, which is gonna be four, four, well four, oh good job Brian you got it.
I didn't mean to do that, but... Basically, it's gonna add one to three, then two to two, and three to one. So it's just gonna do that very useless algorithm. But let's talk about what the big O with that would be. Well for everything that we get into input, for whatever input's length is, 'cause input's gonna be an array. It's gonna touch everything once. And we're doing other things, you could figure out the coefficients by adding like how many instructions are we doing per loop, but we don't care.
This is about broad strokes now. (clears throat) Excuse me. So the broad stroke here is that, we're gonna do one loop over everything, which basically says that it's gonna be N. So for every length, we're gonna go over it once. You can say here that the big O is N. Because we go over everything once. That makes some sense, right? Pretty simple so far.
So let's talk about find. So we have needle in a haystack haystack would be an array and needle would be whatever you're looking for in the array. So here, we're gonna loop over it, and if haystack equals needle, then we're gonna return true. Pretty simple algorithm. So what would the big O be here, right? Well potentially if it's the first, if the needle is the first thing in the haystack, it could just be instant return, right? However, we're still looking at broad strokes here, we don't actually, this would be like half, or a quarter end, right? But we're stuck with those unimportant details and we're still gonna say this is N.
In other words, we're still mostly looking at the worst case scenario. And the worst case scenario would be the last thing and we'd have to go through the entire array. So this is still O(n). Even if you're short circuiting, we're still have the potential to loop over everything and thus we're gonna say it's big O(n). Okay, so... Let's look at this one right here. Make tuples or tuples, depending on who you ask how to say that. I internally say tuples because that's what I hear everyone else saying.
And the basic idea here, is, let's see... If I have something like... Come on. One, two, three, right? If I have an array like that, basically I'm gonna make every combination possible of an array of arrays. So I'm gonna do one comma two, then I'm gonna do one comma three, then I'm gonna do two comma one, actually I think it'll even do like two comma two, right? Whatever.
Something to that effect though. (clears throat) So it's gonna loop over everything, and then create these tuples for us. So, the question here is like, what is the big O of this? Well, we have one loop and then inside of that loop, so basically, we go to one in this array, and then inside of that loop, we're going to loop over everything again inside of that loop. So we're gonna do one on our outer loop and the inner loop's gonna do one, two, three, then we're gonna do two and then on the inner loop we're gonna do one, two, three again.
So now you have to be thinking about, like, okay well how many times am I gonna be looping over it? Well, the answer is, is we have an outer loop and we have an inner loop, which means that we're gonna be N squared, right? And I hope you've seen the trick, alright? There's nothing more to the trick that this, you just look for loops, right? So every time you see four or wild nested or something like that, chances are that's gonna be, almost unexceptionally, that's gonna be your answer right there. So you just look for nested loops. So if I have a four loop, within a four loop, within a four loop, it's gonna be N cubed.
And so on and so forth. Also if you have a N cubed algorithm, you're probably doing something wrong. I'm just throwing that out there, there's very rare occasions where that's appropriate. That basically it right here. We're just looking for nested loops because that's, 95% of the time, what's gonna add the most time to what you're doing. Something else worth mentioning. So, if you have no loops and if you just do something in return that's said to be constant time, or o(1).
But you'll always hear that just said constant time, and I'll be saying that ad nauseam as we go forward. So, that's what I mean. Basically means there's no loops in your code. We're also gonna see o(log n). When we start getting to recursion and recursive algorithms. Basically if you're playing recursion or recursive strategy, any sort of like divide and conquer, which again we'll talk about here in a little bit. It's just gonna be log N. That's basically saying that, as you add more and more elements to whatever you're doing, it's going to take a less and less time per item that you're adding to the list.
So, you know maybe the first ten take me ten and then the next ten take me five seconds and the next ten take me two and a half seconds. So it's a diminishing adding of time. And that's what logarithmic time means. Yeah, the input diminishes. And that's gonna be mostly like merge sort and quick sort and dealing with trees as well, that we'll see these recursive log N's. - [Woman] We've got a question online. - Sure.
- [Woman] Do you have it or do you want me to read it to you? - Go ahead. - [Woman] Okay. Is it fair to say that if you had to loop over the array twice, you could have O two N? Or would that still be reduced to O N? - That's a great question. Who asked that? - [Woman] Brody Y. - Brody Y, okay. So the answer to that question is, you would be adding a coefficient right, but as we saw with before like three X squared plus X plus one, we just dropped the three. So that O is pretty aggressive and sucking away all of the other terms.
So we would still say that's O N, even if you have like four loop and then another four loop underneath that and another four loop underneath that, We're still only, we're adding coefficients we're not actually adding terms, exponential terms. But that's a great question.
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