Native Methods & JavaScript

[00:00:00]
>> Bianca: Let's talk about some native JavaScript methods, expressions, operations that you see, and talk about what the time complexity of each one is. So what's a method? Think about array methods or? What's that?
>> [INAUDIBLE]
>> Bianca: Yeah, that was a little complicated though. We'll save that one. That's another good question.

[00:00:23]
>> Speaker 2: For loop.
>> Bianca: Hm?
>> Speaker 2: Pop.
>> Bianca: Who said for loop?
>> Speaker 2: For loop.
>> Bianca: Yeah, so for loop, we talked about that a little bit, is what?
>> [COUGH]
>> Bianca: Linear, right?
>> Speaker 2: Yeah.
>> Bianca: So if you have a for loop, it's whatever the ending case, which is like, usually, you say i < n, and whatever n is, that is going to be the number of operations, the number of times that loop executes.

[00:00:51]
Good, and then, what did you say, Matthew?
>> Speaker 3: Pop.
>> Bianca: Pop, yeah, so pop is where we remove. I should do,
>> Bianca: Where we have some array, 1, 2, 3. And we say array.pop, which just removes the last one, and then, my goodness,
>> Bianca: 1, 2. So pop is a constant time operation, because you're always taking off the last one, always taking off the last one, cool?

[00:01:32]
What are some other ones? So we have pop.
>> Speaker 4: For each as complicated as the map?
>> Bianca: Well, I guess, so the thing to know about for each in map is that under the hood, they're just loops. So it's very similar to the for loop. It just gets a little hairy, because you're passing a callback in there, and based on what is inside of that callback, it can vary the number of operations.

[00:01:58]
So if in your for each, you pass a function that also has a loop in it, then it's gonna change. So that's why it's a little complicated because there are some other factors. Pop will always just pop off the last one, and,
>> Bianca: There's no other variables to consider.

[00:02:18]
>> Bianca: Okay, what else? How about Patrick?
>> Speaker 2: Let's say we wanna get the first value array. Can you do a for loop that just always gets the first value with that cuz it would be constant?
>> Bianca: Well so you wouldn't actually need to use a for loop. If you wanna get the first one, you can always just reference the zero.

[00:02:38]
And this would be constant, so just like in our min max price range example, when we had the sorted list, just go directly to the index. And you can imagine, if you're a visual person, that there's this array that exists in memory. And then there's some mathematical formula to calculate where your needle that's gonna read it is gonna land in your hand drive.

[00:03:08]
This is not exactly how it works, but you can kind of imagine that's why it's constant time. So, when you have an index, you can imagine that there's some formula that's two plus two or two plus index multiplied by the memory address, something like that. It knows exactly where to go, it doesn't have to search through all of your data in your hard drive to get to where it is.

[00:03:32]
Or actually, in this case, it's in memory because this is not a database.
>> Bianca: So that's why,
>> Bianca: This is constant time, and this. You don't need to start at array 0 to get to array 1, it just goes directly there. I just imagine this big needle reaching in and pulling, there it is.

[00:03:55]
But that's just my active imagination. Similarly with an object, so if we have some object,
>> Bianca: Right? And we're doing a property lookup. You can imagine,
>> Bianca: That it's doing the same thing.
>> Bianca: So it has some formula, and it just goes [SOUND] right to where it needs to go, constant time.

[00:04:31]
>> Bianca: All right, what about this?
>> Bianca: As your inputs grow, 1+2 will always be 1+2, assuming that your input isn't, these numbers aren't variables, right? Or actually even if it was, 1+n is always just gonna be one operation, right? Just addition.
>> Bianca: Okay, so math is constant, our lookups are constant.

[00:05:04]
What else? Saving to an object an array, you can think of it as constant in JavaScript.
>> Bianca: Any other common methods, expressions, operations? We talked about the greater than or less than, that's a constant time operation.
>> Bianca: So when you're looking through your algorithm, you can kind of spot these things and think about, okay, as my input grows, and you need to also pay attention to what is your input, right?

[00:05:38]
Cuz there could be a few different variables. You can have a list and you can have a number. And we'll talk about that when we go through some examples. But as your input grows, how is it gonna change, right? So if you have an array and you pop one off, if the array is length 3 or the array is length 1,000, it's always just gonna pop off the last one.

[00:05:59]
That's just constant, it's not changing when your input changes. However, if we do something like,
>> Bianca: Unshift or, why am I blanking? What's the other one, where you-
>> Speaker 2: Push?
>> Speaker 3: Slice?
>> Bianca: No,
>> Bianca: No.
>> Speaker 2: Splice?
>> Bianca: No, so when you put something on or take something off the front of an array, so-

[00:06:27]
>> Speaker 2: Shift and unshift.
>> Bianca: Okay, shift and unshift, what the difference there is that shift and unshift are not constant time operations. So if we're starting with 1, 2, 3, we wanna shift a 0 on the front. We have to first,
>> Bianca: So we put the zero here but then we have to move the 1 to the next one, then we need to move the 2 to the next one, and then we need to move the 3 to the next one.

[00:06:55]
And so, if our array is size 3, we have to move things over 3 times. For array size 100, we have to move things over 100 times. So what is the time complexity of that?
>> Speaker 2: Is that actually how they do it?
>> Bianca: Mm-hm.
>> Speaker 2: Okay.
>> Bianca: What is it?

[00:07:15]
>> Speaker 4: Quadratic.
>> Bianca: Close, so if the length of the array is 3, it's 3. If the length of the array is 100, it's 100.
>> Speaker 2: Linear.
>> Bianca: Linear, so it's just n. So if n is our length of the array, it's gonna be linear. Mm-hm?
>> Speaker 2: So then, kinda a native method they use is kind of a combination of both of these that you talked about?

[00:07:38]
What about something like reduce that has all of these different, can expand, but then also you're contracting through addition as well?
>> Bianca: Yeah, so that's another one that takes a call back. And the time complexity of reduce, in its core, it's really just a loop that's calling a function with some arguments.

[00:08:00]
So that's linear time. But when you're taking a callback, you need to consider the time complexity of that function that you're passing in to a reduce. So if you have a constant time operation in reduce, like the classic example of reduce is adding two numbers together or something, that's constant time.

[00:08:16]
So that's really not gonna change anything, so it'll still be linear. But if you're doing something more complicated inside of that call back, it can increase the time complexity significantly. So, yeah, good question. These are good questions. And no one's ever asked me about, I guess the last time I taught this class, map and reduce and for each weren't that popular yet.

[00:08:40]
So this is good. This is good.
>> Speaker 2: Someone online asked about sort.
>> Bianca: Mm, okay, so that's a good question. So sort under the hood is, it really depends. Dang it, this is a hard question. We could just say that it's n log n, which is something that we're gonna talk about when we get to sorting.

[00:09:07]
>> Bianca: I don't wanna put all my cards on the table.