Big-O

[00:00:00]
>> Now we get to some knowledge and we're gonna have different knowledge portions of this course. I want to start with Big-O because it's something that is a little misunderstood. I don't know if it should be hyphenated or not. I believe it hyphenated cuz it looks cooler. Big-O, I mean, what is Big-O?

[00:00:18]
Someone tell me, and this will come up a lot. Some of the questions I'm gonna ask you, I'm going to say, what's the Big-O of this function you just wrote? Yeah.
>> I can try. Big-O notation is kinda of like the formula that you use to determine how long something's gonna take, like a problem.

[00:00:37]
Or actually I've only used it as a problem, I've never used it for anything else, I don't know if you can. So,
>> Yeah, well but it's the longest amount any function is going to take, given the worst case scenario of input. It's important to know as engineers, as computer scientists, we should know Big-O.

[00:01:00]
Because you're thinking, my function that, I don't know, my function that I wrote, that it has for-loops in it. I only have 100 elements to iterate over, fine. But if you write things that take billions of elements, then you see that time creep up, and creep up, and creep up.

[00:01:17]
Knowing Big-O is really important. But because it's trying to masters, I want you to master all the Bigs. Big Omega, Big Theta, Big O. You don't have to know Big Omega and Big Theta. I think it's just called knowledge to have because most people say Big O, we know it's a thing.

[00:01:35]
But there's Big Omega. Big Omega describes the best case scenario, the operational complexity of the ideal case of your input. If all things go well, it's gonna run really, really quickly, and that's the best case. Big theta is the average case. Well, on average, or the precise case, it's gonna run at this complexity, this time.

[00:02:00]
And big O is the worst case. And you're thinking, why are computer scientists so pessimistic, they only care about Big O? Yes, it's awesome when things run on Big omega. But generally, we care about the Big O time, because we wanna know about the worst-case scenario. What is the slowest possible thing that can happen in this function?

[00:02:19]
So in this case, this search function which just iterates over an array, and if it finds whatever number it's looking for, it's gonna return true, if it doesn't find it's gonna return false. So the best case with this search function because I have one for loop, which means I'm iterating over the elements one time, but I return early.

[00:02:38]
So the best case is element zero. Element at index zero is the thing I'm looking for, we're going to turn true. So, we're gonna say that's Big O one or Big omega one, which is constant time. It's gonna return instantly. And it doesn't matter how many elements are in our data set, it doesn't matter if it's a billion or a trillion or a gazillion.

[00:03:01]
I'm not sure if gazillion is a number, but it doesn't matter if the first element is the thing we're looking for, it's going to return immediately so it's constant time. Big omega. Big theta is the average time. On average, we'll probably have to iterate through the entire array or we'll say on average we're gonna have to iterate through half the array.

[00:03:21]
You follow? Like if we had a giant data set on average, we're gonna have to go through half of it to find the thing we're looking for in an evenly distributed data set. So that's actually Big data n over 2 cuz that's half of the elements we're going to iterate over, but we always drop those extra numbers so it's just big data n.

[00:03:39]
And n is of course the number of elements you're traversing, or the size of data set. It can mean a lot of things, but it's generally time or number of elements. So big data on average n over 2 which we just could call n. The Big O case is also n.

[00:03:54]
So let's say that's the return false case. You didn't find the element all of you are looking for, at the worst case, we're gonna have to iterate through the entire data set, the entire array. And it's like the thing we're looking for isn't there, cool. So in the very worst case of this function, we're going to say it's Big-O n, hopefully that helps with Big-O a little bit.

[00:04:16]
I know it's intimidating cuz people be like, a tree to access its login or they'll just throw out numbers that you expect to memorize. But instead of memorizing it's better to really take these to heart. I'll show you the trick, I'll show you the Jem trick at the end for figuring out big-O and when you say you're like, that makes sense.

[00:04:33]
Hopefully if I'm doing things right. And we care about big O because I can say, it's big-O 2n or big O n squared, that doesn't necessarily mean anything, when you look at a graph of how long things take to run, so don't think 10 or 100, think a billion elements, that timing complexity adds up.

[00:04:53]
So big -O n factorial is the worst possible time. Factorial is say, so that's the bang sign, or exclamation point, whatever you wanna call it. So factorial 4 would be 4 times 3 times 2 times 1, that's factorial. That's the worst possible time. It's very unusual, if you write something, to get big O factorial time.

[00:05:15]
But just don't, your function will pretty much never finish, it'll just get worse and worse. 2n, n squared, those are all terrible running times you want to avoid things like that. We get to a little bit reasonable times, we get to n log n. So the trick and I won't go into what logarithmic means, but the trick is think if you're iterating over a data set, and every time you iterate, you're reducing the number of elements as in you're filtering the number of elements you need to iterate over.

[00:05:46]
That's going to be log time every time. So giving a good example of log time. We'll get some examples that are log time, trees, funny element as a tree is log time because trees are ordered. So I look here and I say, on let's say a binary search tree.

[00:06:05]
Is this element bigger or smaller, I'm gonna go left. Bigger or smaller, go right, go left or right. So, and no time iterating over the entire tree to find the thing I'm looking for, that's why it's log time, because every time I'm reducing the number of possible matches.

[00:06:19]
Big O n, that is kind of the base case, that means we iterated through the entire data set to do whatever we're trying to do. That's gonna happen a lot. Generally, you see it as a for loop reiterating over the entire dataset. Worst case scenario, that's probably the most common case.

[00:06:39]
Log n is, like I said before you're reducing the number of elements that are between log n and n is, I'm going to have to iterate over the entire data set. But as I do every single iteration, I'm going to narrow down what I'm looking for. And log n, it's not great.

[00:06:56]
It's not terrible soccer. It's somewhere in the middle there. What you're always striving whenever you're writing any sort of algorithm you want log n time cuz that's fast, that's short of constant time which is bigger than 1, which means it doesn't matter what we're doing it's always gonna return to the same time.

[00:07:11]
It doesn't matter if they're billion or trillion, quadrillion it's always gonna return the same time. But it's pretty hard to write things in constant time, so log n. I know I'm saying a lot of like computer sciency terms, but a lot of companies will ask you, what's the big O time?

[00:07:26]
The cheap is looking at something like this and understanding, okay, forget big omega, big data, they're fun to know. And if you throw that out, I'll be like, woah, this person is pretty smart. They're smarter than me. I wanna hear what they have to say. But the trick I use is looking at number four loops looking at number of loops, and that's like the cheating way.

[00:07:47]
So, if one for loop is big-O n, what's the big-O of this?
>> n to the third.
>> Yes, n cubed, n to the third. Because we're iterating over and then every iteration we have to iterate over again, and then every one of those iterations we iterate over again.

[00:08:05]
So going back, Yeah, we're out here, n squared, n to the third, as you get n to the 10 whatever, you kind of get here but you'll never get to this line really. And that's the trick, it's a simple trick. So apply that to things that are loops that don't necessarily look like it.

[00:08:26]
What's the big-O of this?
>> n cubed?
>> Yes, n to the third again, it's count the loops, every loop you're iterating over, you're iterating over. There's no special, well actually, that's my Jem tip, count the loops. It's a little tricky sometimes and I make it seem straight forward in these examples, but generally have some idea of the Big-O time.