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.