This course has been updated into a 4 part series! We now recommend you take the A Practical Guide to Algorithms with JavaScript course.
Transcript from the "Calculating Time Complexity Solution" Lesson
[00:00:00]
>> Bianca Gandolfo: What is the time complexity of this guy or gal, or neither? Anyone, anyone get to this one?
>> Speaker 2: I thought this one was linear cuz it's the single.
>> Speaker 3: It's constant.
>> Speaker 2: It has an increment within it.
>> Bianca Gandolfo: Yeah, so if we just broke it down, this one's constant, right?
[00:00:21] The loop is goinna be linear, [SOUND] And here, constant. Constant, right? We don't really care about the constants. We just throw them away. So the end of the day, we're going to call this linear
>> Bianca Gandolfo: Cool, the fact that we're calling this function twice means nothing to our big o notation.
[00:00:52]
>> Bianca Gandolfo: Questions, comments?
>> Bianca Gandolfo: Big surprises from this, no, okay.
>> Bianca Gandolfo: All right, so this is an interesting question, right? Because we have to know how string dot length works. Does anyone know how string dot length works?
>> Bianca Gandolfo: [LAUGH] How does it work?
>> Speaker 2: We googled it, cuz to try see how it worked, and it seems like strings are so it just stores the length Yeah, yeah, absolutely.
[00:01:24]
>> Bianca Gandolfo: So the trick here is that, that length is not a function. It is just a property lookup. And all property lookup on objects. And secretly, everything is an object in JavaScript. So anytime you see this dot, and you are not calling it, it's a property lookup and it's going to be a constant time.
[00:01:44]
>> Speaker 4: It doesn't have the so it's not evoking a function.
>> Bianca Gandolfo: Yeah, exactly, so if your'e envoking it maybe you are popping. So if you have an array in here, [SOUND]. And we did an array dot push, this is still gonna be a constant time operation. We are still envoking it.
[00:02:02] When we envoke it, actually it's still a constant, so it doesn't matter. Let me do a better example, for unshift, we were talking about how unshift is linear before. If we don't call it, this operation is just a property lookup and it's constant. When we call it, suddenly now it's linear.
[00:02:22] So the details do matter here.
>> Bianca Gandolfo: They matter but we're also estimating. Cool, so str.length, property to look up, constant time. We're good to go. We're good to go?
>> Bianca Gandolfo: Awesome.
>> Bianca Gandolfo: All right, so we already talked about this. Push is what?
>> Bianca Gandolfo: Constant. What about unshift?
>> Speaker 2: Linear.
[00:02:54]
>> Bianca Gandolfo: Linear, o of n, all right