Transcript from the "Calculating Time Complexity" Lesson

[00:00:00]

>> Bianca Gandolfo: So let's jump into an example. Does anyone here use Kayak.com, like Priceline? So let's imagine that you work for Kayak.com and you have these hotel, kind of flights, etc, websites, you do use a lot of sorting, right. You have to sort, you're searching, all of these things.

[00:00:19] So it's a very algorithm-heavy type of application, very practical. We use these all the time, these e-commerce type websites. And so let's say for example, you work at Kayak.com and your PM asks you to add a feature that on the top right, it just lists the range of the prices for the hotels.

[00:00:42] So maybe, I don't know what's a good UI decision here or where you'll put that. Maybe like right here, we would put $50 to $400. Whatever it is that actually reflects the minimum and the maximum price

>> Bianca Gandolfo: Of the hotels in this dataset, in some range, right? Are we following here?

[00:01:07]

>> Bianca Gandolfo: Any questions about that? Cool. All right. So we'll have to write an algorithm to do a job. Yay. So, like I was saying, the more data we have, we don't know how much data is in kayak.com, The longer that's gonna take to figure out the minimum and the maximum required for that range, right?

[00:01:30] Cuz we have to look through n amount of data or x amount of data. Cool. And so, that's cool, we understand that. That's gonna be true, no matter what. What about as our data grows? How does that cost change? And that's the thing that we're interested in. And we're gonna look at some different examples and how to think about that.

[00:01:55] Cool. So here's an example of our data. We have an array of hotels. And so price is unsorted, etc. Or maybe who knows how many are in between here. Cool? Awesome. So one approach to figure this out is to compare every number to all the other numbers, right.

[00:02:24] And so we would have to go through all of this, calculate, maybe the difference. Like, where and find the highest difference between them to find the top and the bottom. Obviously, we know that this is not the most efficient way to do it, right? Just off the top of our head.

[00:02:43] It seems like a lot of extra work, and it may not be the most intuitive way of approaching this problem. But there's one way to approach it. Just literally comparing every number to every other number in our data set, cool. And so, how many comparisons will we have to make?

[00:03:07]

>> Speaker 2: However many.

>> Bianca Gandolfo: Yeah, so it's gonna be this amount of columns times this amount of rows, right? And so if this was four, right, it'd be 4 times 4, 16 comparisons, right? It's 10, 10 times 10, 100 comparisons. And so if we distill that down into any number, what would we call that in math?

[00:03:38]

>> Speaker 3: Squares?

>> Bianca Gandolfo: Square, yeah, yeah, and so we call this n squared.

>> Bianca Gandolfo: Where's my So we call this an n square solution. It didn't show up, that's okay.

>> Bianca Gandolfo: Does that make sense? So n squared, as in grows the amount of operations that have to happen, grows exponentially by two.

[00:04:05] And we can see with this box. Every time it grows, we have to add a column on the right, And we have to add a row on the bottom. And so we could just count that. And that would be the time complexity of that operation.

>> Speaker 3: The diagonal though is just comparing numbers to themselves.

[00:04:26] Why is that necessary? You know what I mean? If-

>> Bianca Gandolfo: Yeah, you could optimize and say, if this number is itself, skip. But at the end of the day, it's not really gonna make a big difference. Yeah, cool.

>> Bianca Gandolfo: All right.

>> Bianca Gandolfo: Cool, uh-oh.

>> Bianca Gandolfo: Where's my other one?

[00:04:59] Okay,

>> Bianca Gandolfo: It's out of order. Here we go. Sorry, sorry, sorry. Okay, so this is just what I was saying before. As it grows, how does this grow?

>> Bianca Gandolfo: Right, significant amount of growth, right? Cuz the difference from 3 to 5 is two. The number of operations from 9 to 25, much more than that.

[00:05:34] So we call this a slow algorithm and squared is considered very slow. It's not ideal. Cool, great. Awesome, so here's another way we could think about this problem. So what if we just checked, if for the highest number and the lowest number. How many operations do we have to do for that?

[00:05:58] So as we're going through, we're asking what's the maximum? What's the minimum?

>> Bianca Gandolfo: So as we go through, yes this is the max, yes this is the minimum. At this point, right, the first loop. First. Yes, no, who knows, who knows, no. And we'll just update this. Does that make sense, as we're looping through?

[00:06:27] It might even be easier to think about it like that, if you want. So how many comparisons here were made, overall?

>> Speaker 2: N times two?

>> Bianca Gandolfo: Mm-hm. So for every input, this is, if we have one, say we only have a list of 1, we have to check, we have two operations, right.

[00:07:01] If we have two, we have four operations. If we have four, we have eight operations.

>> Bianca Gandolfo: Are we seeing this here? Again, you can just count these boxes and you can see how many operations there are. And then we can distill it down to what that means in a more generic way and call it 2n, yeah.

[00:07:32]

>> Bianca Gandolfo: Cool, did you have a question?

>> Speaker 3: I just-

>> Bianca Gandolfo: Or you're just-

>> Speaker 3: Trying to ask some-

>> Bianca Gandolfo: [LAUGH] That's okay, cool. So n being the dataset, the size of the dataset. Cool.

>> Bianca Gandolfo: So, what about this case? What if our data was sorted? So here, we have our array and it's sorted.

[00:08:03] How many operations will we have to do to complete this?

>> Speaker 2: Complete what?

>> Bianca Gandolfo: To find the highest and the lowest.

>> Speaker 2: Two, right?

>> Bianca Gandolfo: Yeah, probably just two. Highest and lowest, maybe three if you have to return something.

>> Speaker 2: It's just like it's the derivative of the n squared and 2n, and then again, and then you get the 2.

[00:08:30]

>> Bianca Gandolfo: Yeah, it's not that complicated. It's like a coincidence, lots of 2's here. It's actually, it has nothing to, yeah. So the reason it's 2 is because all we have to do is say hotels. Zero, right? To get, this is gonna be the minimum, assuming it's in ascending order.

[00:08:53] And then we have hotels, right, hotels.length-1, that's gonna be our max. So that's 1 in two operations.

>> Bianca Gandolfo: Do we see how that's different than our other things where we'd have to loop and check everyone? Cool.

>> Bianca Gandolfo: Any questions about the difference between these run times?

>> Speaker 2: What do you call this last one?

[00:09:27]

>> Bianca Gandolfo: This is constant time.

>> Bianca Gandolfo: Mm-hm. So as our input-size grows here, it doesn't change. So if our input, so if this list is a billion long, it's still gonna cost us two operations. That's the fastest, right, that you could ever want. It's always just gonna be 2.

[00:09:57]

>> Speaker 2: Do you count the sorting though, in the operation? Cuz when you add a new item-

>> Bianca Gandolfo: Yeah, so we're assuming that's already sorted.

>> Speaker 2: Already sorted.

>> Bianca Gandolfo: Yeah.

>> Speaker 2: Yeah, okay.

>> Bianca Gandolfo: Mm-hm, good question though, great.

>> Bianca Gandolfo: I see some faces in the audience that look confused.

[00:10:21]

>> Bianca Gandolfo: Let's see, can someone make up a question? It might not even be really your question. It could be just a made-up question.

>> Speaker 2: Wait, do you ever need to just get the minimum and max of a list? Or would you know it was already sorted? Like would there be a used case where you could do this?

[00:10:40]

>> Bianca Gandolfo: Would there be a used case for this specific example? Yeah, if you know it's already sorted. If you're keeping your list sorted, which is usually a good idea if you need to do something like this, then yeah, yeah. But sometimes, you don't have that luxury, right? Sometimes you're getting data from who knows where.

[00:11:00] Might not be sorted, you might have to sort it yourself first, cool.