Video 4-3: Comparison-Based Lower Bound

0:05 Next, let's um establish a bit of an a stronger impossibility result. We've seen an example of this for the sub subset maximum subarray problem where we said, okay, uh any correct algorithm has to read the input. The same will be true for sorting. If I have a sorting algorithm that pretends to sort the input without even looking at every element, I can clearly fool it in the same way. I can smuggle in another element and no matter where the algorithm places it, I can make sure that I give it a different value and then it had to go somewhere else. So the same same works here too. But we can do much better at least um with a bit of an assumption.

0:59 In the next section, we'll look at a lower bound for sorting, which means an impossibility result for any kind of thinkable sorting algorithm that it cannot be faster than a certain certain threshold. And um you should think of this as really the the kind of jewels in algorithm theory because there are very strong results that is is hard to find in other engineering disciplines. uh anyone can build things but uh well many people build things many engineers build things but often times you don't have a matching impossibility result that tells you oh the thing you've built is essentially best possible and in computer science we often have that for algorithms of various kinds sometimes um under some assumptions like the NP hardness theory and all of complexity but here it's not even with any assumptions just um a modeling a model of the algorithms that we allow. So you could say it's a somewhat unique feature and should be cherished.

2:02 So um if you think about what we're trying to do here is it's a statement where I say all correct sorting algorithms need at least so and so much cost in this case comparisons and uh such a statement it has an all quantifier over all algorithms that clearly needs a way to get our hands on what that is. we need a way to speak about a generic algorithm without writing down what uh what it looks like. We've actually seen an example of that and that was the whole point why I always stress this model of computation chapter that we have a concrete model in mind that is is suitable for these kinds of impossibility results in principle at least you can say what does it mean all algorithms well all possible word RAM algorithms that is what we want in practice if you can say something about all possible word RAM algorithms that's a strong statement uh here we'll use an even more restricted and simpler model.

3:07 And in that sense in a way you can say it's a stronger lower bound because um it gives you it gives you less power for the machine that you're using and you show still you need a certain cost.

3:24 The model that we're looking at here is the comparison model uh which is um allowing you to do free computation except for uh a very limited thing namely um for sorting you eventually have to determine the order of elements and in the comparison model there's precisely this one operation that I'm charging you for which is that you can compare two elements and I'll tell you which one is smaller which one is larger Uh, you can also move things around. Um, but what I charge you for is only the comparisons. Now, there's one catch though. This is also the only way you're allowed to access elements. And this maybe sounds not very limiting, but we'll we'll come back to that. The assumption is that all our algorithm is allowed to do with the elements that we're sorting is treat them as a black box and ask which of two elements is larger or smaller. I can move them around freely. All these things are fine. But I'm say not allowed to add up two elements.

4:32 They could be strings or database rows or any any such objects where addition doesn't make any sense. So all we all we have is comparison. You can say this is great because it makes the fewest assumptions about these objects that I'm sorting which means algorithms in this model are completely generic. If all they need is a comparison operator, say the comparable interface in Java, then I can use them for any objects. Also, merge sort and quicksort are precisely doing that. If you revisit their code, all they do is apart from moving things around and then uh scaffolding the recursion and so on, if they uh access elements, it's always in a comparison less or equal one thing less or equal another one.

5:24 Now, here comes the main trick for why this is a good model to prove lower bounds in. And I'll I'll show you some example of this. Um the the point is that because we only count the number of comparisons, all this extra fuss that algorithms tend to do working on an array and then recursing on the left side and swapping things around, we don't really care about that because all they are paying for is the comparisons. So I might as well treat them as being just asking comparison questions.

5:57 Now what what complicates life a little bit is that almost all sorting algorithms work by rearranging elements. So if they ask is ai less than aj these are no longer the elements that originally set in these positions but they've swapped things around. But for any algorithm you can remember all those swaps and kind of work your way back in the original input what was the element sitting at this position and you can trace the comparison back to these elements. The objects have kept their identity. They just traveled around. Okay. Um let me instead of uh reading the list here, show you some uh example.

6:47 This is what such a decision tree looks like. It uh is a binary tree. The nodes are comparisons. And here these indices always refer to the original input. There's no swaps. There's only comparisons. And what's in the box here next to it is the possible orderings of the input that are still compatible with the comparisons I've done so far. So the first comparison here says compare the first two elements a z and a1. then they're either a z is less than a1 or a z is greater than a1 and this splits the the world of possibilities into two parts right in originally this is for I should say this is always for a fixed number of elements that we're sorting and here the tree is for sorting three elements humongous uh list of uh uh elements to deal with so there's six possible permutations that these three elements could arrive among those six there's three that are compatible with having the first smaller than the second. So uh 1 2 3 1 3 2 3 1 all of these have index zero less than index one and the other three are on the right hand side. Okay, that's how this works.

8:09 Um if you have a have a concrete input say 2 3 1 then you can trace your way through the tree like this. You start in the root and compare these two elements a 0 a1 2 is less than three so I go left right now I ask uh the next comparison a1 less than a2. Okay, again this is this time this is larger so I go right and then I do another comparison between the the first and last and here again this is greater so I end up in this case and the leaf tells me ah the original input was 231 which is correct here right now you may ask where do these where do these weird trees come from and the point is that every algorithm you could Um you could imagine for example insertion sort corresponds to a specific for every n corresponds to a specific such tree. If you simulate it on all possible inputs you can generate this tree. This is what the website here does. And you can also do this for larger inputs. If you go to four elements it already gets a bit messy because there's these uh four factorial different inputs.

9:30 um but the structure remains the same. Okay. So again I can I can simulate one input here with insertion sort is a bit more interesting because it rearranges the elements. So let me do this once just to make the concept clear. My input is 3142 and we do insertion sort. So we build up um a sorted prefix. Initially the sorted prefix is just one element. Now the next the first interesting thing is comparing the first two elements and I'm trying to insert the one in the sorted prefix of just the single three but that I compare those two and I go right because three is larger than one. And what um what insertion sort now does is uh ah on top is the array. So insertion sort now moved the three to the left of the of the swap the one and the three. So that now the sorted prefix is 1 three. But it keeps tra um it keeps track of where the elements originally lived because the comparison tree wants to talk about the original indices. Now the next round starts for insertion sort. I'm going to pick the four and try to find its position in the sorted prefix three. For that I compare these two. But the original comparison is between zero and two. That's what you see here if you have good eyes.

11:04 So um you compare these and now uh you go to the left because the four was larger and so the sorted prefix 134 doesn't need any swap. It stays where it is and the next round starts. It immediately jumps to the next comparison which is the two is now inserted into the sorted prefix. So you compare the two and the four. Again four is larger so we go right. And uh now I'm I'm comparing I've swapped the the two in. Now I'm comparing two with the next element. And here you have to remember where these originally were. So it's actually a comparison between zero and three. So you do this comparison again. You go right and you swap the two left. Then you do another comparison between the first two. These were originally here. And after that you find oh the original input was 3142 which it was. That's what these comparison trees look like.

12:02 And note that um for every possible input that you have, there's some path down this tree to some leaf that contains only this ordering. That's all these these things do. Also, it's a binary tree. At every point, there's two options how the comparison can can go. Okay.

12:26 Uh formally, we don't have data movement. That's only a imaginary if you want. The nodes are comparisons. The child links are the outcomes of comparisons. A leaf corresponds to one specific input. And the next comparison in general may depend on the prefix of the path. The tree doesn't need to be symmetric.

12:46 Okay, here's an example again, the small one from the beginning. And uh a lot of the things here that I've I've said verbally written down again. The crucial thing now starts with this. If I follow such a path down, every step down is a comparison. So the cost of an algorithm is the path is the length of the path. The cost of an algorithm on one input is the length of that path. The worst case cost of an algorithm is the height of the tree. the longest path from any to any leaf from the root because comparison trees are binary trees. If they have L leaves, the height needs to be at least log of that of the number of leaves. That's how binary trees are. Uh go back to the heaps if you remember if you want to see the proofs. And because the comparison trees need to deal with all inputs of a certain size n, they need to have one leaf at least for each possible input n factorial.

13:53 And that means immediately we need the height to be log n factorial which you can work out to be in tilda asmtotic n log base 2 of n. You can work this out a bit more precisely just by doing proper real analysis or looking it up on the on the cheat sheet. That's Sterling's formula for the sake of the argument. Let's do that should be on here. Um Sterling's formula for factorials is is this this thing. Now you have to plug it into log base 2 and then uh a lot of things simplify. In particular this n / e to the power n becomes the leading order term of n log base 2 of n minus log of e * n yada yada yada few low order terms. Uh let's not be let's not care about the sublinear terms here but you can work this out a bit more precisely. That's what I'm saying here.

15:00 Also observe that this is the cost that merge sort had. Merge sort needs n login comparisons. We didn't do the analysis for that but it's basically dividing the element visits by two. So we've kind of done that which means merge sort is is very strongly optimal in an asmtoic sense if you count comparisons. It's doing the right number of comparisons including the constant factor even.

15:33 Um to double check understanding, let's look at this and I'll go back to the previous slide in a second. If you look at the comparison tree from the previous slide, is that an optimal sorting algorithm for three elements?

15:46 Comparison trees are always for a fixed input size, right? A general algorithm gives you a different tree for each n and they get bigger and bigger. This is for three elements only.

16:28 course, the meta question that is not written in the question, but that you're prompted to think about is how would I know? Uh, anyone still busy thinking? There's a couple people online.

16:52 Let me show some answers. Then we have a half half split even though it's small numbers. Okay, the majority flipped. The majority decided on this voting day. [snorts] uh voter turnout could be couldn't be better in this room I guess. So the majority is right. Let's quickly analyze this this algorithm here. What is the worst case cost of this algorithm to sort three elements? If someone wants to shout it in, how many comparisons does it do in the worst case? Yep.

17:35 That's right. Um, but I'm I'm talking about specifically this tree, right? Um, and worst case now is over the inputs, which is over the leaves. And um, I mean, the longest path I can I can find is something like this. So I I have one, two, three comparisons on this way. And there's nothing that's steeper. So it has worst case cost three. Now, is that good or bad? How would I know? Well, for sorting three elements, how many comparisons do I need?

18:11 Yep. Yep. Because log of 3 factorial, otherwise known as six, is some number between two and three. I can't have a fractional number of comparisons, so I need to round up. That's um the height is always an integer. So you round this up and that's three.

18:35 So there's no way to get all six permutations sorted with just two comparisons. In this case, you can also just work out brute force, right? I mean, you don't learn enough, but really um with two comparisons, all you learn is four bits of information. So you can distinguish four different things, but there's six, so it doesn't work. That's that's what this is getting at. And this is maybe a good point to go back to this um illustration here where you can look at the small comparison trees for some other sorting algorithms. So insertion sort if you go to okay maybe let me draw this um just as a stylized binary tree. If you go for insertion sword on five elements, this is already 120 leaves, right? Gets a bit big and you see there's quite some difference. Some leaves are high up and some leaves are far down. The red line here is where the optimal uh bound is. This is log of five factorial rounded up, otherwise known as seven. And so you see there's quite a few elements that are below seven.

19:49 Shocking news. Insertion sort is not generally a worst case optimal sorting algorithm. How about something like merge sort? Aha, much better. Okay, you see it's not precisely optimal. It sometimes needs one extra comparison more than it should more that it could potentially. Note that this lower bound is just an impossibility result. It says you cannot possibly have all leaves above that line. it doesn't guarantee that there is a way to put all the leaves on that line or above. That's not ruled out. And indeed, here you can just brute force um and find an optimal tree. Here it is possible with five elements. You can get them sorted with seven comparisons always. And here's one way to do it.

20:41 That's what I initially mentioned. Um this is an open problem. If there is some some simple way to describe these trees in general, I can for every fixed n I can go through all possible binary trees and I'm going to find the best one. People have done this up to certain n. But of course this is not a general algorithm. It's not a sorting algorithm in the usual sense. And it's as of yet unknown whether there is a clean simple rule that tells you on this input of a million elements, this is the first comparison to make so that you're on the on track to being optimal.

21:15 Okay? And you can look at some other some other fun inputs and uh you see that they're far from optimal uh if you just look at comparisons. I'll leave that for you to play with. What you should take from this is um that merge sort is essentially best possible with costmetric number of comparisons and we have this matching upper and lower bound up to even the leading order term with constants. If you want to look more closely all of this is just for your fun and maybe you find it interesting. uh maybe I find it interesting and that's why it's on the slide but it's not part of the exam material. The lower bound evaluated a bit more carefully gives you um this linear term as well and the linear term this this factor log base 2 of e is 1.443 443 and so note this is negative so um the lower bound is actually a bit less than n login by this linear term and um merge sword also gets uh a negative term here it's this periodic function that we've seen where here the c is somewhere between this n1 and one um there is a better algorithm and it used to be it doesn't say the the year board Johnson I don't know if you can read this 1959 up until a couple of years ago I used to be able to say the latest progress on this sorting question is from 1959 predating quicksort predating most computers uh no longer true I'll comment on that in a second uh there's an algorithm called merch insertion that used to be the general best method for comparisons um it gets the number of comparisons very close to the lower bound.

23:12 Unfortunately, it uses uh at least quadratic time to find the comparisons. So, not completely practical. Uh but we used it as a base case in some other uh divide and conquer algorithm where you can you can do this to lower the constant. And then um there's a there's a a more recent paper preI nothing to do with that where this was lower claimed to be now optimal up to the linear term as well. Uh the paper is is published in some non-core algorithms journal and I don't know if anyone has fully digested the proof. It seems correct from like there's no known counter examples are so known but it hasn't been fully vetted in the way I would have uh wanted or would be able to trust it. It's a bit hard to read but it seems at least that linear term um is also closed now.