In this video, we'll begin the proof of
the master method. The master method,
you'll recall, is a generic solution to
recurrences of the given form, recurrences
in which there's a recursive calls, each
on a sub-problem of the same size, size n
over b, assuming that the original problem
had size n. And, plus, there is big O of n
to the d work done by the algorithm
outside of these a recursive calls. The
solution that the master method provides
has three cases, depending on how a
compares to b to the d. Now. This proof
will be the longest one we've seen so far
by a significant margin. It'll span this
video as well as the next two. So let me
say a few words up front about what you
might want to focus on. Overall I think
the proof is quite conceptual. There's a
couple of spots where we're going to have
to do some computations. And the
computations I think are worth seeing once
in your life. I don't know that they're
worth really committing to long term
memory. What I do think is worth
remembering in the long term however, is
the conceptual meaning of the three cases
of the master method. In particular the
proof will follow a recursionary approach
just like we used in the running time
analysis of the Mertshot algorithm. And it
worth remembering what three types of
recursion trees the three cases Is that
the master method corresponds to. If you
can remember that, there will be
absolutely no need to memorize any of
these three running times, including the
third, rather exotic looking one. Rather,
you'll be able to reverse engineer those
running times just from your conceptual
understanding of what the three cases mean
and how they correspond to recursion trees
of different type. So, one final comment
before we embark on the proof. So, as
usual, I'm uninterested in formality in
its own sake. The reason we use
mathematical analysis in this course, is
because it provides an explanation of,
fundamentally, why things are the way they
are. For example, why the master method
has three cases, and what those three
cases mean. So, I'll be giving you an
essentially complete proof of the master
method, in the sense that it has all of
the key ingredients. I will cut corners on
occasion, where I don't think it hinders
understanding, where it's easy to fill in
the details. So, it won't be 100 percent
rigorous, I won't dot every I and cross
every t, but. There will be a complete
proof, on the conceptual level. That being
said, let me begin with a couple of minor
assumptions I"m going to make, to make our
lives a little easier. So first, we're
gonna assume that the recurrence has the
following form. So, here, essentially, all
I've done is I've taken our previous
assumption about the format of a
recurrence, and I've written out all of
the constants. So, I'm assuming that the
base case kicks in when the input size is
one, and I'm assuming that the number of
operations in the base case is at most c,
and that, that constant c is the same one
that was hidden in the big O notation of
the general case of the recurrence. The
constant c here isn't gonna matter in the
analysis, it's just all gonna be a wash,
but to make, keep everything clear, I'm
gonna write out all the constants that
were previously hidden in the big O
notation. Another assumption I'm going to
make. Now goes to our murtured analysis,
is that N is a power of B. The general
case would be basically the same, just a
little more tedious. At the highest level,
the proof of the master method should
strike you as very natural. Really, all
we're going to do is revisit the way that
we analyze Merge Short. Recall our
recursion tree method worked great, and
gave us this [inaudible] log [inaudible],
and the running time of Merge Short. So
we're just gonna mimic that recursion
tree, and see how far we get. So let me
remind you what a recursion tree is. At
the roots, at level zero, we have the
outermost, the initial indication of the
recursive algorithm. At level one, we have
the first batch of recursive calls. At
level two, we have the recursive calls
made by that first batch of recursive
calls, and so on. All the way down to the
leaves of the tree, which correspond to
the base cases, where there's no further
recursion. Now, you might recall, from the
Merge Sort analysis that we identified a
pattern that was crucial in analyzing the
running time. And that pattern that we had
to understand was, at a given [inaudible]
J, at a given level J of this recursion
tree. First of all, how many distinct
subproblems are there at level J? How many
different level J [inaudible] are there?
And secondly, what is the input size that
each of those level J subproblems has to
operate on? So think about that a little
bit and give your answer in the following
quiz. So the correct answer is the second
one. At level J at. Of this recursion
tree, there are A to, to the J
sub-problems and each has an input of size
of N over B to the J. So first of all, why
are there A to the J sub-problems? Well,
when J equals zero at the root, there's
just the one problem, the original
indication of the recursive algorithm. And
then each. Call to the algorithm makes a
further calls. For that reason the number
of sub problems goes up by a factor of A
with each level leading to A to the J sub
problems at level J. Similarly, B is
exactly the factor by which the input size
shrinks once you makea recursive call. So
J levels into the recursion. The input
size has been shrunk J times by a fctor of
B each time. So the input size at level J
is N over B to the J. That's also the
reason why, if you look at the question
statement, we've identified the numbers of
levels as being log of base B. Of N. Back
in Merge Short, B was two. We [inaudible]
on half the array. So the leaves all
resided at level log base two of N. In
general, if we're dividing by a factor B
each time, then it takes a log based B of
N times before we get down the base cases
of size of one. So the number of levels
overall, zero through log base B event.
For a total of log based B event plus one
levels. Here then is what the recursion
tree looks like. At level zero we have the
root corresponding to the outer most call.
And the input size here is N. The original
problem. Children of a node correspond to
the recursive calls. Because there are A.
Recursive calls by assumption, there are
A. Children or A. Branches. Level one is
the first batch of precursor calls. Each
of which operates on an input of size N
over B. That level log base B. Of N. We've
cut the input size by a factor of B. This
many times, so we're down to one. So that
triggers the base case. So now, the plan
is to simply mimic our previous analysis
of Merge Sort. So let's recall how that
worked. What we did is we zoomed in, in a
given level. And for a given level J, we
counted the total amount of work that was
done at level J subproblems, not counting
work that was gonna be done later by
recursive calls. Then, given a bound on
the amount of work at a given level J, we
just summed up overall, the levels, to
capture all of the work done by all of
the, recursive indications of the
algorithm. So inspired by our previous
success let's zoom in on a given level J.,
and see how much work gets done, with
level J. Sub problems. We're going to
compute this in exactly the way we did in
merge sort. And we were just going to look
at the number of problems that are at
level J and we're going to multiply that
by a bound on the work done per
sub-problem. We just identified the number
of level J sub-problems as A to the J. To
understand the amount of work done for
each level j sub-problem, let's do it in
two parts. So, first of all, let's focus
on the size of the input for each level j
sub-problem. That's what we just
identified in the previous quiz question.
Since the input size is being decreased by
a factor b each time, the size of each
level j sub-problem is n over b to the j.
[inaudible] Now we only care about the
size of a level J sub problem in as much
it determines the amount of work the
number of operations that we perform per
level J sub problem. And to understand the
relationship between those two quantities
we just return to the re currents. The
recurrent says how much work gets done in
the specific sub problem well there's a
bunch of work done by recursive calls the
A recursive calls and we're not counting
that we're just counting the work done
here at A level J and the recurrence also
tells us how much is done outside of the
recurrent calls. Namely it's no more than
the constant C times the input size.
Raised to the d power. So here the input
size is N over B to the J, so that gets
multiplied by the constant C. And it gets
raised to the D power. Okay. So C. Times
quanity N. Over B. To the J. That's the
emphasized. Raised to the D. Power. Next,
I wanna simplify this expression a little
bit. And I wanna separate out the terms
which depend on the level number J, and
the terms which are independent of the
level number J. So if you look at it A and
B are both functions of J, where the C and
end of the D terms are independent of J.
So let's just separate those out. And you
will notice that we have now our grand
entrance of the ratio between A and B to
the D. And foreshadowing a little, recall
that the three cases of the master method
are governed by the relationship between A
and B to the D. And this is the first time
in the analysis where we get a clue that
the relative magnitude of those two
quantities might be important. So now that
we've zoomed in on a particular label J
and done the necessary computation to
figure out how much work is done just at
that level, let's sum over all of the
levels so that we capture all of the work
done by the algorithms. So this is just
gonna be the sum of the epression we saw
on the previous slide. Now since C into
the D doesn't depend on J, I can yank that
out in front of the sum, and I'll sum the
expression over all J. That results in the
following. So believe it or not, we have
now reached an important milestone in the
proof of the master method. Specifically,
the somewhat messy looking formula here,
which I'll put a green box around, is
going to be crucial. And the rest of the
proof will be devoted to interpreting and
understanding this expression, and
understanding how it leads to the three
different running time bounds in the three
different cases. Now I realize that at the
moment this expression's star probably
just looks like alphabet soup, probably
just looks like a bunch of mathematical
gibberish. But actually interpreted
correctly this has a very natural
interpretation. So we'll discuss that in
the next video.