Data Structures and Algorithms in JavaScript Calculating Big-O of JS Operations

[00:00:00]
>> Bianca Gandolfo: Let's try to calculate some, real code and talk about time complexity with them. So some operations are constant time. Some operations, are linear time. Some are more, some are less. Let's explore, native methods. Yeah, do you guys know some JavaScript native methods? Maybe for some arrays.
>> Speaker 2: [INAUDIBLE] Like you'll have to amend.

[00:00:29]
>> Speaker 3: Push.
>> Bianca Gandolfo: Yeah, so that would be one. Like array that, push is a good one.
>> Bianca Gandolfo: Mm, that's not native.
>> Speaker 3: Pop.
>> Bianca Gandolfo: Yep got a pop, then we have like some, like the expressions. Then we have maybe some loops.
>> Bianca Gandolfo: And what else can we put in here?

[00:01:02] We have like array.unshift
>> Bianca Gandolfo: Etc. So when we push to an array, as our array increases in size, how does the push method, how much more work does the push method have to do?
>> Speaker 2: Constant?
>> Bianca Gandolfo: Constant, it's the same, right? What's constant? O of?
>> Speaker 2: 1
>> Speaker 3: 1, yeah.

[00:01:33]
>> Bianca Gandolfo: Whoops, cool. What about pop? As our array grows in size, how much more work does pop take?
>> Speaker 2: Constant as well.
>> Bianca Gandolfo: Mm-hm.
>> Bianca Gandolfo: Awesome, and expressions like this, obviously they don't change in size, so that's also gonna be constant. What about a 4 loop?
>> Speaker 2: Linear?

[00:01:58]
>> Bianca Gandolfo: Mm-hm.
>> Bianca Gandolfo: So, as our, whatever we're looping through, right? It could be a number, it could be an array. As that grows, we're gonna add one more every time, for every loop. Good? Awesome. What about unshift?
>> Bianca Gandolfo: So unshift is, when you put an element at the beginning of an array.

[00:02:35]
>> Speaker 2: When you put it at the beginning?
>> Bianca Gandolfo: Hm hm.
>> Speaker 2: Seems like it'd be constant. So would you have to shift every-
>> Bianca Gandolfo: Yep.
>> Bianca Gandolfo: So here, we have to shift everything over one index, what kind of operation is that?
>> Bianca Gandolfo: So how can we think about this?

[00:02:56] So, let's say our array, oops, our array, has a length of 4.
>> Bianca Gandolfo: How many times do we have to shift it over, for it to do this, right? Shift over 1 to this index, 2 to this index, 4 to this index, or you know 4 to the next index over.

[00:03:20]
>> Speaker 2: Would it be quadratic?
>> Bianca Gandolfo: Let's think about it. So what if, our
>> Bianca Gandolfo: We doubled, we doubled, right? So how much work is this? So we have to move it over how many times?
>> Speaker 2: Four.
>> Bianca Gandolfo: Four times yeah?
>> Bianca Gandolfo: For this one,
>> Bianca Gandolfo: How many times do we have to move this over?

[00:03:56]
>> Speaker 2: Eight times.
>> Bianca Gandolfo: Eight.
>> Speaker 2: Linear.
>> Bianca Gandolfo: Mm-hm, so as our array grows, we have, in more moves that we have to make, cuz we have to shift every one over, and we can't skip it. Where there's no getting out of that. So we were just talking about array.

[00:04:22] That unshift.
>> Bianca Gandolfo: And if we wanted to add, a 0 to it, how many times do we have to shift? So this is four moves, right? And if we double it.
>> Bianca Gandolfo: This is eight moves. So the size of the array here. Size of 8.
>> Bianca Gandolfo: Size of 4.

[00:05:06] So given this, if we had an array of 100, or length 100, how many shifts would we have to make to add the 0 at the beginning? 100, yeah, and so that's a linear time operation. So, the point I'm trying to make is that, even though we have this native methods and we do need to be mindful that they run, they still running underneath the hood at different time complexities.

[00:05:36] And when we're calculating time complexity, we need to keep that in mind. So if we're unshifting, which is not a very popular thing to do, but you might be unshifting in your algorithms, I don't know. Or sorting it's another one, something that sort, is different time complexities. Cool.

[00:05:54] Questions about this? No. Everyone's just an expert at time complexity now? Okay.
>> Speaker 2: Do you have some example concerning quadratic and exponential?
>> Bianca Gandolfo: Yeah. So quadratic, so an example of quadratic would be, like a loop within a loop. So if you're looping over the same set twice, that is just a classic example of quadratic in an exponential.

[00:06:25] Similarly, like if you have three loops looping over, the same data set, or two different data sets of a similar length, you're gonna have a cubic which is an exponential, yeah.
>> Bianca Gandolfo: Cool. So is sorting linear? That's a great question. It depends on the sorting algorithm that you use, and if we think about sorting and what it takes, we have to compare things to one another, and we're gonna get to that in a second, but you're never gonna see a linear sorting algorithm.

[00:07:01] If someone invents a linear sorting algorithm, they're gonna win some Nobel prize in computer science, if that exists.
>> Bianca Gandolfo: So no, there's no linear sorting.