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.