This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Finding Big O" Lesson
[00:00:00]
>> [MUSIC]
[00:00:04]
>> Brian Holt: We have this function called a cross out. If I have an array of a bar of 1, 2, 3, right. It's basic code, I'm going to reverse the array and add it to itself, so it's going to end up being something like 1 plus 3, which is gonna be 4.
[00:00:26] 4, 4, well good job Brian you got it. I didn't mean to do that but basically it's going to add 1 to 3 and 2 to 2 ,and 3 to 1, right? So it's just going to do that very useless algorithm. But let's talk about what the big old that would be.
[00:00:45]
>> Brian Holt: Well for everything that we get into input for whatever input length is because it input can be an array. It's gonna touch everything once. And we're doing other things that you could add. You could figure out the coefficients by adding how many instructions are we doing per loop right?
[00:00:59] But we don't care right? This is about broad strokes now.
>> Brian Holt: [COUGH] 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 end. So, for every length, we're gonna go over it once. So, you can say here that the big O is M, because we go over thing once, it makes some sense, right?
[00:01:32] Pretty simple so far. So let's talk about Find, right, 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.
[00:01:52] Pretty simple algorithm. So, what would the big O be here? Well, potentially if it's the first, if the needle is the first thing in the haystack, it could just be instant return. However, we're still looking at broad strokes here, and this would be like half or a quarter n.
[00:02:10] But were sucked in with those unimportant details, we're still gonna say this is n, in other words we're still most looking at the worst case scenario and the worst case scenario it would be the last thing right. We'd have to go through the entire array. So this is still O(n).
[00:02:24] So even if you're short circuiting we'll still have the potential to loop over everything and that's when I say it's a big O(n). Okay, so let's look at this one right here make tuples or topples, depending on who you ask how to say that. I generally say topples because that's what I hear everyone else saying.
[00:02:46] And the basic idea here is, let's see.
>> Brian Holt: If I have something like.
>> Brian Holt: 1,2, 3, if I have an array like that, basically I'm gonna go and I'm gonna make every combination possible of array of arrays, right. So I'm gonna do 1,2. I'm gonna do 1,3 and then, I'm gonna do 2,1.
[00:03:23] Actually, I think it'll even do like 2,2, right, whatever. Something to that effect though.
>> Brian Holt: So it's going to loop over everything and then create these these topples for us right. So the question here is what is the big O of this? Well we have one loop and then inside of the loop, so basically we go to one right 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 then the inner loop's gonna do 1,2,3.
[00:03:59] Then we're gonna do 2, and then on the inner loop we're gonna do 1,2,3 again, right? So now you have to be thinking about like, okay, well how many times am I going to be looping over it? Well, the answer is, since we have an outer and we have an inner loop which means that we're gonna be n squared.
[00:04:14] And I hope you've seen the trick, there's nothing more of the trick than this, you just look for loops. So every time you see for a while 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, if I have a for loop within a for loop within a for loop, it's going to be end cubed right, and so on and so forth.
[00:04:36] Also if you have a end 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's basically it right here. We're just looking for nested loops, because that's 95% of time what's going to add the most time to what you're doing.
[00:04:56] And something else worth mentioning. So if you have no loops and if you just do something in return that's had to be constant time. Because or 01, we always hear just said constant time, so and I'll be saying that ad nauseum as we go forward so. That's what I mean.
[00:05:15] This could 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. And basically, if you're playing recursion a recursive strategy any sort of like divide and conquer, which again we'll talk about here in a little bit.
[00:05:36] It's just gonna be be a log n right, and that's basically saying that as you add more and more elements to whatever you're doing it's going to take less and less time per item that you're adding to the list, right? So if maybe the first ten take me ten and then the next ten take me five seconds to the next ten take me two and a half seconds, right?
[00:05:54] So it's a diminishing adding of time and that's what logarithmic time means.
>> Brian Holt: Yeah, to the input dimension. So and that's going to most of like merge sort and quick sort and dealing with trees as well that will see these recursive logins.
>> Speaker 2: We've got a question on line.
[00:06:16]
>> Brian Holt: Sure.
>> Speaker 2: Do you have it or do you want me to read it to you?
>> Brian Holt: Go ahead, you read it.
>> Speaker 2: Okay, is it fair to say that if you had to loop over the array twice, you could have O 2n or would that be written still be reduced to O n?
[00:06:31]
>> Brian Holt: That's a great question. Who asked that? Brody?
>> Speaker 2: Brody Y.
>> Brian Holt: Brody Y, okay. So the answer to that question is you would be adding a coefficient, but as we saw before with the three x squared plus x plus one, we just dropped the three. So that O is pretty aggressive and sucking away all the other terms.
[00:06:51] So we would still say that's O n, even if you have like for loop and then another for loop underneath and another for loop underneath. We're still only, we're adding coefficients aren't actually adding terms or exponential terms right. But that's a great question.