That's another very important reason to use reductions. and that gets us closer to our goal of being able to classify the difficulty of problems, and that's to establish lower bounds. so let's take a look at that. So, what we want to do is come up with a proof that a problem requires a certain number of computational steps. and we had an example of that for sorting. We showed in the de, decision tree model, any compare based sorting algorithm has to use at least at least N log N and compares in the worst case. And we show that be showing that no matter what the algorithm is, it has to distinguish between all the possible cases of sorting. And that led us to in fact, a tree that has N factorial leaves on the bottom. And the height of the tree has got to be at least log of that, which is N log N. And you can go back to the sorting lecture and look at that. now that's a complicated argument that certainly took you a little while to understand. and, in general, it's extremely different, difficult to establish lower bounds because it's generally requires a complicated argument like that. You have to be arguing about all possible algorithms and that's very often tough to do. Initially, there was a lot of optimism that we would be able to have lower bounds as researchers worked more and more. And we'd be able to classify problems. This actually worked out pretty difficult to get non-trivial lower bounds for all kinds of computational problems where people thought it would be easy. But the good news is that reduction allows us to take the ones that we have and spread the lower bound. so, for, if we can reduce sorting to a new problem and, without too high a cost of reduction, that gives us an N log N lower bound on that problem. So, let's see how that works. so we have to make sure the cost of the reduction is not high, that's key. so, and actually, most of the time, like in the examples that we've looked at, we used linear time reductions. So, that is we only use a constant number of calls to Y. and we use just a linea r number of steps, so usually we're going through everything in the input and output to do some kind of conversion, and that's what we've done in all the examples that we've seen so far. so, then the idea is, so if there's a lower bound for X, and you reduce X to Y, that establishes a lower bound than Y, right? So why is that? If I could solve for Y more quickly, then I could use the reduction to solve X more quickly. so if I have a reduction from X to Y and there's a lower bond of N log N and X, I can't have a linear logarithm on Y. Because if I did and I have a linear time reduction, that would give me a linear time algorithm for X. Same way if I have a lower bound of n squared for X, I can't have an N login algorithm for Y. Because if I, if I did, since I reduced X to Y, then that would give me linear time algorithm for Y. So, the reduction allows us to propagate the lower bound. If I could solve Y, then I could easily solve X but I know I can't easily solve X, so therefore I can't easily solve Y. It's a very powerful technique and really where most of our lower bounds comes from. So, just for an example, let's look at lower bound for the convex hull algorithm. and it's again, convex hull certainly don't seem so related but it's actually the case that in any algorithm for convex hull is going to take N log N. And so we start with a more general statement about sorting. use the so-called quadratic decision tree model. and this is just a detail about the model of computation that makes the idea of comparing a serving algorithm to a, a convex hull algorithm. It makes, it makes them both use the same operation. So quad, quadratic decision tree you get not just these comparisons, but you can use tests like this the, the product of the difference of two numbers. are they less than zero or not? and those are the basic kinds of operations that you're going to use in the in the geometric algorithms. And so, the proposition is that under this model, sorting linear time reduces to convex hull. so that says, if I can com pute the convex hull, then I can sort. since I can't sort faster than N log N, I can't do convex hull faster than N log N. and the proof is not terribly difficult but the implication is really important. So, convex hull algorithms it was just based on that idea, am I making the right turn? that's called a CCW test in computational geometry. I have three points, and going from first to second to third, is that a count, counterclockwise turn? and then, you can implement that test with these kind of quadratic things. It's just testing the slopes of two lines and comparing them. So, it's kind of like a comparison. and, and the implication of the fact that sorting reuses a convex hull means that you can't solve a convex hull fast. and so how do we do the reduction between sorting and convex hull? and again, the, I have a sorting instance, I have some numbers to sort. and what I want to do is create a convex hull instance that gives me sort. Well, all we do is we take the numbers that were supposed to be sorted and we convert them to points on a parabola. so we just take X1 and X1 squared, and X2 and X2 squared and like that. Those are points parabola. now, there's no points and, and we give that to the convex hull algorithm. Now, all of those points are on the convex hull. in a convex hull algorithm, its supposed to return on in clockwise order. and you can see with just finding the smallest that gives us the points in sorted order. So the convex hull algorithm does its job. However, it does it we can take the solution to the convex hull algorithm, and get a solution to the sorting algorithm. Sorting reduces the convex hull. therefore our convex hull can't be easy cuz that would make sorting easy. this kind of thinking is really, is really profound and it has really done a lot to enhance our understanding of the difficulty of different algorithmic problems. so, that's, that's the proof that I just explained. this parabola thing is definitely going to be convex and all the things are on the hull, so we just get the po int that's got the most negative X coordinate and you've got the integers in order. so establishing lower bounds through reduction is really important. we have a big convex hull problem to solve and, and we're wondering, do we have a linear time algorithm for this? It's a quite natural thing to wonder. and so how are you going to convince yourself that there's no linear time convex hull algorithm? one thing you can do, and believe me, a lot of people did this, is just try to find a linear time algorithm. Keep working at it, keep working at it. you're going to use algorithms that are based on this simple kind of comparison between points. It doesn't seem like it should take N log N, it seems like we should be able to find a linear time algorithm. and that's the hard way. The easy way is to know that reduction from sorting, and that means there's no point in to try to put in our effort to try to improve on the Graham scan. Graham scan gets it done in N log N. We can't do better than N log N so we might as well call it a day and move on to some other problem. and that's an example of reduction for proving lower bounds to help us guide our algorithm design efforts.