Video 3-4: §3.3 Comparison-based lower bound

0:00 Lower Bounds

0:01 much so in this in this section we'll talk about the comparison based lower bound for sorting and this is one of the the gems in computer science that you can not only engineer some solution to a problem but you can also have mathematical proofs that you cannot really go much beyond what you've already done you cannot do much better than what you know and i mean this is this is not uh completely unique to computer science i put this uh this well the the principle of conservation of energy and physics here is one thing uh at some point the efficiency of some engine is is lower bounded by the fact that you can uh can't have a perpetual mobility and stuff uh but the efficiency of actual combustion machines is far away from this theoretical limit so there's still room to go for engineers to improve engines and in computer science i mean this is also true but in some cases like for sorting we we have a matching lower and upper bound and the distance between the two is really uh diminishing so you can say we know the best possible way to sort and the same best possible way to sort is actually practical so this is where much the theory is much closer to

1:24 the practice in computer science in some of these algorithms i think this is something that's not celebrated enough in computer science we can we can build cool systems and we can have meaningful mathematical proofs in mathematical models that are very close to saying and this is essentially as good as it gets even if you try to be ever so smart

1:50 okay maybe it's not unique but it's a feature of computer science that i i like a lot so we can speak of optimal algorithms even though that term might be a bit overused

2:03 now what is behind these lower bounds in computer science if you unwrap this it is a statement about all thinkable algorithms because you're saying every algorithm needs at least that many comparisons to sort that would be the statement that we're looking at and what's behind this is a way to say what is that all algorithms we have to make a way uh we have to formalize this and for this you need mathematical models that's again something i stressed this in in unit one i guess five times but uh one more time won't hurt mathematical models are not just to torture you they're really useful because they can prove these lower bounds and one model we've seen is the word ram model and so you can say all algorithms is all possible algorithms on a word ram that's a formal way to do it it's a good way to do it but it's it's one where the lower bound proofs become absurdly complicated so people usually go to a simpler model where the algorithms are a bit more restricted in what they can do but the lower bound proofs become easier so let's make this concrete what we do in our case is we say instead of talking about arrays and words and bitwise operations and all

3:20 The Comparison Model

3:28 that we just allow the following two operations we can compare two elements so we're given an array the machine is it's a custom build sorting machine it can only do sorting it starts with an array it can take two elements and compare them and the other operation is it can move elements around so we can have some leeway how we do this we can swap elements or we can allow extra space and or get read the value from here and write it here that's that's okay because the up the cost of a program on this comparison machine is only the number of uh well for for the proof that we'll see is only the number of comparisons you can count those two but for the interesting sorting methods there one is within theta of the other

4:27 what's good about this model is that it makes very few assumptions about um what we're doing so it's very general in terms of the objects that we're sorting so you can apply it to many scenarios

4:43 and the algorithms that you study here are general another good thing is that the algorithms we've just seen they fall under this model you can formulate merge sorting quicksort in this abstract comparison based world because all they do is they compare two elements and they move elements around

5:04 and the last good thing about this model it is so restricted that if you only count the comparisons every program on this machine on this comparison model machine can be can be written as a decision tree so what this is we'll see an example on the next slide

5:29 i stress we count only comparisons and ignore the data movement because the they will dominate in in the statements we make um let me show you the example first and then we may come back so here's a concrete decision tree for sorting the absurdly big array of three elements and the way to read is is is as follows the algorithm says you're given an input and the first step you do is you compare index zero and one and then there's two possible outcomes either a zero is smaller or not so if it's smaller you go to this branch otherwise you go to the other branch and then again so these two happen to be the same comparison they compare one and two on both sides but that's not in force they can be different okay so again if this was the case then you do another comparison and if this comes out as less or equal then you actually know the original order of the input because you basically checked for sortedness zero was less than one and one was less than two that means they're already in order and there's a symmetric case if it comes out the up the opposite way then the input must have been like this permutation completely inversely sorted

6:54 and for the four other ways how you can order three elements there's also one outcome okay so just to stress these parts a bit the notes in this tree are individual comparisons the next comparison can depend on the outcomes the different subtrees need not do the same comparison even though in the example they do the child links left and right are the outcomes of one comparison and each leaf at the bottom of the tree is one possible order of the input

7:35 Comparison Lower Bound

7:40 so one thing to stress here is this is one comparison tree now what is this in terms of an algorithm it is one concrete algorithm for one concrete input size okay a decision tree like this is always tailor made for lists of size three but that's okay we can say an algorithm that works for arbitrary lists sizes it induces one such tree for every input size and the tree has to be different because it's getting bigger and bigger but for the usual algorithms it has a certain kind of structure that you can figure out if you want so one comparison tree is one algorithm on a specific size okay and if you fix the size the different comparison trees gives you give you all different possible algorithms now why do we why do we like to force ourselves to think in these terms because this way of representing an algorithm allows us to analyze what's going on

8:48 one point is if you want to to know how costly is an execution of this algorithm shown in this tree on a specific input then you say if the input was actually ordered like two one three you would have to follow this path and well you run through three comparison nodes so the algorithm used three comparisons in this case and in another case it used only two so the number can vary and that's just the depth of the leaf in the tree which also means the height of the entire tree is the worst case number of comparisons and by extension if you wanted i think it's not on the slide but still true if you take the the average depth of the leaves that's the average complexity of the algorithm and well the highest leave is the best case i mean once you understood that the depth is the number of comparisons i guess these statements are not so hard

9:50 another observation now that's obvious from the example these decision trees are binary every comparison node has just two outcomes in this model so if we have a tree with l leaves we need to have a tree of height log n log l rounded up it's the same argument as we've used for binary heaps the thing is if you fill the heap the best case you can have in terms of height is every level is completely full and then the analysis from heap supplies so the height is at least log l and now comes the last uh the last crucial step if we want to correctly sort any list of n items with such a decision tree so if that's if the decision tree is to represent a correct sorting algorithm then it must have one leaf for every possible ordering of the input because if it would not distinguish all possible orderings it can't possibly sort correct it would treat two algorithm two inputs the same that are differently ordered so that can't really work out

10:58 which means the number of leaves must be at least n factorial that's the number of ways to order n elements and so by putting this together with that the height of such a decision tree has to be at least log of n factorial and now that can be evaluated to be asymptotic to n log n that's where all this n log n comes from because log of n factorial is roughly n log n okay you can make this statement more precise sometimes that's useful i won't obsess about this too much

11:43 an immediate observation is that merge sort uses asymptotically n log n comparisons so it is an optimal sorting algorithm in the worst case for the number of comparisons and not just theta and log n but precisely 1 times n log n plus lower order terms so in the tilde asymptotic it's optimal with the correct leading factor the constant factor of the leading asymptotic term okay

12:15 remember we had this 2n log n for merge sort where i said remember 2n log n for merge sort that was the number of element visits or array accesses and here i'm counting comparisons so the factor 2 comes from from this distinction if you merge you have to read everything once and write everything once but the comparisons is only one per element

12:42 and that's the problem that i stated uh on the motivation slide already more precisely stated it's not clear if if we have an algorithm that is according to this more precise lower bound optimal up to a little o of n term in the number of comparisons although i might have to update the slides there was some progress on this very recently like uh last last year the year before must have been in the time since i last thought this uh but this has not been peer reviewed it's absurdly complicated algorithm and no one knows if it's correct i think that's the state of the art still but at least some someone claims they have found such an algorithm and so pushing this boundary a little further

13:33 Clicker Question

13:41 take this a little bit back to the concrete realm there's a comparison tree on the previous slide this one and the question is can you do better can you find in terms of the worst case another comparison tree for three elements that uses fewer comparisons

14:45 three two one that didn't lock oh come on and that's correct it is optimal uh you can't do it with fewer than three there's different ways to prove it i mean the easiest is probably just insert into the lower bound