Big O Time Complexity

[00:00:00]
>> We're gonna first tackle Big O cuz I do feel like Big O is kinda that one thing that if you don't know it just means I'm gonna be saying a bunch of nonsense up here. And it just kinda sucks because then we keep talking about it you don't know what it is.

[00:00:12]
So Big O is the easiest way to put it is that it categorizes your algorithm on time or memory based on the input. It's not meant to be an exact measurement. So if someone someone's not gonna say your algorithm is gonna take 450 CPU units. You're gonna first say, well, what's the CPU unit?

[00:00:28]
And second, how did you come up with that exact number? Instead it's a generalized way for you to be able to understand how your algorithm will react as your input or the things you are using grow. And so if someone says, this is Of N, what they mean is your algorithm is a grows linearly based on input.

[00:00:49]
We'll go over some more. And so why do we use it well it often helps us make decisions on why you should or should not use a specific data structure. You will see as we do this data structures progressively make these constraints to make them more and more performant.

[00:01:05]
But if you use them incorrectly they become massively in performance, I don't I don't know what the opposite of performance is in performance, there we go. So here, we're gonna take a quick code example right here. For those who know Big O, this is a breeze you know it immediately.

[00:01:22]
So if you don't know Big O, this would actually be really hard. You wouldn't have a way to be able to kind of describe what is the running time of this code. You wouldn't actually have the lingo. So hopefully we can do that. We can get this lingo going.

[00:01:34]
To say it differently Big O as your input grows, how fast is your computation or memory grille? So that's the most important concept. Number one, growth is with respect to input. So just remember that, put that in your head. Obviously in the real world, this is not a real trade off in the sense that depending on the size of data you use, depending on how much memory you have to allocate depending on the GC pressure, these things are not necessarily free trade offs.

[00:02:00]
You can't really trade time for memory, because it takes time to create memory. So if you create a linear amount of memory in some sense your algorithm is bound by how much memory you create. So it's not necessarily for free. So let's go back to our example. So how does our program grow with respect to input?

[00:02:18]
Well, I conveniently named it n intentionally, but notice that it is a string. So it has a length and has a series of characters associated with it. Strings are effectively arrays really when you think about it. But anyways, so here we go. So if you look at the for loop, what you'll see is that the for loop has to execute the length of the string.

[00:02:36]
That means if our string grows by 50%, how much slower is our function, 50%. It grows linearly. For every one more unit of string, there is one more loop that it has to do. So there you go, that is the simplest way to put it. And for those who did not see that, it's not very obvious, but for me, that's over, and you can see it right away.

[00:02:58]
So how can you tell, simplest trick and all of it is just simply look for loops. Where do you loop over the input? If you see that, easiest way to kind of tell, the Big O complexity of anything, right? So when we look at this, you'll notice that I now put a new function and we have a function that goes over and sums all the things that are happening here in this string, and then we do it again.

[00:03:21]
What's the running time of this function, anyone?
>> Of N.
>> Okay, we got one Of N, anything else cuz we do a sum and then we do some again. I was really hoping can someone just say 2 of N, 2 of N hanging on Of 2 of N, okay, you're right.

[00:03:37]
What's the running time? Right, no it's not that. It's actually not that at all. Second most important concept is you always drop constants, the reason why is here's a very good example of why you don't care about constants. Though practically speaking constants are extremely important. Theoretically they're not important, if you had something that grew at 10N versus N squared, you'd clearly see as we get down here N squared just gets massively larger.

[00:04:02]
It grows disproportionately fast in comparison to no matter what constant is in front of the linear Of N. So yeah, that is why constants aren't necessarily important cuz again, we're not trying to get exact time. We're not trying to get this is how many units of CPU you need to use.

[00:04:19]
It's how does it grow? If I'm gonna give this thing 10,000 as N, is it gonna hold my computer or am I gonna be able to do it fast? Is it going to be instant? I need to kinda just generally know where it's gonna be. And so that's kinda the heart of Big O if you will, all right?

[00:04:36]
And I've talked about this, right practical versus theoretical. Yes, Of N is faster than Of N squared. But just like in sorting algorithms, often it will use insertion sort for smaller subsets of data. Because insertion sort, though slower in theoretical terms, cuz it's N squared, is actually faster than say quicksort, which is log of N when it comes to small, datasets.

[00:04:58]
Because practically speaking, sometimes things that are N squared or faster than N, right? Because your N is sufficiently small. And the constant that is dropped is larger enough that it actually makes real impact. All right, so let's do another example right here. We're gonna go over the entire length of the string.

[00:05:14]
And if we happen to run into a capital E, we are gonna return whatever we have at that moment. And so what is the running time of this algorithm?
>> Of N.
>> Of N would be correct, good job. The reason why we do that is that often we consider worst case.

[00:05:36]
And so when you're in interviews you're gonna pretty much exclusively describe worst case. And if you think about it a string without a Capital E, how much of the string are you gonna go through? Well, you're gonna go through all of it. A string with a capital E at the end or maybe one unit from the end or two units from the end, you're gonna get big O of N minus 2.

[00:05:53]
Well, that's just simply N, we drop all constants there you go. It's always N because it doesn't matter where that E is. Practically speaking it could be in the middle it could be at the end. And if it's one half N still again it's just N. So the three important concepts I want to drive home for time and space complexity are these, growth with respect to input, constants are always dropped.

[00:06:16]
Whenever you're pretty much doing in an interview, it's worst case scenario, rarely are they gonna ask you for best case or even average case. Now there are some algorithms that it makes more sense to reason about the best case and the average, case and we will go through some of those today because they actually change and there actually is a variety of runtimes for him.

[00:06:35]
But, at least whenever I've done interviewing, I have never once been asked for best or average. And I've conducted about 200 interviews and I've been in about 50 interviews I've never had it. So I just assume most people here aren't ever gonna happen. So here's some common complexities you will see.

[00:06:53]
You got right down here in the ones that you can't really see there's actually two lines right here, which is Of 1, which means constant time. Doesn't matter how big the input is, it does the same set of operations every single time it's instant, effectively. Now that constant, that's in front of the one, can be a very large number but it doesn't matter cuz it's the same constant no matter how big the input is.

[00:07:15]
Then there's log of N, that's base two log for those that forgot what log means, don't worry I failed it on my ACT. I'm sure we all forget it at some points but we'll kinda go over it more log of N being the screen line. You can see it grows linearly even though this graph is rectangular.

[00:07:32]
So it doesn't look very linear, log of N very common running time, you'll see. N squared, you can see that it starts becoming kind of ridiculous. It grows pretty fast. And the last two are effectively algorithms that can't run on traditional computers. I don't know if it can run in the quantum realm cuz I'm in the quantum realm is practically magical as it is.

[00:07:51]
So whatever realm that is I don't know about that but traditionally speaking, you can't solve the traveling salesman for 12 cities. That is a algorithm that runs in the last two time range, right? It's just effectively impractical on a computer, will take thousands of years. All right, so, let's go over some more examples.

[00:08:09]
Again, I said count the loops. So N squared, for every single character in the string. We're gonna go over every single character in the string. That is like computing the area of a square, right? N by N, it's just a square we're going over. We're just going down each single line.

[00:08:26]
You can think of it kinda like graph that you're going over. So for every single character we go over every single character, same thing for cubed. For every single character we go over every single character every single character we won't pretty much see any of these type of algorithms today but that's like multiplying a matrices, right?

[00:08:43]
If you just simply multiply matrices together two of them you're gonna get N cube like algorithm. Because you have to do this every single time. And then you'd have to do that a bunch more times. It's very painful. O(n log n), we will see some O(n log n) and some O(log n) algorithms quick sort is one.

[00:09:02]
It'll make more sense once you look at it but effectively how you think about it is that for every time, you go over. Half the amount of space you need to search, but you need to search the whole space once for every time. So, you go over n characters, then you have how much you need to do, then you go over n characters you have how much you need to look at.

[00:09:20]
And you just do that cuz that's kind of how I think about. And then of course log n, you just have the amount of input you have to search, but you only need to look at one point at a time. And so it eventually goes down to zero.

[00:09:30]
All right, and then we'll also see the craziest of all runtimes today once. I've only seen this in one problem once very excited about it. Have scored of N, yes, I do math.square root as squirt. I think that's fantastic. But a score of n it's a very unique one.

[00:09:47]
And I think actually it does show a mind blowing trick that you can do. All right, so why so obviated, of course, we don't need yet another Big O explanation. I just wanted to make sure we're all on the same page. Cuz again, the algorithms in this course are the important part.

[00:10:01]
It's not necessarily the Big O. I'd rather have you have the technical understanding of algorithms than be able to tell me the running time. The run time once you kinda get the trick look for loops, okay, I can see how we're going over input, it's easy after that.

[00:10:16]
Long as you keep these three concepts in your head, growth with respect to input, constants are dropped, consider worst case, you'll do well in an interview. Long as you can kinda qualify okay, here's where my loops theoretically are, we're good to go. One more note, there are other things that measure time complexity other than Big O, just people don't use it right?

[00:10:33]
They're Stata, there's little omega. There's all these other ways, but Big O is the upper bound. The effectively the least upper bound you can do. All right, space, the final frontier, we are not gonna really be talking much about space growth. I will mention it from time to time.

[00:10:49]
It's just less interesting. I've gotten it once or twice in an interview. But the reality is that people do this in react, which emotionally bruises me. And so when I see this I just assume people don't care necessarily about space or time sometimes. And I care about it but I can't do anything about it.

[00:11:09]
This may not be the popular way to do it anymore, react to changes too fast for me to keep up with it. I don't really do a lot of front end stuff, so anyways before we go, questions.
>> What is your favorite algorithm.
>> My favorite algorithm to implement is probably quicksort.

[00:11:23]
And I'll explain why. Cuz I think it's just super duper neat, practically speaking I think a ring buffer is just. It just always is awesome. And then you can replace a ring buffer with an array list if you don't need first in first out behavior, right? Everyone agree?

[00:11:46]
By the end of the course, you will agree with me because then you'll understand what I'm saying here. In fact, by the end of today, you should be able to understand what we're talking about, yap
>> If I don't know, TypeScript, can I follow the course?
>> if you don't know TypeScript, can you follow the course?

[00:12:03]
Well, I chose TypeScript because the, a, the typing language is very straightforward. We're not gonna do a ton of type script. So if you know JavaScript, you know TypeScript, except for, you'll see a, kind of some foreign characters in some unique positions. But it's really the types that are important.

[00:12:18]
And so I really wanna make sure I can type out the types so you can see it. And I kinda created a nice little project in which we will all practice typing out algorithms together and that one is going to be in TypeScript as well and there's a reason why I chose that for just the technical reasons of TypeScript as well.