Faster Algorithms

[00:00:02]
>> Bianca Gandolfo: So we talked about speed. Are you guys ready to make it faster? Let's check our time, okay.
>> Bianca Gandolfo: So,
>> Bianca Gandolfo: What is the time complexity of this algorithm? So this algorithm returns if an array is unique or not unique. It does so by comparing each item to one another.

[00:00:31]
So we could spread this out a little bit.
>> Bianca Gandolfo: So we have our first loop is looping through the length of the array. We have the second loop is looping through the length of the array.
>> Speaker 2: Is it n squared?
>> Bianca Gandolfo: Mm-hm.
>> Speaker 2: Quadratic [INAUDIBLE]
>> Bianca Gandolfo: Yeah, exactly.

[00:00:47]
Quadratic, and we can see I have some console logs here so that we can see where n is 3.
>> Bianca Gandolfo: We have at least 6, sorry, 9. So we start with the outer loop. Then we do the inner loop three times. Outer loop, inner loop three times. And so that's gonna be 9, 9,

[00:01:20]
>> Bianca Gandolfo: Steps, more or less. Cool, all right, well, we can do better. This is our first technique. I call it the breadcrumb method. I'm not sure where I got that from, to be honest. It could be very common. It could also just be something I made up. But essentially what you do with the bread crumb method is that you're keeping track of things that you've already seen.

[00:01:44]
It's also called caching. Right, so once we see something, we save it and then we can do a property look up on an object, which is what? What's the time complexity of our copy look up? Which is a constant time operation, so instead of having to do more work, again, we just take a look.

[00:02:02]
So in this case we're gonna do one loop through the array. And if we have already found it before. So if we haven't found it, let's start with that, we're going to save that value to the object, and set it to true. So the next time we run into that, we simply check, this is a constant time operation, check if we've seen it before.

[00:02:28]
And if we have, then we know it's not unique, versus the first method where we have to have two loops. We were comparing each one to one another. That's going to be quadratic time. When we use the breadcrumbs technique we could take a quadratic time algorithm and make it linear.

[00:02:45]
And so huge gains in performance. Something that essentially can't even ever be completed in quadratic time is so slow to something that's pretty easy to manage with a large data set.
>> Speaker 2: This is common nomenclature, to refer to it as breadcrumbs? Or is it just like your favorite-

[00:03:02]
>> Bianca Gandolfo: I don't know. Like I was saying, I'm not sure where I got that from. Have you ever heard of it called breadcrumbs? It's caching, but I call it breadcrumbs, cuz I like that mental image. And then we can see here, inside of our loop, we're only looping three times

[00:03:22]
>> Bianca Gandolfo: Whereas before, we are looping multiple times.
>> Bianca Gandolfo: Cool, so easy optimization, we're just gonna cache the result.