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.