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.