0:00

Let's complete the proof of the master method. Let me remind you about the story

Â so far, the first thing we did is we analyzed the work done by a recursive

Â algorithm using a recursion tree. So we zoomed in on a given level J, we

Â identified the total amount of work done at level J and then we summed up over all

Â of the levels resulting in this rather intimidating expression star. C into the D

Â times a sum over the levels J from zero to log base B of N of quantity A over B to

Â the B raised to the J. Having derived this expression star we then spent some time

Â interpreting it, attaching to it some semantics Sticks. And we realize that the

Â roll of this ratio A to the B over D, is to distinguish between three fundamentally

Â different types of recursion trees. Those in which A = B to the D and the amount of

Â work is the same at every level. Those in which A is less than B to the D and

Â therefore the amount of work is going down with the level. And those where A is

Â bigger than B to the D in which case the amount of work is growing with the level.

Â This gave us intuition about the three cases of the master method and even gave

Â us predictions f or the running times we might see. So what remains to do is turn

Â this hopeful intuition into. A rigorous proof. So we need to verify that in fact

Â the simplest possible scenarios outlined in the previous video. Actually occur. In

Â addition, we need to demystify the third case and understand what the expression

Â has to do with the number of leaves of the recursion tree. Let's begin with the

Â simplest case, which is case one. We're calling case one, we're assuming that A

Â equals B to the D. This is the case where we have a perfect equilibrium between the

Â forces of good and evil. Where the rate of the sub problem proliferation exactly

Â cancels out with a rate at which we do less work per sub problem. And now,

Â examining the expression, star, we can see how easy our lives get when A equals B to

Â the D. In that case, this ratio is equal to one. So naturally this ratio raised to

Â the J is also equal to one for all J. And then of course this sum evaluates to

Â something very simple. Namely one summed with itself log base B of N plus one

Â times. So the sum simply equals log base B of N. Plus one, and that's going to get

Â multiplied by. This CN to the D term which is independent of the sum. So summarizing,

Â when A equals B to the D, we find that star equals CN to the D times log base B

Â of N plus one. Writing this in big o notation, we would write big o of end of a

Â d login. And again, I'm going to suppress the base of the logarithms. Since all

Â logarithms differ only by a constant factor we don't have to specify the base.

Â That's just suppressed by the constant hidden in the big O notation. So that's it

Â for case one. Like I said, this is the easy case. So what do we do when A is not

Â equal to B to the D? And remember A could be either less than or bigger than B to

Â the D. To answer that question, let's take a short detour into geometric series. For

Â this single slide detour we're going to think about a single constant number R.

Â Now, what you want to think about is R. Representing that ratio A. Over B. To the

Â D. From the previous slot. But for this slide only let's just call it R. This is a

Â constant. It's bigger than zero, and it's not equal to one. Now, suppose we sum up

Â powers of R stopping, let's say, at the Kth power of R. I claim that this sum has

Â a nice closed form formula. Specifically it is exactly, R. To the K. Plus one,

Â minus one. Divided by or a minus one. Now, whenever you see a general formula like

Â this, it's useful to keep in mind a couple of canonical values of the parameters that

Â you can plug in to develop intuition. And for this expression, you might wanna think

Â canonically about the cases, R=2, and R=1/2. So when R=2, or something that

Â powers a two. One+2+4+8+16, and so on. One hour's a half, [inaudible] have one, plus

Â a half, plus a quarter, plus an eighth, and so on. Now I'm not gonna prove this

Â for you, I'd like you to prove this yourself. If you don't already know this

Â fact. So the way to prove this is simply by induction. And I will leave this an, an

Â exercise. What I wanna focus on instead is what this fact can do for us. The way that

Â we use this fact is to formalize the idea that, that in recursion trees where the

Â amount of work is increasing in the levels, the leaves dominate the overall

Â running time. And where recursion trees, where the amount of work is decreasing in

Â the level, the root dominates the running time. In the sense that we can ignore all

Â of the other levels of the recursion tree. So, and in the vision in this slide, we

Â have two upshots. First of all, for the case when R is less than one. And in this

Â case, this expression on the right-hand side. R to the Q plus one minus one over R

Â minus one can be upper bounded by one over one minus R. So again, remember, you might

Â want to have a canonical value of r in mind here, namely, one half. So what we're

Â claiming here is that the right hand side is nor more than two for the case of

Â R=1/2. And that's easy to see if you think about one plus one-half plus a one-fourth

Â plus one-eighth and so on. That sum is converging to, to as k grows large.

Â So in general, for our less than one constant, the sum is divided by one minus

Â one over R. Now, we're not actually gonna care about this formula, one minus one

Â over R. The point for us is just that this is a constant. And by constant, I mean

Â independent of K, independent of how many terms we sum up. Obviously, it depends on

Â R of the ratio, but it does not depend on how many things we sum up on K. So the way

Â to think about this is, when we sum up a bunch of terms where R is less than one,

Â then the very first term dominates. The first term is with a one. And no matter

Â how many terms we sum up, we never get, grow bigger than the sum constant. A

Â similar situation holds for the case where r is a constant bigger than one. When r is

Â bigger than one. A tiny bit of algebra shows that we can upper bound the right

Â hand side by r to the k. Times something which is constant, independent of K. So

Â again, let's interpret the second upshot in terms of a canonical value of R.

Â Namely, R equals two. Then our sum is one plus two plus four plus eight plus

Â sixteen, and so on. And what this is saying is that no matter how many terms we

Â sum up, the overall sum is never gonna be more than twice. The largest and final

Â term. So if we sum up to say 128, the sum, you'll notice, will be 255, which is, at

Â most, twice that largest term, 128. And that saying is true for any K. The entire

Â sum is no more than twice that of the largest term. In this sense, the largest

Â term in the series dominates the whole thing. So to summarize this slide in just

Â into one sentence we sum up powers of a constant R when R is bigger than one the

Â largest power of that constant dominate to the sun when R is smaller than one then

Â the sun is just a constant. Let's now apply this to prove case two of the master

Â method. In case two of the master method, we assume that A is less than B to the D.

Â That is, the rate at which sub problems are proliferating is drowned out by the

Â rate at which we do less work per sub problem. So this is the case where the

Â amount of work is decreasing with each level of the recursion tree. And our

Â intuition said that, well, in the simplest possible scenario, we might hope that all

Â of the work, up to a constant factor, is being done at the root. So let's make that

Â intuition precise by using the basic Sums fact on the previous slide.

Â So, since A is less than B to the D. This ration is less than one. So let's call

Â this ratio equal to R. So R, you'll notice, does depend on the three

Â parameters, A, B and D. But R is a constant, it does not depend on N. So what

Â is this sum? The sum is just, we're just summing up powers of this constant R,

Â where R is less than one. What did we just learn? We just learned that any such sum

Â is bounded above by a constant, independent of the number of terms that

Â you sum up. So therefore, what is this expression star evaluates to. It evaluates

Â to C, which is a constant, times N to the D. Times another constant. So suppressing

Â the product of these two constants in Big O notation we can say that the expression

Â starts upper bounded by Big O(n to the d). And this makes precise our intuition that

Â indeed the overall running time of the algorithm, in this type of recursion tree

Â with decreasing work per level, is dominated by the root. The overall amount

Â of work is only a constant factor larger than the work done and merely at level

Â zero of the tree. Let's move on to the final and most challenging part of the

Â proof, the final case. In case three we assume that A is bigger than B to the D.

Â So in conceptual terms, we're assuming the rate at which sub problems proliferate is

Â exceeding the rate at which we do less work per sub problem. So these are

Â recursion trees where the amount of work is increasing with each level, with the

Â most work being done at the leaves. And once again, using the basic sums fact, we

Â can make precise the hope that, in fact, we only have to worry about the leaves. We

Â can throw away the rest of work, losing only a constant factor. So to see that,

Â you will again denote this ratio between A and B to the D as R. And in this case R is

Â bigger that one. So this sum is a sum of a bunch of powers of R were R is bigger than

Â one, what did we just learn about that two slides ago in the basic sums facts, we

Â learned that such sums are dominated by the largest and last term of the sum. Okay

Â so the bounded it by a constant factor times the largest term. Therefore, we can

Â we can simplify the expression star to the following. I'm

Â gonna write it in terms of big O notation. And, like, on the last slide, I'll use it

Â to suppress two different constants. On the one hand, I'm gonna be suppressing the

Â constant C, which we inherited way back when from the original recurrence. And on

Â the other hand, I'm gonna use it to also suppress this constant that comes from the

Â basic sums fact. So ignoring those two constants, what do we have left? We have N

Â to the D. Times the largest term of the sum. So what is the largest term of the

Â sum? Well, it's the last one so we plug in the biggest value of J that we're ever

Â going to see. So what's the biggest value of J that we're ever going to see? We'll

Â it's just this. Log base B of N. So, we get the ratio A over B to the D, raised to

Â the log base B of N. Power. Now don't despair how messy this looks. We can do

Â some remarkable simplifications. So what I want to do next is I want to focus just on

Â this one over B to the D, raised to the log base B of N term. So that's going to

Â be. You can write that as B to the minus D log base B of N. Which if I factor this

Â exponent into two successive parts I can write this as B Raise to the log base B of

Â N power. And only then raised to the minus D. And now of course what happens is that

Â taking the logarithm of N base B, followed by taking, raising it to the B power,

Â those are inverse operations that cancel, so that leaves us just with the N. So this

Â results in a end to the minus D. And now remarkably this end to the minus D is just

Â gonna cancel out with this end to the D. Leaving us with merely. A, raise the log

Â based B event. And thus, out of this crazy sea of letters, rises a formula we can

Â actually understand. So A to the log based B of N, if we step back and pick for a

Â minute, is actually a supernatural quantity. Describe something about the

Â recursion trees that we already knew was supposed to pop up in the analysis. I'll

Â let, I'll let you think through exactly what that is in the following quiz. So the

Â correct answer to this quiz is the fourth response. A raised to the logarithm event

Â is precisely the number of leaves of the recursion tree. And remember in our

Â intuition for case three, recursion trees where the amount of work is increasing per

Â level, we thought that perhaps the work would be dominated by the work done at the

Â leaves which is as proportional as the number of leaves. So why is this the

Â answer? Well just remember what recursion trees look like at level zero. We have a

Â single node, and then with each level we have eight times as many nodes as before.

Â That is, with each level of the recursion tree, the number of nodes goes up by a

Â factor of A. How far does this, how long does this process go on? Well, it goes on

Â until we reach down the, the leaves. Recall that in the input size starts at N

Â up at the root. It gets divided by a factor of B each time, and it terminates

Â once we get down to one. So the leaves preside at precisely level log base B of

Â N. So therefore. The number of leaves is just a branching factor which is A raised

Â to the number of times that we actually multiply by A which is just the number of

Â levels which is log base b n. So each time we go down a level we

Â increase the number of nodes by a factor of A and we go down a level log base B of

Â N times. Leaving us with a number of leaves equal to A raised to the log base B

Â of N. So what we've done is we've mathematically confirmed, in a very cool

Â way, our intuition about what case three should look like in the master method.

Â We've proven that in case three when A is. Bigger than b to the d. The running time

Â is, o of the number of leaves in the recursion tree, just as the intuition

Â predicted. But, this leaves us with one final mystery. If you go back to the

Â statement of the master method, we didn't say, a to the log base b of n. In case

Â three, it says the running time is, n to the log base b of a. And, not only that,

Â we've used this case three formula over and over again, to evaluate Gauss's

Â recursive algorithm for integer multiplication, to evaluate the Strassen's

Â matrix multiplication algorithm, and so on. So, what's the story? How come we're

Â not getting the same thing, as in the statement of the master method? Well

Â there's a very simple explanation, which is simply that, believe it or not. A log

Â base B of N, and N to the log base B of A. Are exactly the same thing. This looks

Â like the kind of mistake you'd make in freshmen algebra. But actually, if you

Â think about it, these are simply the same quantity. If you don't believe me, just

Â take the logarithm base B of both sides, and it'll give the same thing in both

Â sides. Now, you might well be wondering why I didn't just state in the master

Â method that the running time of case three is this very sensible and meaningful

Â expression, a raised log based b of n, i.e., the number of leaves in the

Â recursion tree. Well, it turns out that while this expression on the left hand

Â side is the more meaningful conceptually. The right hand side. N. To the log base B.

Â Of A. Is the easiest one to apply. So recall when we worked through a bunch of

Â examples, of the master method, this right hand side was super convenient, when we

Â evaluated the running times of out rhythms. When we plugged in the numbers of

Â A. And B. In any case, whether or not you want to think about the running time in

Â case three as proportional to the number of leaves in the tree or as proportional

Â at the end of the log base B of A, we're done. We've proved it. That's case three.

Â That was the last one. So we're done with the master method. Qed. So that was a lot

Â of hard work for doing the master method and I would never expect someone to be

Â able to regurgitate all of the details of this proof you know it's something like a

Â cocktail party well maybe except the nerdiest of all cocktail parties but I do

Â think there's a few high level conceptual points of this proof that are worth

Â remembering in the long term, so we started by just writing down a recursion

Â tree for the recursive algorithm and in a generic way. And going level by level, we

Â counted up the work done by the algorithm. And this part of the proof had nothing to

Â with how A and B related to each other. Then we recognized that there

Â are three fundamentally different types of recursion trees. Those with the same

Â amount of work per level, those where it increases with the level, and those where

Â it decreases with the level. If you can remember that, you can even remember what

Â the running times of the three cases should be. In the case where you do the

Â same amount of every work at each level. We know there's a logarithmic number of

Â levels. We know we do end in D work at the root. So that gives us the running time in

Â case one had ended the day you log in. When the amount of work is decreasing with

Â the levels, we now know that the route dominates. Up to a constant, we can throw

Â out the rest of the levels, and we know end of the D work gets done at the root,

Â so that's the overall running time. And in the third case, where it's increasing in

Â the levels, the leaves dominate. The number of leaves is A raised to the log

Â based of B of N, and that's the same as N, the log based B of A. And that's

Â proportional to running time in case three of the master method.

Â