Big O Notation

[00:00:00]
>> Bianca: So what if we had multiple expressions or we put them inside of a loop, like how do we reason with a function that, in the function body, has multiple expressions? And so the way I think about it is if you have multiple expressions that are not inside of a loop, I just add them together.

[00:00:21]
So if we have a bunch in constant time, I would just say like 1 + 1 + 1 equals three. However, if these things get put inside of a loop then you start to multiple it. So, if you have a loop inside of a loop right, we have n, a loop is linear, right?

[00:00:38]
We talked about that. And if we have a loop inside of a loop it's n times n, which is then quadratic. If we have three loops n times n times n. However, we also need to think about what is going on inside of those loops. So if inside of the loop we're doing like recursion, that can add some more things.

[00:00:58]
And so depending on the time complexity of that method that you're calling, you need to just multiply it by n inside of a loop. Otherwise, just add it.
>> Bianca: Does that make sense? Questions about this?
>> Bianca: Okay.
>> Bianca: Okay, so what about O(logn)? So logarithmic time, so we do not really talk about logarithms anymore after like,I don't know, high school or something.

[00:01:39]
Unless you're a scientist, I guess logarithms are really important if you deal with like really big numbers or really small numbers. Which is what we do if we're analyzing large sets of data. I'm not gonna teach you logarithms right now, but all you need to know really is that logarithmic times, so logarithms can have a different bases.

[00:02:00]
You can have base 10, you can have base 2. And you can think about, as your input increases, the work, or the number of operations that need to be done, decreases by a fraction. So commonly, if you are looping through an array, you have a loop, and then every time you loop, you cut your problem in half.

[00:02:24]
That is going to be a logarithmic time. So every time you loop, you only have to do work on half of your dataset. Or a third, or some fraction, right? So logarithmic can be some fraction, so. Base 2 will be divided by 2. Base 3, 3, 10, etc.

[00:02:40]
So as it increases, the time complexity increases at a fraction, so it grows really, really slow, which is good. Which is why it's pretty close here to constant time, and it's often better than linear time when we have a large enough datasets that we care about, this kind of stuff.

[00:03:05]
So that's what you need to know about logn. Cool, and then there's also nlogn. Nlogn happens when you have a linear loop, and then you're also looping and cutting it in half, so linear, and then you're cutting it in half. And you multiply them together to make nlogn.

[00:03:29]
And we'll see an example of that later. So you'll put some examples to these vocab terms. Okay, questions?
>> Speaker 2: So you mentioned different bases and how is that determined, is it base 2 or base 10, is that-
>> Bianca: It's what have you divide it by, so if you are dividing your input by 2, then it's base 2, if you are dividing it by 10, it's base 10.

[00:03:49]
Typically you're gonna see it divided by 2, mostly.
>> Speaker 2: Like a binary search?
>> Bianca: Yeah exactly, binary search, anything where you are cutting it in half. Okay, so here's a little table to help us have some reference. So if we're just running a statement, returning a value, for example, this cost of time, any sort of value you look up, array object.

[00:04:17]
Variable is gonna be a constant time, again, with the needle just going directly to where it is in memory, easy. So loop, you can think of this as loop that cuts a problem in half every time. n is just gonna loop through all of them. So anything where you have to like look at everything at least once is gonna be at least n, right?

[00:04:38]
So n squared there's gonna be double nested loops and we have triple nested loops of n to the 3 or n cubed. So just a word of caution, I'm giving you some tools to make rough estimations here. This is not the full version of how to calculate time complexity.

[00:05:00]
Which is deeply mathematical and really out of the scope of this workshop. But what you need to be mindful of is what is n. Because you're gonna have a lot of different data points in your methods, in your algorithms. And so, you wanna make sure that you're identifying what is the dataset that's growing.

[00:05:18]
And if you have more than one dataset that has a variable length, you're gonna need to take that into consideration. That's something that when people get started with this, they just assume that n is always gonna be the length of the array. Or n is always gonna be a certain input, and it's not necessarily so.

[00:05:32]
You need to really think about how your code is executing and what is changing as your input changes.
>> Speaker 3: Can you provide a concrete example?
>> Bianca: Of what exactly?
>> Speaker 3: What you were describing.
>> Bianca: Of what I was describing. So like I will in future our slides.
>> Speaker 3: Okay.

[00:05:51]
>> Bianca: Yeah, yeah, yeah. Yeah, and when we go through it, I'm going to ask you, okay, what exactly is n here? And we're going to think about like, what are the things that are changing? Because that's one of the common mistakes, is assuming that n is a particular thing when it's not necessarily a particular input.