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.