Big O Time Complexity

[00:00:00]
>> So for this first part, this is just going to be lecture, so you can kind of chill out for a second before we get into the big stuff. But I wanna introduce you to some tools that we're gonna use to look at algorithms. And again, if you're gonna be doing interviews anytime soon, this is gonna be something that you should really kind of get in depth on, probably more in depth than even that I'm gonna get on it.

[00:00:23]
But knowing how to talk about Big O is, I don't know I put that in air quotes, it's actually called Big O, anyway, let's talk about Big O is very important. So Big O is a way of talking about how efficient an algorithm is. And when I say algorithm, I'm actually meaning more in the mathematical sense.

[00:00:47]
We like to talk about algorithms in the sense of computer science, but algorithm is, I think, originally a mathematics term that we kind of just applied to computer science. You'll find that mathematics and computer science end up having a lot of crossover. That's also not to say that you need to be very good at math to be able to do this.

[00:01:05]
So if you don't have a math background, do not worry, this stuff can still make a lot of sense to you. A lot of people will say, I don't do computer science because I don't know math that well. Nothing I'm gonna do here today is going to be any worse than algebra.

[00:01:22]
Is that true? Yeah, we're not doing any calculus or anything like that, no algebra too, this is just college are not college algebra, but high school algebra level. So anyway, going back to Big O, Big O was this concept of taking a algorithm kind of zooming out and saying, just on a very broad stroke how efficient is this.

[00:01:44]
And that's useful because then we can kind of compare algorithms and broad strokes, and not get to mired in the details. So I like to describe the O part cuz it's a big open O, that is a vacuum that sucks out all the unimportant details and you're kind of left with the heavy, very important details.

[00:02:07]
So, allow me to get mathematical for just one second, 3x squared + x + 1. Just zoom in a second. So we have 3x squared + x + 1, that's a formula that maybe that describes how much time it takes for an algorithm to run. Where x is how long the array is, right?

[00:02:33]
So if I have an array of one, it's gonna be 3 times 1 squared, which is 1, + 1 plus, so it'd be 5, right? Now, if we try and plug in something like 5, the first term would be 75, and when I say term, I just mean the first thing between the plus signs, right?

[00:02:57]
That's the mathematics, which just means like 3x squared is one term, x is one term, and 1 is one term. So if we plug in 5 to the first term, we'd get 75, we get 5, and we get 1. So you can see this first term, it carries most of the weight of the algorithm, right?

[00:03:14]
So if I plug in, again, if I do 5 million, this ends up being the first term was that 75 trillion, the second term is 5 million, and the last one is one, right? So 75 trillion is so much bigger than 5 million and one, for the sake of Big O analysis, we can just ignore the plus x+1 because they don't really affect the final product so much.

[00:03:40]
I'm not worried about the difference between 300 and 303, I'm worried about the difference between 300 and 300 million. Does that make sense? I'm trying to just focus on the very broad strokes of this. So that's what Big O does, instead of saying that we have this complexity of 3x squared +x+1, we're just gonna say that we have the complexity of x squared.

[00:04:05]
Or they like to use n instead of x squared, so we're gonna say n squared. So the complexity, the Big O of this 3x squared+x+1, is gonna be n squared. So basically, the life hack here is this, you just look for the biggest term, right? So 3x squared would be the biggest term here.

[00:04:26]
And we even ignore the coefficient, the number next to it, so we just look at x squared, right? So the Big O of 3x squared +x+1 is just n squared, because that's gonna carry most of the weight of this particular algorithm. Now, why do we care? Why am I talking about math in this Frontend Masters Course?

[00:04:48]
You didn't sign up for a math class, and you certainly don't wanna take it from me. Well, we're gonna use the same methodology, we just applied it to math, but we're gonna now apply it to a computer science problem. So in particular, what we're gonna be concerned about the x that we're worried here about is this input.

[00:05:13]
This input is gonna be an array, right? And we're worried about what the difference is if I have one item in the array or if I have 100 items in the array or if I have a million items in the array. So this function here, crossAdd, all it does is it takes the beginning and the end and adds it together.

[00:05:33]
Then the second item and the second last item adds them together, the third, the last, and the third item and adds them together, right? So it kind of crosses each other to kind of make this crossAdd array. So here, I have this for loop that goes over the array and it just adds all the numbers together.

[00:05:58]
So the question you wanna be asking yourself is, how many instructions am I gonna give the CPU based on how long this array is? Well, the thing that you really wanna be looking at here is this for loop, right? Cuz this var answer equals array and this return answer here, those execute once no matter how long input is, right?

[00:06:22]
This would be like the plus two part of our equation up here, right? The +1, which is to say we can ignore it. But this here, this four loop, this is gonna happen more and more and more, depending on how long input is, right? So if this is 1, input is of length 1, right?

[00:06:42]
We give it the array of 0 inside of square brackets, that's only gonna take one four loop, right? It's only gonna go through this one iteration. But if this is of length 1 million, this four loop, this body here is gonna happen 1 million times, right? So you can see here this is getting stretched out, depending on how it's gonna be happen more and more.

[00:07:05]
So it's gonna take longer and more computational power to execute, depending on how long input is. So this is gonna be our most significant term in this function, right? So how many times is this for loop gonna happen? Well, it's gonna happen however long input is, right? That's how long this for loop is gonna go for, it goes for through input.length.

[00:07:30]
So this is gonna be of n, right? Or x, but we're gonna stick with n from now on. So the complexity of this is gonna be o of n, right? Does that make sense? Where n is just the length of the array. Here's the life hack here, here's where I'm burying the lead a little bit.

[00:07:51]
Just look for for loops, not just loops in general, right? So val loops would count as well. Just look for loops, right? So if you have a loop, that's gonna be n, if you don't have any loops, it's gonna be what we call constant, right? So that's gonna be Big O of 1, which means no matter how long the input is, it's not gonna take that much longer.

[00:08:13]
Now, you might ask, what if I'm doing a lot of things inside of this for loop? Does that affect it? Well, that would be like the three here and the x squared. It's a coefficient, Big O just ignores all of that stuff, right? We're just looking really for the loops.

[00:08:31]
Okay? How about this one here? You can cheat by looking down the page, but maybe just bear with me for a second and don't cheat. [LAUGH] Just find one here. So I have a needle, which will be like I'm looking for 5, and I have an array of 15 and I'm looking for wherever 5 is, right?

[00:08:52]
It's like a typical linear search in an array. So, I'm gonna loop through this and I'm going to look for the needle, and if I find that in the haystack, then I'm gonna return true. What's the Big O of this? Well, it might not go through the entire loop, right?

[00:09:10]
It actually might find it on the first thing. So if 5 is the first item in the array, and I'm looking at an array of 1 billion, it doesn't matter, it just takes 1 second, or one second, it definitely doesn't take, it takes a millisecond. What's that? Well, that's gonna be still Big O of n, because this short circuiting here, right?

[00:09:30]
Where we could just return true, that's still just a coefficient, right? So we're still gonna say n, keep in mind that it actually could be the last thing in the array, which means that we would look at literally either every item in the array to find it, right?

[00:09:45]
So if it was of length 1 billion, we will look at a billion things. So we're still gonna call this Big O of n. And what I'm trying to demonstrate to you here is there's a difference between best case scenario, worst case scenario, and average case scenario, right?

[00:10:00]
Best case scenario, first item in the array just finds the returns and you're done, that's called the best case scenario. The worst case scenario is, it is the last item in the array, and we'll take the entire array looking for it. So what's the average case scenario in this array?

[00:10:19]
Somewhere in the middle, like it'd be, like a half n, right? But again, Big O doesn't care, so we're still gonna say this is Big O of n, despite the fact that it could exit sooner. Does that make sense? Okay, I promise I'm gonna let you write code here in a second, you're not gonna be stuck listening to me lecture this entire time.

[00:10:41]
All right, so let's talk about this one here, I love asking people, how do you say this word? Is it tuples? Is it tuples? There is a correct answer and I don't like it. [LAUGH] I've always said tuples my entire life and I will probably continue to say tuples because it's just buried in my brain.

[00:11:00]
I don't know how to fix that. I believe the correct way to say that is tuples. It's not really a JavaScript concept, it's more of a Python concept in general, but the idea is, it's a pair, right? You have an array of length 2, right? And you have one first item and one second item, and that's a pair of values, and we call those tuples, tuples, whatever.

[00:11:26]
So what if I wanted to take an array and I wanted to make a tuple out of every single possibility in the array, right? So if I had an item that was or had an array here, an input of length three, then I would end up, I think, with nine items in the array, right?

[00:11:41]
Because I'd make every pair possible, right? Again, not something that you would typically do, but what is the Big O of this? And so, how did we get to this n squared kinda solution here? Well, we have this outer loop that's gonna run over every item in the array, and then for every item in the array, we're going to run through every item in the array again, right?

[00:12:09]
So if I have something of length 3, then it's gonna run 9 times, Ii I have length 4, it's gonna run 16 times, right? And you can see here, that number just keeps going up and up and up. If I have something of length 10, it's gonna run 100 times, right?

[00:12:23]
And it gets kind of out of control really quickly. So if input here was like, 500, right? This is gonna take a really long time. Which is bad, we don't wanna do that, right? So that's n squared. So how did we get n squared? Well, we have an outer loop and then we have an inner loop.

[00:12:43]
And when you see nested loops, then you can kind of assume n squared, right? And if you saw another one inside of here, another for loop inside of that, that would be n cubed, right? Or n to the third. There's not really any n cubed algorithms, and please don't write any [LAUGH].

[00:13:05]
That's kind of like a bridge too far. There are n squared, there's reasons to write n squared, but it's a, you wanna be pretty careful with that, cuz those n squared ones get out of control pretty quickly. But that being said, you and I are gonna write some n squared algorithms today.

[00:13:22]
>> It's best practice to avoid the n squared just to go for constant time complexity? And I guess, how are we gonna make that trade off? If this is further down the line then answer it then answer it then.
>> It's a good question and we're basically gonna be answering that question for the rest of the damn class [LAUGH].

[00:13:44]
But it's a super valid question and I'm glad you asked it. There's no right answer to it, right? The reason why there's no just one sorting algorithm in one data structure, that'd be a much shorter and better class is these algorithms are so fit for different problems that you're gonna have to choose.

[00:14:08]
They're definitely gonna be time to n squared algorithm is gonna be way better than a log(n) algorithm or n log(n). But anyway, things that are judged to be better algorithms are not always better algorithms, right? And I'm gonna show you that kinda, again, throughout the rest of the course.

[00:14:25]
Frequently, you're not gonna have a choice as well, right? Sometimes you just kinda have to do something in a really inefficient way because you wanna do inefficient things. And that's really what I want you to learn today is how to make that trade off in your head. And we'll yeah, we'll be making lots of examples, but I want you to continue to ask yourself that question throughout the rest of the course.

[00:14:47]
Cool, good question. All right, so let's talk about this one here, function get middle of array. What do you think the time complexity of that one's gonna be?
>> O(1).
>> There you go. So this is gonna be O(1), you can see it's written like that here. So array, this can be a very large array.

[00:15:17]
It could be of length a million, it can be of length a billion, but there's no loop here in the middle, we're just gonna go find the middle item in the array and then return that. So that's said to be O(1), or the way that you say that out loud is its constant time, right?

[00:15:32]
And I guess I should tell you how to say the rest of these, so O(n) squared, you would say this is quadratic time. You can also just say, O(n) squared, but people will call that quadratic time. And then here Big O of n, again, feel free to just say Big O of n, that's accurate and people say that, but you can also call this linear time.

[00:15:57]
I don't hardly ever say the word quadratic time out loud, I don't know why, but I will say linear time, and then I always say constant time. Basically, the question you need to ask yourself to find out something's constant time or not is, does this take more time if the array is longer?

[00:16:17]
And in this case, no, it doesn't, so we're just gonna say this is constant time. Okay, so let's zoom out here just a second. I kinda tried to give you a little bit of a graph of how this looks in terms of how many items in the array.

[00:16:36]
And I swear, I think there's only one more graph left in this course, there's not a lot more graphs. So if you have some PTSD from school from graphs, like I do, I swear there's not too many of them. But you can see here, this red line here, this is gonna be what it represents.

[00:16:57]
If I have eight items in the array, is still gonna only take me, let's just say that it's one millisecond to run this particular item, right? So no matter how many items in the array, it's a constant amount of time it'll take to run the algorithm. This blue line, we could say this is linear time, this is why it's called linear, right?

[00:17:14]
Cuz it's literally just a straight line that goes up. If I have six items in the array, it takes a constant amount of time. So we're adding just a constant amount over time depending on how many items are in the array. And this green one here, that's going up and you can see it's going up faster and faster, that would be quadratic time or Big O of n squared.

[00:17:38]
Because the more items we add to the array, it's gonna just take off and go, we add an exponential amount of time. Does that kinda make sense? As you might imagine, if I put Big O of n cubed, that's just gonna be basically a straight line up, right?

[00:18:12]
All right, so there's one I haven't talked about yet. We're gonna talk about it when we get to recursion, and merge sort, and quick sort, it's this purple line here, which is logarithmic time. And you can see here, it does go up if we add more and more items into the array, but it goes up at a very slow pace, right?

[00:18:33]
So the difference between doing it with 10 items versus 100 items versus 1,000 items, it does take longer to do 1,000 items versus 100 items, but not a lot more. And basically, we can use algorithms as kind of shortcuts to cut out pieces of the work. And by doing that, we kinda get an economy of scale, right?

[00:18:52]
So if we add like 10,000 things, it still is able to go fairly fast because we can do things in logarithmic time. And again, I just wanted to get that kind of in front of you before we got to recursion, so you can kind of see where that fit.

[00:19:09]
But I'll explain logarithmic Big O later in two sections, so just buckle up and wait for that. Okay, so that is really a summary of what Big O is. I'm sure mathematicians would have about two more hours that they'd like to talk to you about Big O, and I am not that.

[00:19:29]
This is in as much as I ever use Big O, which is, I'm trying to say here. I just gave you kind of a very surface level overview of what I think is useful for a computer science, like a web developer, to know about Big O, but there's a lot more there.

[00:19:45]
So I'm not gonna claim that I've taught you everything about Big O.