[MUSIC] All right, so now it's time to figure out how long does that brute force approach take to solve the traveling salesperson problem and how long does a greedy approach take? So by the end of this video you'll be able to analyze the running time for both of these algorithms. Just to remind you of that brute force approach, what we're going to do is we're gonna just generate every single path through the cities, calculate their distance, keep track of the best one. So and we said it works, but we're a bit concerned that maybe it was gonna take a long time. Because there might be a lot of these paths to consider. So let's take a look at the algorithm a little more formally and some pseudocode here. So here's the algorithm. We initialize our best path and our best distance variables. And then we have this central loop, and the loop is just gonna execute as long as there are more permutations of cities, different paths to consider. Inside the loop we'll just calculate the distance of the current path and if that current path distance is less than the best distance we've seen so far we'll keep track of that as the best path and we'll keep track of that distance as the best distance. When the loop finishes we'll have a hold of the best path and we'll just return it. So in our analysis, of course, we have a loop, we just need to figure out first how much is happening inside the loop and then how many times is the loop executing. So that if statement there and what's inside the if statement, that's just constant time. But the one piece we have to worry about inside the loop is this one right here. How long does it take to calculate the best distance of a particular path? Well that's just order n because we basically just need to figure out along each edge between the cities, what is the distance, and add them all together. So we've got an order n operation inside the loop. Now it's time to think about how many times does this loop run? And the answer to that question is going to be the answer to how many different permutations are there? So let's think about this question. So we wanna figure out how many different permutations or how many different paths through these cities could we possibly have. So I'm gonna leave this for a question for you to try to answer. All right, now that you've had a chance to think about this on your own let's go over how many different permutations we could have here. The first question we want to ask is how many different cities can we start from? Well, there's just one. We said we're going to start and end in our hometown, which in this case is San Diego. The next question is how many cities could we go to from there? Well if we take away San Diego, because we're not going to go to San Diego, we've got seven cities remaining. So we could go to any of those seven cities next. Then we ask from the first city we go to how many cities can we go to after that? So let's just arbitrarily assume that we go to Cairo next. And then ask the question, from Cairo how many cities could we reach? Well there are six remaining cities to go to so we could reach six cities next. So we've got the start of some potential paths through our cities. And I want to pause for a moment here to think about how many starting pads do we have so far? Well for each of these first seven cities, that we could pick, we could then go to six different cities from that first city. So we have seven cities we could start from, and for each of those seven cities, there are six options for where to go next. So in total we have 7 times 6 possible starts to our paths. So we have 42 starts so far. And then each of those 42 paths is going to expand in many different ways. So as we go from city to city to city, we're going to multiply the number of choices we have at each point by however many paths we had before. Because each of those paths can expand out in the same number of directions. So let's continue. We know that after we have six cities considered, then next time we're going to have five cities consider, then four, then three, then two, then one, and finally one remaining city for our hometown back to San Diego. So overall what we have is 1 x 7 x 6 x 5 x 4 x 3 x 2 x 1.. And this is equal to 5040 paths or in mathematical notation you may have seen the factorial function. This is 7 factorial. 7 factorial is just 7 x 6 x 5 x 4 x 3 x 2 x 1. For any n the factorial function is n x n- 1 x n- 2 x n- 3, all the way down to times 2 times 1. So here we have 7 factorial different paths to consider. In general, if we have n cities, where one of those cities is our hometown, we're going to have n-1 factorial permutations to try. So this allows us to go back to our algorithm and fill in the missing details. We know that this loop is going to run over all the different permutations, and their n-1 factorial of those permutations. If we multiply that by the order n work we do inside the loop, we get that overall this algorithm is order and factorial. Okay, that looks simple enough. How bad is that really? Well, let's think about the factorial function. How bad it is the factorial function? How fast does it grow? At first, it doesn't seem so bad, right? Seven factorial was only around 5000. So maybe it's not so bad. Well, if we look at some values of n, as n gets big, we can see that it actually is really, really bad. So 10 factorial is already starting to get pretty big at 3.6 million or so. By the time we get to 19 factorial, we're at 1.22 x 10 to the 17 which is roughly the age of the universe. Up to 23 factorial, we've got a number that's equal to the number of stars in the universe. And by the time we get to 59 factorial, we have a number that's equal to the number of atoms in the known universe. That is a huge number, totally unreasonable. And that's only 59. That's 59 nodes in a graph. You've been working with graphs that have thousands of nodes in them. So clearly, we're not going to be able to use this brute force approach on the graphs you've been working with. So this brute force algorithm only works for very small graphs and won't be practical for anything even remotely bigger than small. Which brings us back to our greedy algorithm. Now our greedy algorithm isn't optimal in all situations. But is it fast? Let's see. So here's the greedy algorithm. We're gonna build our path from city to city. And at each city we're just gonna make the greedy choice and choose the edge that's smallest to a node that hasn't yet been visited. So there's the algorithm right there. We're gonna apply the same analysis technique. We're going to look at the loop, itself. How many times does the loop run, and then how much work is done inside of that loop? So it's fairly straightforward to calculate how many times the loop runs because there are n minus 1 cities that we need to consider inside that loop if we subtract out the home town. So that loop is going to run n minus 1 times. But how long does it take to do the work that's inside the loop? The step that we care about here, the most important step is how to select the closest city to visit next. Well if you think about it from any city it's a fully connected graph so we have n minus wind nodes that we could visit, and we need to figure out what's the closest one that hasn't yet been visited, and that could take at most n minus 1 steps. So that's about an order n operation. So putting this all together we have n-1 times the loop is going to run order n steps each time inside the loop, and overall our total algorithm time is going to take order n squared. Phew, n squared much better than n factorial. So although the greedy algorithm doesn't always find the best solution sometimes it does. And it's much, much faster than that brute force approach. It's practical for even large problems. And the better news is that sometimes we can even improve on the greedy algorithm. Not necessarily make it optimal, as Leo's going to talk to you about next, but at least make it better but keep it really fast.
