Data Structures and Algorithms in JavaScript Space vs. Time Complexity

Transcript from the "Space vs. Time Complexity" Lesson

[00:00:00]
>> Bianca Gandolfo: So we talked about pseudo classical and instantiation pattern, which we'll be using, mostly starting tomorrow. Today we won't be using it, but I wanna do a quick refresher. What were the main components of making a class in JavaScript using that pattern?
>> Speaker 2: We have a function that's the constructor.

[00:00:22] And that has the properties, and then you have the prototype. Is that what you call it, or is there another name?
>> Bianca Gandolfo: Yeah, it's a prototype object.
>> Speaker 2: Yeah, and then you have the methods on that.
>> Bianca Gandolfo: Cool, yeah, exactly, so those are the three parts. The first part is the constructor function, then inside of that you define the properties.

[00:00:41] You put that on this keyword, this .blah blah blah. In our example, we said this.floors yesterday. And then for the third part, is our methods that we want to have shared over all the instances and we put that in on the prototype object. Yeah, cool, any questions about how all that works?

[00:01:01] We use the keyword new in there whenever we want to instantiate an instance of our class. Yeah, questions?
>> Bianca Gandolfo: Cool, what were some different recursion patterns that we talked about yesterday?
>> Bianca Gandolfo: There are two main ones that we kinda pointed out.
>> Speaker 2: One was a wrapper that you actually had the recursive function inside another function, and then you could store state within the wrapper.

[00:01:36]
>> Bianca Gandolfo: Yep, we have a wrapper, where we have just the recursive function that lives inside of another function. And we're saving into a variable outside of our function, absolutely. What's another pattern, and these aren't the only patterns, there's lots of different patterns in recursion.
>> Bianca Gandolfo: There was another pattern where we were passing our data through every time we call a recursive function?

[00:02:00] Cool, and then from the chat we have signs or tips on when to use recursion versus loops. That's a great question, we are gonna get into that a little bit more starting tomorrow when we do trees. But the idea is you can always use a loop for recursion, it just gets a little more complicated when you get into nested data structures.

[00:02:22] And so that's when it really becomes valuable to use recursion. It simplifies sort of complicated operations or procedures for nested things that you don't know how nested it will be, right. So if we know how nested an array is, for example, like say we have an array and inside that there's three more arrays, and inside of that there's three more arrays, so you have a triply-nested array.

[00:02:49] We know that we can use three loops, and that's fine, but what if, for the case where our arrays are nested, who knows how many times. It could be different for each case. In those cases, that's the classic recursion use case in JavaScript. Cool, recursions are expensive, they are slow.

[00:03:11] True, so is looping.
>> Bianca Gandolfo: Great, anything else before we move on? Great, so today is day one. Like I was saying, yesterday was kind of a pre-req day and today we will be introducing a lot of new things that is gonna build on top of yesterday. Mostly, what we'll be working on today is the recursion at the end of the day.

[00:03:38] But we'll start off a little bit slow, like I was saying yesterday. We'll start off slow with some elementary sorting, talking about time complexity, how do you calculate that. And then we'll do some recursive sorting algorithms that are really fun, cool. Awesome, so you can come here to slides.com/bgando/femasters, this is our syllabus.

[00:04:02] So you just scroll down to Sorting, and you can follow me to the slides.
>> Bianca Gandolfo: Great.
>> Bianca Gandolfo: Let me know when everyone's there.
>> Bianca Gandolfo: Are we there? Thumbs? Awesome. So, the first thing I want to talk about is speed of algorithm. So, we did a lot of different things yesterday, and you all brought up

[00:04:42]
>> Bianca Gandolfo: The question is, what is the better way, what is an optimized version of this? And I said, wait, we don't know how to talk about that yet, we don't have the vocabulary and method to calculate that quite yet. Some of us might, but we haven't talked about it yet.

[00:04:58] Does anyone here use big O notation previously? A couple of people, awesome. So that's what we're gonna talk about today. There are other notations, but we won't get into them, but I have some resources where you can look into it after. Cool, so time complexity, or what is the runtime of this algorithm?

[00:05:20] Is this algorithm fast, is it slow? How do we answer those questions? That's what we're gonna learn today. So there's a couple things, there's space complexity. How much space is it gonna take up? How much memory is used then we have time complexity. We can kind of ask these questions like, how many comparisons are made?

[00:05:40] How many swaps are made? This is particularly related to our sorting algorithms that we're going to get into later. There are other questions that you have to ask as well, depending on the operation. Basically, it's like how many operations do you have to do? More as your data grows, right.

[00:06:02] You know, we're posed with this problem as computer scientists of how do we measure speed of an algorithm when there's so many factors that make it different. We can't say, this algorithm is five, you know, it runs in five seconds, when the data set is this big. There's different factors, there's a computer, you know, there's like the compiler, there's the language itself, and the environment.

[00:06:22] So all of these different factors will change the actual time in which it is computed. And so that's why we have time complexity notation, which is a relative speed. So as your data set grows, how much more work does your algorithm have to do? How many more operations, and that's gonna define the speed.

[00:06:46] Cool, any questions about that? Awesome, cool. So with respect to input size, and we're always gonna assume the worst case scenario.