4.5 - Interpretation of 3 cases - The master method - [dsa 1] by tim roughgarden

This video is the second of three that describes the proof of the Master Method. In the first of these three videos we mimicked the analysis of merge sort. We used a recursion tree approach which gave us an upper bound of running time of an algorithm. Which is governed by a recurrence of the specified form. Unfortunately, that video left us with a bit of an alphabet soup, this complicated expression. And so in this second video, we're not gonna do any computations. We're just going to look at that expression, attach some semantics to it, and look at how that interpretation naturally leads to three cases, and also give intuition for some of the running times that we see in a master method. So recall from the previous video that the way we've bounded the work done by the algorithm is resumed in on a particular level J of the recursion tree. We did a computation, which was the number of sub problems at that level, a to the j, times the work done per sub-problem, that was the constant C times quantity N over B to the J raised to the D and that gave us this expression. Cn to the D times the ratio of A over B to the D raised to the J. At a given level. J. The expression star that we concluded the previous video with was just the sum of these expressions over all of the logarithmic levels, J. Now, as messy as this expression might seem, perhaps we're on the right track in the following sense. The master method has three different cases, in which case you're in is governed by how A compares to B to the D. And hearing this expression, we are seeing precisely that ratio. A divided by B to the D. So let's drill down and understand why this ratio is fundamental to the performance of the divide and conquer [inaudible] algorithm. So really, what's going on in the master method, is a tug of war between two opposing forces. One which is forces of good, and one which is forces of evil, and those correspond to the quantities B to the D and A, respectively. So let me be more precise. Let's start with the parameter A. So A, you'll recall, is defined as the number of recursive calls made by the algorithm. So it's the number of children that a [inaudible] recursion tree has. So fundamentally, what A is, it's the rates at which sub problems proliferate as you pass deeper in the recursion tree. It's the factor by which there are more sub problems at the next level than the previous one. So let's think of A. In this way. As the rate of subpropabifliation, or R.S.P. And when I say rate I mean as a function of the recursion level J. So these are the forces of evil. This is why our algorithm might slowly, is because as we go down the tree there are more and more sub problems, and that's a little scary. The forces of good, what we have going for us, is that with each recursion level J we do less work per sub problem and the extent to which we do less work is precisely B to the D. So I'll abbreviate this rate of work shrinkage or this quantity B. To the D. By R. W. S. Now perhaps you're wondering why is it B of the D. Why is it not B? So remember what B denotes. That's the factor by which the input size shrinks with the recursion level J. So for example if B equals two, then each sub-problem at the next level is only half as big. As that at the previous level. But we don't really care about the input size of a subproblem, except inasmuch as it determines the amount of work that we do solving that subproblem. So that's where this parameter D comes into play. Think, for example, about the cases where you have a linear amount of work outside the recursive calls, versus a quadratic amount of work that is considered the cases where D equals one or two. If B = two and D = one that is if you reverse on half the input. And do linear work, then. Not only is the input size dropping by factor two but so is the amount of work that you do per sub problem and that's exactly the situation we had in merge short where we had linear work outside the recursive calls. The thing about D = two, suppose you did quadratic work per sub problem as a function of the input size. Then again if B = two if you cut the input in half, the recursive call's only gonna do 25 percent as much work as what you did. At the current level. The input size goes down by a factor two and that gets squared because you do quadratic work as a function of the input size. So that would be B to the D, two raised to the two or four. So in general the input size goes down by a factor B, but what we really care about, how much less work we do per subproblem, goes down by B to the D. That's why B to the D is the fundamental quantity that quan, that's governs the forces of good, the extent to which we work less hard with each occursion level J. So the question that is just what happens in this tug of war between these two opposing forces? So fundamentally, what the three cases of the master method correspond to, is the three possible outcomes in this tug of war between the forces of good, namely the rate of word shrinkage and the forces of evil, namely the sub-problem proliferation. There are three cases one for the case of a tie one for the case in which the forces of evil win that is in which A is bigger than B to the D and a case in which the forces of good wins, that is B to the D is bigger than A. To understand this a little bit better what I want you to think about is the following. Think about the recursion tree that we drew in the previous slide and as a function of A verses B to the D think about the amount of work you've done per level. When is that going up per level? When is it going down per level? And when is it exactly the same at each level? So the answer is all of these statements are true except for the third one. So let's take them one at a time. So first of all let's consider the first one. Suppose that the rate of sub problem proliferation A is strictly less than the rate of work Shrinkage, B to the D. This is where the forces of good, the rate at which we're doing less work per sub problem is out, out pacing the rate of at which sub problems are proliferating. And so the number of sub-problems goes up, but the savings per sub-problem goes up by even more. So, in this case it means that we're gonna be doing less work. With each recursion tree level, the forces of good outweigh the forces of evil. The second one is true for exactly the same reason. If sub-problems are proliferating so rapidly that it outpaces the savings that we get per sub-problem, then we're gonna see an increasing amount of work. As we go down the recursion tree, it will increase with the level of J. Given that these two are true the third one is false. We can draw conclusions depending on whether the rate of sub-problem proliferation is strictly bigger or strictly less than the rate of work shrinkage. And finally, the fourth statement is also true. This is the perfect equilibrium between the forces of good and the forces of evil. Sub-problems are proliferating, but our savings per sub-problem is increasing at exactly the same rate. The two forces will then cancel out and we'll get exactly the same amount of work done at each level of the recursion tree. This is precisely what happened when we analyzed a merd short algorithm. So let's summarize and conclude with the interpretation. And even understand how this interpretation lends us to forecast some of the running time bounds that we see in the Master Method. Summarizing, the three cases of the master method correspond to the three possible outcomes in the battle between sub-problems proliferating and the work per sub-problem shrinking. One for a tie, one for when sub-problems are proliferating faster, and one for when the work shrinkage is happening faster. In the case where the rates are exactly the same, and they cancel out, then the amount of work should be the same at every level of the recursion tree. And, in this case, we can easily predict what the running time should work out to be. In particular, we know there's a logarithmic number of levels, the amount of work is the same at every level, and we certainly know how much work is getting done at the root, right, because that's just the original recurrence, which tells us that there's, acentotically, n to the d work done at the root. So, with n to the d work for each of the log levels, we expect a running time of n to the d times log n. As we just discussed, when the rate of. Work done per subproblem is shrinking even faster than subproblems proliferate. Then we do less and less work with each level of the recursion tree. So in particular, the biggest amount of work, the worst level is at the root level. Now, the simplest possible thing that might be true would be that actually, the root level just dominates the overall running time of the algorithm, and the other levels really don't matter up to a constant factor. So it's not obvious that's true, but if we keep our fingers crossed and hope for the simplest possible outcome. With the root has the most work, we might expect a running time that's just proportional to the running time of the root. As we just discussed, we already know that that's n to the d, cuz that's just the outermost call to the algorithm. By the same reasoning, when this inequality is flipped, and [inaudible] proliferates so rapidly that it's outpacing the same as we get for sub problem, the amount of work is increasing the recursion level. And here, the worst case is gonna be at the leaves. That's where the, that level's gonna have the most work compared to any other level. And again, if you keep your fingers crossed and hope that the simplest possible outcome is actually true, perhaps the leaves just dominate, and. Up to a constant factor, they govern the running time of the algorithm. In this third case, given that we do a constant amount of work for each of the leaves, since those correspond to base cases, here we'd expect a running time in the simplest scenario, proportional to the number of leaves in the recursion tree. So lets summarize what we've learned in this video. We now understand that fundamentally there are three different kinds of recursion trees. Those in which the work done per level is the same in every level. Those in which the work is decreasing with the level in which case the root is the lowest level. And those in which the amount of work is increasing with the level where the leads are the lowest level. Further more it's exactly the ratio between A the rate of sub problem proliferation and B to the D the rate of work shrinkage sub problem That governs which of these three recursion trees we're dealing with. Further more. Intuitively, we've now had predictions about what kind of running time we expect to see in each of the three cases. They're N to the D log in, that we're pretty confident about. There's a hope that, in the second case, where the root is the worst level, that maybe the running time is N to the D. And there's a hope in the third case where the [inaudible] are the worse level, and we do constant time per leaf, per base case, that it's gonna be proportional to the number of leaves. Let's now stand and check this intuition against the formal statement of the master method, which we'll prove more formally in the next video. So in the three cases, we see they match up. At least two out of three with exactly [inaudible] lies. So in the first case, we see the expected end of the D times log in. In the second case, where the root is the worst level indeed, the simplest possible outcome of big O of N to the D is the assertion. Now, the third case that remains a mystery to be explained. Our intuition said this should hopefully be proportional to the number of leaves. And instead, we've got this funny formula of big O of N in the log base B of A. So in the next video, we'll demystify that connection, as well as supply formal proof for these assertions.