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

0:02 in the next section I want to discuss a lower Bound for sorting an impossibility results that basically implies that the two methods we've just seen merge sword and quick sword are almost best possible but in a specific sense and uh I want you to dig behind this superficial statement uh so that you know what it means a bit in more detail a lower Bound in algorithms is usually a synonym for uh there's no there's is a synonym for an impossibility result there's no algorithmic there's no algorithm that can do better than a certain certain um performance and it has to be mathematically proven so it's a uh it must be a rigorous statement and in in that sense it's a super powerful concept because it means if you have an algorithm that's close to that bound you can stop searching right um so a bit I compared it to this conservation of energy principle in physics earlier that's that's the kind of generality that we're hoping for uh it seems to be seems to be somewhat unique for computer science to get so uh so close to these lower bounds um you will often hear this this algorithm is optimal for that problem I don't love that term because it often means it often hides things under the

1:25 rug uh it's often better to unpack what optimal really means and the whole point of this in the next subsession is to S make make you bit sens sensitive to uh uh what's hidden behind when people call an algorithm

1:45 optimal right but what what do we have to do to prove such statements um I want to point out that this is essentially a statement for all algorithms it holds that their running time is at least this or this that's the kind of statement we're we're looking for so we need to prove a statement for all possible algorithms so that's um that's quite a tough tough order tall order and in particular we need a notion to say what are all possible algorithms so any lower bound assumes a model of computation necessarily it could be if it's powerful it could be the ram model the one that we discussed for analyzing algorithms um but often lower bounds restrict computation to something even even more primitive just to make reasoning about the model easier and that's what we'll do here as well um what we'll use is the comparison model which is a standard model also outside of of this specific use case uh this model says okay I'm abstracting very much away from computers what they actually do I only count when they um compare two objects but that's also the only thing they can do so I can take two objects in an ARR AR I can compare them and I'll tell you which one's smaller uh

3:03 and you can move move elements around but uh I'm not going to charge you for this so the cost for running an algorithm is just um is just these two operations I don't charge you for how to come up with your decisions and you could even say um the lower bound will will use is even more strict it only counts the comparisons it doesn't care at all about moving things

3:37 around so this sounds like a silly machine right we don't have computers that work like this but for lower bounds that's that's kind of good this makes very few assumptions you can build many different machines that can compare elements and move them around and for a lower bound that's good because it means the statement we'll get is more General so usually for algorithms a more detailed model is better because then you can react model reality closer but for lower bounds the opposite is true the important bit here is that both merge sword and quick sword are inside this model you can formulate them so that they only work by comparing elements and moving them around we've basically done that in in my high level explanation anyways so they're they're part of this model they're captured by what we'll say and now comes the the big important step so this is this is the uh the key Insight that we have to take I don't know uh how can I highlight this without cluttering it up too much the model has this nice property that we can say what algorithms in this model look like specifically because they're only allowed to compare elements all they can really uh do to base decisions on are comparisons and comparisons in this

4:55 model this is uh only one type of compar comparison say less or equal so it has two outcomes yes or no and then the algorithm is not allowed to do anything else with the object so everything it has to do with moving them around has to be based on the yes or no answer from comparisons so in that sense um we can model computation by having comparison nodes where there's two possible outcomes and then the pro the the algorithm branches in two possibilities it either follows a left or a right path

5:34 we ignore any movement of data in between so instead we'll only look at the comparisons and what next comparison is done can of course depend on what you've done before so you have two different sub trees um but that's that's pretty much all let me show you an example I think that's

5:59 clearer uh so this is um for a very small array for three elements one possible algorithm in this comparison model how does the algorithm work it starts by comparing the the first two elements position zero and one what I denoted below the notes is the possible orderings of the input that are still uh feasible or compatible with where we currently are so I compare the first two elements and the two outcomes are either a Zer is smaller or not um then you can filter out what that means for the different input orders and in this case the algorithm doesn't actually change what it does it does the same comparison in both cases so if a z is smaller than A1 it checks if A1 is also smaller than A2 if that is the case then the input was already sorted we know that then and the algorithm could then decide not to rearrange anything otherwise if we go in this Branch so we know a Zer is smaller than A2 but uh A1 was bigger than A2 then we still have to compare the first and last element and depending on how that goes um we know that the input had this order originally and in both cases the algorithm could then decide ah okay

7:18 now I know what to do and just reassign the elements so that it's that it becomes sorted that's how this so this is how In the comparison model algorithms look like there comparison trees where the nodes tell you these are the two positions in the original array I want to compare those are the two outcomes and depending on that the next thing happens the important bit is that every algorithm In the comparison model can be formulated as such a tree so we have a way to reason about all possible algorithms by studying all possible trees and trees are much easier to handle than General algorithms with whatever complicated

8:08 code and I comes the step where we use this this knowledge what all all algorithms look like to get an impossibility statement first of all uh this is one concrete algorithm but it's the algorithm shown on all possible inputs in the tree if I have one specific input for example this one what will happen is that I I always follow this path down the tree because that's what actually happens if I call the algorithm with this input so one execution of the algorithm is a path from the root down to a leaf and on every step I make one comparison because that's the way we defined this tree every step down is doing one comparison and nothing else happens in between that we count that means the height of the comparison tree is the maximal number of comparisons this algorithm ever does on any input in other in other words that's the worst case number of comparisons that this algorithm does but that's still talking about one concrete algorithm this this kind of tree that we that I drew here the next piece is ha these are binary trees I only have two outcomes and uh with talked about this before if I have a binary tree uh with a certain number of nodes I can compute how tall

9:36 it has to be I can lower bound its height uh here it's very slightly different instead of having the internal nodes we have the number of leaves but it's it's very similar it's even easier in a way um if you have two leaves then you need at least height one if you have four leaves then the most balanced thing seems intuitively to give you the the less the the least Tall Tree uh so the height if you have L leaves um is at least log l because whenever you get one step down you can at most double the number of leaves that's all that's behind this so we now have a statement that if we have a number of Leaves we need a certain height the last thing to nail this down is again Now using something about the problem we're trying to solve we're trying to sort a list of n elements now we need to do a little bit of combinatorics how many different orderings are there if I have n elements the numbers one up through n there's n factorial of those n * n minus 1 * n minus 2 and so on many different ways to see this but you could say um I first pick the position for the largest number

10:58 n I put that somewhere in my array then I have n minus one choices for the next number for the number n minus one so I'll put n minus one in one of those n minus one choices that I've left so in each step I have one less choice but each of those I can combine that's what n factorial comes from so a sorting algorithm needs to work differently on every different input or permutation it's supposed to sort the in so the output should always look the same irrespective of the order original so it has to do different operations otherwise it wouldn't end up with the same state from a different input

11:57 again yep um so the way to read this um that statement here is saying we don't have more than one of these orderings in any of the leaves to turn this into a sorting algorithm this is basically just uh the the reconnaissance stage it's just the Recon part learning in what order the elements are and then you would have another step that rearranges them into sorted order the important part is the rearrangement needs to look different for every possible input

12:49 but yeah here it's already sorted here I have to swap the last two for each of those you can Define number of swaps let's maybe take take it offline um uh the key Point here is you need a different leave for every possible input permutation because you have to act differently to turn it into sorted order so that means if we want to sort n elements we have to have n factorial leaves we know for so many leaves we need log of that as height and uh log of n factorial is roughly n log n you can upper bound it lower bound it to be more precisely you can give statements like this uh but that's not my my key Point um it's enough if you if you keep that in mind and that it's asically equivalent to n log n so that means what does that mean that was the lower bound on the height of the comparison Tree on any comparison tree and the height was the worst case number of comparisons so that means um any algorithm any comparison tree any algorithm In the comparison model must do at least n log n comparisons in the worst

14:09 case um merge sword actually achieves this including the right constant in front of the leading term so it's in that sense uh including the linear the linear the constant factor it's uh it's optimal for comparisons um yes if you if you want to zoom in a bit closer it's still open whether we can do this um there's a slideer question looking at the concrete comparison tree I'll leave that for you to have a look at at home um it's not so

14:49 vital so let's uh let's leave it with that um just to recap again very briefly the steps we formulate a model for all algorithms in this case that was all comparison trees we use something about the problem that we're trying to solve sorting in this case to argue that this all these problems all these programs have to have a specific shape in this case all of them need to have many leaves and then arguing from the shape of the programs that it's a binary tree you can tell something about the cost and that gives you a way to lower bound the cost so every algorithm in this model needs to use so many