0:00

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.

Â