Big O: Loop

[00:00:00]
>> Bianca: Here's another chart that, [COUGH] excuse me, here's another chart on Big-O complexity, and you can see that we have our constant time and our login times are very, very good. Then we have our linear, which grows at a much slower pace as well, also very good. And then as we increase to quadratic and exponential time, those are terrible, terrible, terrible algorithms.

[00:00:33]
Another good resource, if you wanna learn more about this is called a Big-O cheat sheet, where I stole this image. And they have the time complexity and there's the average and worst cases for a bunch of different things. And you can even get a poster, so it's kinda cool, really good resource.

[00:00:54]
>> Bianca: All right. So let's do an exercise together, we're going to reason about the time complexity of a few different functions. So this function is called the count character function. We loop through the length of a string and then we increment to counter. So when our length of the string, which is n, right?

[00:01:18]
So our n here, the thing that's gonna change is the length of the string. And we know that because it affects the number of loops for our loop here. And then when we do an increment, that is gonna be a constant time operation.
>> Bianca: So what do we think?

[00:01:42]
So we have this constant every time. So if string is length five,
>> Bianca: How many operations does this do?
>> Speaker 2: Just one.
>> Bianca: Just one, yeah. How many operations does this line do?
>> Speaker 2: One.
>> Speaker 3: One.
>> Bianca: Five.
>> Speaker 3: Five, the four loops through the number.
>> Bianca: Yep so this will be called five times.

[00:02:06]
And now what about this one?
>> Speaker 2: One.
>> Bianca: Just once, yeah. And so we can say these are both constant time. Because it's gonna be one, because when we, so let's see, let's make this really long walking really fast or something. How many operations for this one?
>> Speaker 2: Still one.

[00:02:30]
>> Speaker 3: Still one, how many operations for this one.
>> Speaker 4: 14.
>> Bianca: Yeah, however long this is, right?
>> Speaker 2: Right.
>> Bianca: And then this one?
>> Speaker 2: One.
>> Speaker 3: One.
>> Bianca: One.
>> Bianca: So what kind of time complexity do you think this algorithm has?
>> Speaker 3: Linear.
>> Bianca: Linear. Linear, right?

[00:02:50]
The big give-away is that we have this loop. And we're doing a constant time operation in the loop, so we just drop those, it's not that important, we stick to the linear, that's the most significant. That's the slowest part of this, so we don't really think about the constant.

[00:03:08]
>> Speaker 3: Question, so it sounds like then when you assess it during the analysis, you evaluate every expression? Whatever's the longest, what's the worst case, and that really becomes your-
>> Bianca: Yeah.
>> Speaker 3: Time complexity.
>> Bianca: Absolutely, yeah, exactly.
>> Speaker 3: So it's not holistically, you assess it? You really break it down into each expression,

[00:03:25]
>> Bianca: Mm-hm.
>> Speaker 3: And then pick the worst one?
>> Bianca: Mm-hm, yep, yep, exactly. And then you'll learn to kinda disregard certain things, like initializing values, and returning values you learned, just to, those don't really matter. And then you can kinda see where to focus your attention when you're estimating time complexity.