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

0:00 <Untitled Chapter 1>

0:03 in the next subsection of the Sorting chapter I want to talk about a lower bound so I teasered this earlier and said computer science is fairly unique as an engineering discipline that we can prove lower bound statements but we can also attain so we're we have matching impossibility results and just in the realm of possible we can actually get and so we want I want to show you this um this is the simplest example of such a bound it's not so much that this Bound in itself is the most exciting in the world but it shows you the flavor of lower bounds and there's many more uh of such algorithmic lower bounds

0:42 um and I just think it's useful to have the the flavor of how these work and their limitations so what is a lower bound it's a mathematical proof that no algorithm can possibly do better than some certain performance uh guarantee um so it's an impossibility result it says it's not nothing's better than x I can can always compare this to uh some Elementary principles in physics but I pointed out that we're we have much stronger lower bound than this in computer science so often we can speak of optimal algorithms even though that term is a little uh simplification is simplifying in that you have to be quite precise about what this optimal really means but you can have an upper and a lower bound that match so I will come to that when we talk about this specific case here

0:44 Lower Bounds

1:42 now this this is all great so we like lower bounds because there are these definitive statements about how good algorithms can be how can we get a lower bound uh to prove a statement remember unit one like all this basic stuff it's a for all statement right for all algorithms the cost is at least this and that so we need a way to formalize what this means all algorithms now we have a way to do that those those are our language models they're exactly doing that so uh we could take our word Ram model and say every possible word Ram algorithm has such and such of a performance and this is the gold standard that we would like to have it turns out this is quite um quite more complicated or more demanding on the technology on the techniques so instead we use a more restrictive model which is also typical if um if you can't seem to find a meaningful lower Bound in some more General model you you look at some restricted one first not because that's the most relevant for practical purposes but it guides you towards where exactly the the

2:50 hardness of a problem lies in our case this simple model will be the comparison model and this is not too far away from how we Define sorting in this unit but we're a bit more specific about saying the only way how you can learn about the order of elements is by pairwise comparisons so you can take two elements and ask which one is smaller or if strictly speaking is a less or equal than b that's the only query we are allowed and the other part is is not as essential but um we assume that we have one array of elements and we can swap them that's the way of moving them uh is not as much of a restriction but um okay I'll comment on on what this does not allow uh the cost in this model is the number of these operations and we count them separately and we will focus on comparisons that's for for this section at least so the number of of such comparisons two elements is a lesser equal than b yes or no that's our main metric for success um in a way that's that's a great model because it's very generic almost all algorithms we we are seeing are of this kind they can be formulated like this

2:53 The Comparison Model

4:12 so we like that we have seen two examples um the model also makes some restrictions so it it for example says we cannot take two elements and add them up or take the average over the all the elements in the array that's not something that the comparison model allows it only gives us the this comparison operation so we will see that this this can be a restriction but for now that's that's the model um merge sort and Greek sort follow this so it's uh we're not talking about the empty set of interesting algorithms at least

4:57 now what's what's useful about this model is that it allows uh apart from describing an algorithm as a program on a word Ram or similar models it allows a different way to view a program if you just count the number of comparisons so um

5:19 uh I'll I'll say let's let's replace this with comparisons in this subsection I want to focus exclusively on those if you do that every comparison based sorting algorithm can be seen as a decision tree where we only keep track of what have we learned about the relative order of the elements I'll show an example in the next slide but a few comments so this is completely ignoring the effort we have to move data around but if we only count comparisons and everything else is for free that's all right

6:01 um and for the rest let's see the example first so here's here's one concrete comparison tree it is a comparison tree for sorting three elements and it's one specific algorithm so just just to see how this works uh the algorithm first asks the first two elements in the array is a0 less than A1 less or equal and there's two outcomes yes or no and then depending on the outcome that's presumably an if statement the algorithm can do two different things right it can continue in different ways because it has to react to whether the element uh in position zero is smaller and in this case it actually does the same next question the Second Step the next comparison asked is the same in in either outcome and it compares the positions one and two but this could have been different in general uh you're free to do different things in the different branches

7:04 and now let's just Trace one of those branches down to a leaf if zero was less than one and one was less than two then the list is already in sorted order and so um we'll write this here in in terms of this permutation of one two three that shows you the relative size of the original input so it was already sorted if you have it the other way around zero is bigger than one and one is bigger than two then it's inversely assorted and the other two cases are somewhere in between and do require a third comparison in this algorithm okay so that's that's one one such example of a comparison tree um and now just a few remarks that we'll use um straight after every of these internal nodes is one comparison that the algorithm does and there's the two outcomes so we have two different parallel universes depending on what the input is in a way uh every such comparison tree represents one algorithm on one input size but all possible uh all possible outcomes for all possible inputs okay one algorithm one size all inputs of that size uh what else um the next comparison can depend on the subtree I mentioned that uh even though our algorithm here it doesn't make use

8:32 of that much it stops early in one branch um the the outcomes are on the edges and then the final point is the leaves at the bottom of the tree they represent one potential ordering of the input so we have a permutation in all the leaves

8:54 okay that's that's cute right that's a cute alternative way to represent a sorting algorithm why would we care we can use this um simplify our thinking about this about this specific algorithm but also about any algorithm because the the powerful statement is any sorting algorithm that's comparison based must correspond to such a tree we may not know how it looks like in detail but there is one every execution of the Sorting algorithms on one specific input is following One path from the root down to some leaf so the height of the tree is the worst case number of comparisons remember height is number of edges which is the same as number of these these uh dark red nodes and that's the number of comparisons and height was to them maximum number of such steps so that's the worst case input

9:53 now how tall must this tree necessarily be we remember from from last unit we talked about binary trees at length and we found that if we have L leaves then well we talked about having a certain number of internal nodes but you can translate that to the leaves as well every internal node must have two edges and so the leaves must be attached to somewhere a binary tree is always exactly one more Leaf than internal nodes so the two things are are very similar in this sense so if we have L leaves we necessarily have a height that's at least log of the number of leaves that's virtually same argument as in the last unit and now we can put these two things together the assumption is we're making a statement about all correct sorting algorithms we're not interested in bounding uh the cost of an algorithm that doesn't actually sort but if it has to properly sort every possible input it needs to have a branch leading to any of the possible input permutations in other words we need one leaf for all possible orderings and the number of orderings is called n factorial yes just you have n choices for where the smallest element goes then you take that out so there's n minus one choices for

11:17 the second smallest and you keep going so n factorial is n times n minus 1 times n minus 2 blah blah blah all the way down to one I guess you have seen that before so we need so many leaves that means the height has to be at least log of that Beast and that's again log of n factorial is a fairly inconvenient function but asymptotics to the rescue we can express that in a much simpler way for example as a Theta notation it's the same as n log base 2 of n asymptotically so in this sense if you divide it the ratio goes to one uh you can even be more precise if you want so you can say it's it's this plus uh a discrepancy that is bounded in terms of order login we haven't talked about such more precise approximations and I won't really use them but some of you will have seen more stuff on asymptotics so like is this essentially just showing this there's more behind this you can get more precise asymptotic approximations if you want or where it's useful

12:31 and so you may have been like I I may have dive deep in the details now but this is it right this is our lower bound because it means every correct sorting algorithm at least in the worst case must use asymptotically n Times log n comparisons so that's pretty cool because that's a statement about all possible sorting algorithms if they are comparison based and we can show something about their worst case right

13:02 now we can compare this with algorithms that we've seen and for example merge sort achieves exactly this up to the first order approximation exactly the optimal part best possible number of comparisons we haven't actually analyzed it that way if you remember the result per merge sort I did have on the slide was 2 times n log n but that was element visits so if we visit an element for reading it in the merge and then for writing it that counted as two visits because it's two different positions uh but there's really just one comparison happening you can always charge the comparison to the element that's written to the output and so every element is written to the output in each merge just once so it accounts for one comparison and that's that's the worst case at least okay

13:54 now it turns out this is one of the things where we don't don't know much more uh there's some recent recent paper trying this that's so complicated I'm not sure if someone has understood it yet and checked if it's correct um prior to that paper at least no one even had an idea whether this is easily doable so if you want to be more precise and also get this this next term of the approximation uh matching the lower bound that's still a bit unknown I don't know how excited you are about this bit but I thought it's worth pointing out that even these very fundamental problems uh are not completely solved and can be can get quite quite tricky

14:40 Clicker Question

14:44 okay A little innocent question um just to see if uh if you're awake the question is does the tree I'll show you in a second again correspond to an optimal worst case optimal sorting algorithm for that input size right remember it's always for a specific input size

15:12 okay I have 57 or so people voting for the attendance code 33 . 49 okay 51 so uh it's quite interesting it's a fairly even split um so let's see what's happening here

16:38 Comparison Lower Bound

16:43 what does it mean to be the comparison tree for a worst case optimal algorithm in this case so let's unpack that first of all we're only talking about size three because as I said 500 times now comparison 3 is only for a fixed size so any proper algorithm merge sort works for any input size so for any input size it would generate one such tree they get really fairly huge to draw because they're exponential in size so I didn't put one on the slide for much much larger um but they exist now for this for this specific one we have three elements to sort that's six permutations as you can just count on the slide here they are so we need to put those in the leaves now if you just do the math uh six is between four and eight so log base two of that will be two point something rounded up is three right so there's no chance with three elements to sort all permutations with two comparisons it's not possible the simple argument if you have just two comparisons you can only distinguish four different things simple coding argument right zero zero zero one one zero is one one that's all I I don't get to six so I need to spend

17:58 three comparisons sometimes and so that's what the question was really asking does this tree have height three which I guess you all know how to check so the answer is yes uh

18:14 which also shows you like for a very small number of elements it's not so hard to find an worst case optimal algorithm the challenge is to do this in the general case