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

0:00 Intro

0:03 in this next subsection i want to talk about a lower bound that is a provable guarantee that no algorithm in a certain class of algorithms can ever perform better than a certain a certain bound a certain um minimal barrier that we cannot get breakthrough and that's one of the the core features in in algorithm theory that you're not only able to construct an engineer algorithm that are useful to solve problems in practice but also you can show often very rigorously what their limits are and this is this is the goal of this section to show on an ex on a simple example namely the uh the world of sorting how such a lower bound proof can look like and also what we can do about it with that uh let's get started on the comparison based model again i think this topic is something that many of you will have seen but maybe not quite from the rigorous perspective so let's spend some time on this

1:14 Lower Bounds

1:18 a lower bound is a mathematical proof that no algorithm can do better so it's essentially a statement about all algorithms and these are very hard to prove if you remember from the proof techniques this is a statement that is all quantified over all algorithms it's a very powerful concept because it's an impossibility result that is proven rigorously mathematically so there's no no regal way there's no way to discuss with this i'd like to compare it with conservation of energy principles in physics but it's usually much stronger i mentioned this before usually we can prove stronger lower bound than what the fundamental limits in in physics mean for machines usually our i don't know uh combustion machines reach limits much earlier than the conservation of energy would predict in computer science we're often much closer in that we can for many problems um achieve something that is at least asymptotically the same as the lower bound we find an algorithm that has the cost predicted by the lower bound up to constant factors and up to the fact that we have to do to restrict our attention to large inputs

2:48 but subject to these restrictions these are optimal algorithms i'm not the greatest fan of using this term here because optimal can mean many different things for different people but it's a useful a useful concept to

3:07 well to sell your your results probably uh that's what is what it's most useful for as i said it's a statement about all algorithms so we must precisely capture what this means what is all algorithms we already know one one way to do it any formal model of mod of computation is suitable to do this any formal model of computation of computers defines a class of algorithms but it turns out that the ram model is fairly powerful and so it's hard to prove lower bounds for it it's not impossible when people do this this is an active field of research but for for today and for here we want to look at a more restricted model where the lower bound proofs are simpler and this restricted model is the comparison model sometimes people don't make this very explicit so i want to make this very very explicit it is a model of computation it is a model of a computer that you can have in your mind but we cannot really build this type of computer it's a purely theoretical abstraction but one that will be essential in the proof in what follows in the next subsection so it's uh don't don't mistake this as a blueprint to build the next generation of uh pension whatever or intel core i

3:59 Comparison Model

4:35 whatsoever uh this is a mathematical abstraction so our machine is a is a box and we have a large array of elements that we try to sort in our case but the comparison model doesn't care much it's you can work with these elements in any way you like

5:06 this array is filled with objects of different sizes and the algorithm has a the the machine has a balance where you can put two elements and you can compare them and the outcome is is either less equal or greater and that's all you can really know about the elements that you're working with they're they don't have colors they're not numbers that you can divide the abstraction here is the only thing you know and the only thing you can do with these elements is compare them if you have to you can say which one is smaller which one is like which one is um bigger the other thing is you can move elements around so you can decide to swap two elements and then you just exchange them in the array so we can do comparisons

6:07 we can do swaps and pretty much that's it it's a very simple model of computation as i said it's overly restrictive you wouldn't be able to do much beyond sorting with it a few other related problems but that's not the point the point is to have a simple model that captures the essence of the sorting problem and then prove lower bounds so let's let's continue with this it makes very few assumption um very few assumptions on the objects that we're sorting as i said you can only compare some only compare them which is uh weird if you want to program with it well not too weird because merge sort and quicksort actually uh just use the element in that way but this is what makes the model uh helpful for lower bounds um because it's it's fairly general it doesn't make many assumptions that means it applies to many different things

7:09 and what makes this this problem uh there's this model nice for um for analyzing it is that every algorithm can be represented by a single uh relatively easy to understand object and that's the so-called decision tree now this is um is this a tree and i will i will show an example on the next slide in a second but i want to briefly explain what it looks like we only model the comparisons that our algorithm does so remember one decision tree means one algorithm there's a one-to-one correspondence between these

7:15 Decision Tree

7:57 and so we model only the comparisons we ignore the data movement the actual algorithm has to swap elements around the decision tree completely ignores this the nodes in the decision tree are the actual comparisons that the algorithm does and this could mean it could say we compare the element at position 17 with the element at position 42 and that can have a couple of different outcomes smaller equal or greater and that's what a single node in the comparison tree uh encodes and then the next comparison that the algorithm

8:40 does after these can depend on what was the outcome so if this is your node you can have different outcomes less equal greater and uh the next comparison is here in these child notes and that comparison can depend on what that comparison gave as a result all right and if you continue doing this you eventually reach a leaf node that doesn't have any further children and these leaf nodes correspond to an input permutation so one important aspect of this model is because we don't assume anything about the objects that we are given all that is really irrelevant is to learn which of the object is the smallest what's the second smallest what's the third smallest in other words what is the order of these objects in sorted order how would i have to rearrange them and learning this permutation is what decision trees encode if you restrict yourself to permutations that implicitly means we will never use this

9:18 Permutations

9:57 equal branch because permutations imply that all elements are distinct that's a minor assumption here that makes life a little cleaner but it's not a vital restriction you can extend the comparison model to handle these cases as well so here's an example of a comparison tree as promised this is again a specific algorithm on inputs of size three to not make it too big there's six different permutations of the numbers one of of three objects and because we don't assume anything about the objects we might as well take the integers one up through n we just are not allowed to make use of that knowledge so if we start out the algorithm doesn't know anything and any of these six permutations is is possible

10:11 Comparison Trees

10:51 to be the permutation that the input is in now the algorithm decides to first compare the the first and the second position in the array if the first position is smaller it decides to make another comparison namely the second and third so remember we start at zero so if we follow this left branch if the input is such that both of these comparisons turn out as less then the input must have been already in sorted order that's one of the possible outcomes and you see whenever you do a comparison there's a certain number of permutations that are currently compatible with your state of knowledge what you currently have learned about the input and then adding the next comparison splits this set of permutations into two parts and as soon as that part is a single permutation you have learned the exact order of the input and that's all we need for sorting you could then just uh move all the elements around to apply the inverse permutation and then the input is sorted i hope this example makes it a little more clear what these comparison trees look like and remember you have a different comparison tree for every input size

12:19 now what can we say about these trees um if we execute the algorithm on a specific input so maybe this is something to note here one comparison tree all right if i now if i now were to execute this algorithm on an input of that size i get a single execution and that's what this is talking about um so one execution means following one path in this comparison tree and the leaf that i reach encodes the input permutation on every step i do

13:22 in every note that i pass through i do one comparison so that means the length of this execution path is the cost of that execution and the height of the comparison tree is the longest such path so that's the worst case number of comparisons okay so in our case the height of this tree is we defined it as the number of edges 1 2 3 and that's also the number of comparisons that this algorithm does in the worst case any of these inputs is the worst case where you do three comparisons uh next observation is comparison trees are binary trees in this in this model where the outcome is uh is one of two things and that means remember we talked about this when we discussed binary heaps even if we make all the levels full from the pop we do need that many levels to get to a certain number of nodes so if we have l leaves at the bottom it turns out we need a height that is log of l rounded up

14:41 and finally the last last observation is if you want a comparison tree for sorting then you need all these uh all the permutations that are possible for an input to be in as leaves that is n factorial leaves and so the height is this log of n factorial which is asymptotically equivalent to n log n okay so uh wrapping up any decision tree

15:15 start a step before that any comparison any comparison based sorting algorithm corresponds to one decision tree per input size any such decision tree for a size n has to have n factorial leaves and it has to have size height i'm sorry height at least uh log of that which is n log n up to lower the terms so the height of this comparison tree must be n log n and the height of the comparison tree is the worst case number of comparisons of that algorithm so what we've proven is that

16:04 this second part here so that's that's not what i wanted to say i haven't written down the the statement of the lower bound which maybe we should so uh this is this is the conclusion from these two things

16:54 and well here we don't have a notation for greater equal but more precise let's write log n factorial here to make it easier any comparison based sorting algorithm needs at least log n factorial comparisons in the worst case and that is uh tilde n log n so we could try to squeeze that in here to make it complete and let's see

17:31 that is the lower bound the comparison based lower bound for sorting and we've seen that merge sort essentially achieves this we didn't really analyze this in detail we analyzed the number of element excesses where the constant factor was slightly different um if you revisit the analysis and look at the number of comparisons you do in a merging step uh that's the same that's linear in the size of the output of the merge and hence we get we get this bound for merge sword and so merge sort is an asymptotically comparison optimal algorithm even with the right leading constant

18:19 what's less clear is about these low order terms you can actually do with a good deal less than n log n comparisons you could in principle go down to something like n log n minus 1.4 n and it's a long-standing open problem in computer science whether you can do whether you can find a sorting algorithm that achieves this asymptotic number of comparisons in the worst case there's essentially been no progress since the early 60s on this question with some very recent attempts uh which haven't fully been uh reviewed yet but uh yeah this is as of yet it's a it's an open standing problem in in the theory of the problem

19:11 i want to briefly see if you were following this and so to test your understanding about the um the concept of decision trees uh let's do this question and i probably should show you this slide so that you can compare with this so the question is just for this input size is this a tree that's best possible in the worst case or is there any way we can sort three elements more efficiently

20:12 maybe time to switch to that screen okay we were at 39 for the first question so i will leave it open for a few more seconds you should see the results now yep so there's a large uh fraction of you who are saying yes this is optimal and this is correct and the reason for that is well um we have to look at the number of leaves there are six leaves in this case so we take the logarithm of that that's a number between two and three we can't really do sorting with two and a half comparisons in the worst case that won't work so the best we can do is round up and that means three comparisons are necessary to sort three elements and this algorithm also shows that this is sufficient because this is one way to do it there are others which were equally good so yes this is an example of an optimal worst case optimal sorting method for three elements

21:44 without exciting statements statement i'll conclude the section on the lower bound