Data Structures and Algorithms in JavaScript Calculating Big-O of Loops

[00:00:00]
>> Bianca Gandolfo: So my next question I'm posing to you is, so what if we have multiple expressions, loops, etc. So we're looking at time complexity of individual operations, so let's talk about how do we combine that? It's gonna take a little bit of math and I'll give you a rule of thumb, right.

[00:00:19] You're either gonna multiply something, or you're going to add something, for the most part, for the most part. You're gonna add things when they're next to each other but they're not in a loop if they're inside of a loop that might hint to you that it's multiplication, okay.

[00:00:37] And then again we're just doing estimations here this is not exact math. Cool. So, whatever, blah, blah, blah. We have some for loop here.
>> Bianca Gandolfo: So, Christina asks would it be helpful for interviews to memorize all JavaScript native methods and it's time complexities. I discourage memorization. I actually just encourage you to understand how they work.

[00:01:07] And then be able to figure out the time complexity from there, because there's no way that you're gonna be able to memorize everything. And so, what you wanna do is understand the underlying mechanics, so that you can calculate it on your own. Good question.
>> Speaker 2: Sorry, what makes a method native?

[00:01:27]
>> Bianca Gandolfo: It comes for free with JavaScript.
>> Speaker 2: You didn't have to add a library or anything?
>> Bianca Gandolfo: Yep, yep, yep.
>> Bianca Gandolfo: Yeah, so there's native methods and then there's like browser methods. There's methods that come from a library, methods that you wrote yourself, yeah.
>> Speaker 2: Thank you.
>> Bianca Gandolfo: Yeah, good question.

[00:01:53] All right, so, i'll return. Let's just do 1 + 1. All right, so what's our time complexity here?
>> Bianca Gandolfo: So, here we are combining some stuff. 1 + 1 what's our time complexity of that expression?
>> Speaker 2: Constant.
>> Bianca Gandolfo: Yeah so O of 1. And then what about our loop?

[00:02:38]
>> Speaker 2: It's linear, I'm thinking it would still be. Linear because it, even though, cuz what you're doing inside the loop is constant.
>> Bianca Gandolfo: Mm-hm, yeah, exactly. So we have that. We're gonna guess that that's linear time. Take a guess. Let's look at something similar. And see how it compares.

[00:03:03] So everyone understand my notation here? My pseudo JavaScript?
>> Bianca Gandolfo: I don't know.
>> Bianca Gandolfo: No.
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: What's going on here? So what's this?
>> Speaker 3: Was constant, but then you have a nested loop.
>> Bianca Gandolfo: Mm-hm.
>> Speaker 3: Which is n squared.
>> Bianca Gandolfo: Yeah. Cool.
>> Bianca Gandolfo: So I'm gonna give you just a quick and dirty, like how do we estimate what is the time complexity of these.

[00:04:18]
>> Bianca Gandolfo: I don't know, these loops. So when we have a statement next to each other, we're gonna add them together. So we can say that this is O of 1, plus O of 1 which doesn't really amount to anything to O of 1 right? When we have something nested we're gonna multiply them.

[00:04:42] So we're gonna think about this as, let's see, how do I separate this? As O(n)*O(n).
>> Bianca Gandolfo: And you can kind of estimate this as looking like this, O(n) squared.
>> Bianca Gandolfo: You know times o(2).
>> Bianca Gandolfo: See [INAUDIBLE] because it's nested, we multiply it, if they're standing next to each other, we add it.

[00:05:21]
>> Bianca Gandolfo: But we only care about significant digits, so we just cut off our constant time and we stick with O(n squared).
>> Bianca Gandolfo: So yeah, we're just estimating here and we're thinking worst case scenario.
>> Bianca Gandolfo: And then we chop it off because we go for the worst case, cool?

[00:05:54] Quick and dirty.
>> Bianca Gandolfo: Any questions about that?
>> Speaker 2: Can you repeat the last one you deleted?
>> Bianca Gandolfo: Yeah, sure. So when something is nested in a loop, you wanna multiply it. When they are sitting next to each other, you add them. So here we are sitting next to each other we add these and then we're also gonna multiply it against our loops.

[00:06:28] But they're not significant so we just chop it and in fact as soon as you [INAUDIBLE] loop you could just automatically say, okay that's in squared. And that's totally fine.
>> Bianca Gandolfo: For loop, you can think linear.
>> Bianca Gandolfo: Cool? Awesome. Any questions here. All right.
>> Speaker 4: I'm still a little confused on how you decide what to chop off.

[00:06:55]
>> Bianca Gandolfo: You chop off the one that's the slowest. I'm sorry, you keep the slowest one.
>> Speaker 2: Keep the slowest. Got it, okay.
>> Bianca Gandolfo: Yeah, yeah, yeah.
>> Bianca Gandolfo: Cuz we're just interested in the worst case scenario.
>> Bianca Gandolfo: All right, good question.
>> Bianca Gandolfo: That's the most math we're gonna do.

[00:07:20] All right, so we have this question, what about O of log n? And I kinda gave you a hint.
>> Bianca Gandolfo: That, things are O of logn when you cut it in half. So you can think about any algorithm where your data set is cut in half in order to find it.

[00:07:50] So the classic example is you have a telephone book. And you could leaf through all of the pages of the telephone book to find. You know, your friends last name. If this was 1980.
>> Speaker 2: Mm-hm.
>> Bianca Gandolfo: You look through it or since it's sorted, you can open the telephone book to the middle.

[00:08:12] And you can say so my friends last name starts with a f. You know is it greater or less. If it's less, then you rip the phone book in half and you throw away half. Have you guys seen this metaphor before?
>> Speaker 2: Yeah.
>> Bianca Gandolfo: And then you open it in half again and you say, is it greater, is it lesser?

[00:08:31] And then [LAUGH] depending on, you rip off the other half and you keep doing that. And so it's logarithmic, because as it grows the amount of steps that you're doing is halved, essentially. And so you can see that logarithmic Graph that it kind of goes like that. And that's a pretty good algorithm.

[00:08:49] We're happy when things are logarithmic, for the most part. Cool and that's a binary search.
>> Bianca Gandolfo: Cool, all right. Questions?
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: Cool. Some common operations so running a statement like like one plus one, constant time, value look-up. An array object or variable is going to be constant time, login is going to be when you loop.

[00:09:28] And cut everything in half every time and you are throwing it away, that's important. Because we are going to do something, when we cut it in half. But we don't throw away the other half and I will talk about that in a second when we get there later today.

[00:09:39] It will be fun. And then, O(n) looping through. N squared, double loops. And again, it's important the loops are nested. They're not loops next to each other, that's still linear, so if it's a loop on top then a loop right after, that's going to be two n. Right, nested is n squared.

[00:10:00]
>> Bianca Gandolfo: Cool. All right, are you ready?
>> Bianca Gandolfo: Space complexity. Basically the same, except we're thinking about when we're doing an algorithm, are we creating another data structure to save our data? So, in some of the things that we were doing yesterday when we created an extra array to store our data, what would you think that space complexity was?

[00:10:31] Remember when we did that?
>> Speaker 2: Yeah, we created a second order [INAUDIBLE] reverse going into it.
>> Bianca Gandolfo: Yeah, yeah, so when reverse the array we created a second one and we just copied it over. So as our data grows, right, it was an array of integers. As that grows, how does the space grow that it takes up?

[00:10:58]
>> Speaker 2: Seems linear.
>> Bianca Gandolfo: Yeah. It's absolutely linear, yep exactly, maybe that matters maybe that doesn't matter. We mostly just talk about time complexity, base complexity is a little less important. But it is something you should note so that's why we have in place sorts and then we have not in place sorts which will copy over.

[00:11:22] Cool. All right, so here's some review notes for you to read on your own, if you'd like. Remember I promised you a link, it's right here if you wanna learn about other notations and what they mean. In interviews, in real life, we're only gonna really talk about big O.

[00:11:42] Everything else is more of an academic type thing to talk about. So if you're interested in that kind of thing, have at it. More stuff for you to read. Here is our big takeaway. It's worst-case scenario. We drop any non-significant operations or constants.