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.