Transcript from the "Review: Time Complexity" Lesson
>> Bianca Gandolfo: All right, we're going to get started. We're going to have the world's quickest recap. All right? So we're going to rehash everything we've done for the past couple days. But I have a big ask. A bold request of the audience. Are you guys ready? My request is, as we're going through, I'm going to ask you on your reflections.
[00:00:20] On learning this material over the past couple of days, what were things that were confusing at first? What advice would you give to your previous self when learning this material? Cool? Be mindful as we go through the curriculum. Think of maybe an aha moment that happened. Think of something that was confusing at first, and then it became more clear after something happened, etcetera.
[00:00:49] Does that make sense? Everyone understand the bolder quest? You have moments in your mind that come to mind, no? We'll see. Okay, all right, keep it there. All right, so world's fastest recap. Are you ready? Ready? Get set, go. All right, so does everyone remember time complexity? Time complexity is how we measure the speed of our algorithm, right.
[00:01:22] So some common operations for measuring time complexity. If we're running a statement.
>> Bianca Gandolfo: Like a return statement, for example, it's gonna be constant time. Lookups on arrays and objects are going to be constant time if you access them directly. A loop that cuts a problem in half every iteration.
[00:01:46] This is gonna be logarithmic, looping through all of the values of an array, that's gonna be linear. And then we have linearithmic, which is n(log)n when. We split it in half but also we loop through the entire array. Or entire collection, it doesn't necessarily have to be an array.
[00:02:10] So then we have O of n squared quadratic time, double nested loops. Exponential time would be triply nested loops. Cool? Questions here?
>> Bianca Gandolfo: Okay, awesome. So here's our time complexity graph. This is from bigocheatsheet.com. I highly recommend that website if you kinda wanna peek through more stuff about time complexity.
[00:02:40] Something that we discussed a couple days ago is this n(log)n time, for when we're talking about merge source. You guys remember that? And just here graph, I just wanted to point out that it's going to be slower than our linear right? So this is the number of operations that have to be completed versus a number of elements, right?
[00:03:02] So for something that's constant times, it's gonna stay the same, which is not even graphed here. Something that (log)n is going to grow but then it's gonna grow more slowly over time as the problem keeps getting cut in half in linear time. It's gonna be the same, proportional.
[00:03:24] n(log)n is a little bit slower than linear time, I'm sorry, a little bit, yeah, a little bit slower than linear time but also a little bit faster than exponential time.
>> Bianca Gandolfo: Right, and we have found that our fastest sorts are running in n(log)n, right? Merge sort, quick sort, we talked about that.
[00:03:49] And then we have exponential time, and squared, which grows pretty fast. Shoop, see that? That's a bad thing. We learned that bubble sort and search your sort, selection sort, all of these elementary sorts that have these nested loops are gonna be,
>> Bianca Gandolfo: Quadratic time, cool? Everything else just is basically a straight line up.
>> Bianca Gandolfo: So how do we estimate? Here's the steps. So you're gonna go through your algorithm, estimate each line. Then you're either gonna multiply them or add them, based on whether they're nested in a loop. Or, they are side by side. And then you're gonna drop any non significant digits and just assume the worst case.
>> Bianca Gandolfo: Cool?
>> Bianca Gandolfo: All right., so here's our bold request. Who here did not know time complexity before this class? Awesome. Who now feels like they have a pretty solid understanding of time complexity? Cool, so what got you there? What was a big takeaway for you?
>> Speaker 2: I think that chart you showed earlier where you showed each, what is it level, or whatever, where you have the different types of-
>> Bianca Gandolfo: This one?
>> Speaker 2: Yeah, that one. Operations, that's it. So that was helpful for me, to kind of
>> Bianca Gandolfo: So like maps being like, real operations.
>> Speaker 2: Yeah.
>> Bianca Gandolfo: To their time complexity?
>> Speaker 2: Yeah.
>> Bianca Gandolfo: Cool.
>> Speaker 3: That was super helpful. And the thing that made it click even more for me was that you drew out a graph showing how many comparisons would have to happen.
[00:05:49] You know what I mean, like--
>> Bianca Gandolfo: The table.
>> Speaker 2: Yeah, the table. Thank you.
>> Bianca Gandolfo: Yeah, so let's see, that'd be like writing out table showing number of comparisons.
>> Speaker 2: Yeah. I think that's when it clicked for me.
>> Bianca Gandolfo: Cool. Anything else? Anything that was confusing at first?
>> Tebit: I get how to find from this lesson. Time comma to the cell complexity on the last slide. I didn't realize before this lesson how to find but the steps to find. The time it took, time complexities where we had before.
>> Bianca Gandolfo: Got it, so for you it was the breakdown of the steps for estimating time complexity.
[00:06:47] And it's really important that we recognize that we are estimating time complexity. There are mathematical proofs that go behind calculating this and we have not gone there and we will not go there in this class. Anything else?
>> Bianca Gandolfo: Anything? Okay.
>> Bianca Gandolfo: All right. So Christine says some example walkthroughs were helpful, like when we doubled the sample size.
[00:07:20] For example, what's a useful way to think about time complexity? Thinking about what happens when we double the input. Let's say when we double and so we fit. Cool, all right. So further study is going to be a formal analysis of algorithms. There are classes like this online if that tickles your fancy.