So having motivated and hyped up the, the
generality of the master method, and it's
used for analyzing recursive algorithms.
Let's move on to it's precise mathematical
statement. Now the master method is, in
some sense, exactly what you want. It's
what I'm gonna call a black box for
solving recurrences. Basically, it takes,
as input, a recurrence in a particular
format, and it spits out as output, a
solution to that recurrence. An upper
[inaudible] the running time of your
recursive algorithm. That is, you just
plug in a few parameters of your recursive
algorithm, and boom, out pops its running
time. Now, the master method does require
a few assumptions, and let me be explicit
about one. Right now. Namely, the master
method, at least the one I'm gonna give
you, is only gonna be relevant for
problems in which all of the subproblems
have exactly the same size. So, for
example, in Merge Sort, there are two
recursive calls, and each is on exactly
one-half of the array. So Merge Sort
satisfies this assumption both so problems
have equal size. Similarly, in both of our
integer multiplication algorithms, all
subproblems were on integers with N over
two digits with half as many digits. So
those will also obey this assumption. If,
for some reason, you had a recursive
algorithm that recursed on the third of
the array, and then on the other
two-thirds of the array. The master method
that I'm gonna give you will not apply to
it. There are generalizations of the
master method that I'm going to show you,
which can accomodate unbalanced subproblem
sizes, but those are outside the scope of
this course. This will be sufficient for
almost all of the examples we're going to
see. One notable exception, for those of
you that watch the optional video on the
deterministic algorithm for liner time
selection. That will be one algorithm
which has two recursive calls on different
subproblem sizes. So to analyze that
recurrence, we'll have to use a different
method, not the master method. Next I'm
going to describe the format of the
recurrences to which the master method
applies. As I said, there are more general
versions of the master method which apply
to even more recurrences, but the one I'm
going to give you is going to be
reasonably simple and it will cover pretty
much all the cases you're likely ever to
encounter. So recurrences have two
ingredients. There's the relatively
unimportant, but, still necessary base
case step. And we're gonna make the
obvious assumption, which is just
satisfied by every example we're ever
going to see in this course. Which is
that, at some point, once the input size
drops two a sufficiently small amount,
then the [inaudible], then the recursion
stops, and the problem is solved, sub
problem is solved in constant [inaudible].
Since this assumption is pretty much
always satisfied in every problem we're
going to see, I'm not gonna discuss it
much further. Let's move on to the general
case, where there are recursive calls. So
we assume there were recurrences given in
the following format. The running time on
an input of link N is bounded above by
some number of recursive calls. Let's call
it A different recursive calls. And then
each of these sub-problems has exactly the
same size and it's, one over B fraction of
the original input size. So there's A
recursive calls, each of on input of size
N over B. Now as usual there's the case
where I never be as a fraction and not an
integer and as usual I'm going to be
sloppy and ignore it and as usual that
sloppiness has no implications for the
final conclusion, everything that we're
going to discuss is true, for the same
reasons and the general case where N over
B is not an integer, outside the recursive
calls we do some extra work and lets say
that it's O of N to the D for some
parameter D so in addition to the input
size N there are three letters here which
we need to be very clear of what their
meaning is. So first of all there's A,
which is the number of subproblems, the
number of recursive calls. So A could be
as small as one or it might be some larger
integer. Then there's B. B is the factor
by which the input size shrinks before a
recursive call is applied. B is some
constant strictly greater than one. So for
example if you re-curse oh half of the
original problem then B would be equal to
two. It better be strictly bigger than one
so that eventually you stop recursion. So
that eventually that you terminate.
Finally, there's D, which is simply the
exponent in the running time of the quote
unquote combined step. That is, the amount
of work which is done outside of the
recursive calls. And D could be as small
as zero, which would indicate constant
amount of work outside of the recursive
calls. One point to emphasize is that A, B
and D are all constants. That's all,
they're all numbers that are independent
of N. So A, B and D are gonna be numbers
like one, two, three or four. They do not
depend on the input size and. And in fact,
let me just redraw the D so that you don't
confuse it with the A. So again, A is the
number of recursive calls. And D is the
exponent in the running time governing the
work done outside of the recursive calls.
Now, one comment about that final turn,
that Big O of N to the D. On the one hand,
I'm being sorta sloppy. I'm not keeping
track of the constant that's hidden inside
the Big O [inaudible]. I'll be explicit
with that constant when we actually prove
the master method, but it's really not
gonna matter. It's just gonna carry
through the analysis, without affecting
anything. So you can go ahead and ignore
that constant within the Big O. Obviously.
The constant of the exponent, namely D. Is
very important. Alright? So depending on
when D. Is depends on whether that amount
of time is constant, linear, quadratic, or
so on. So certainly we care about the
constant [inaudible]. D. So that's the
input to the master method. It is a
recurrence of this form, so you can think
of it as a recursive algorithm which makes
A recursive calls, each on some problems
of equal size, each of size N over B, plus
it does N to the D work outside of the
recursive calls. So having setup the
notation I can now precisely state the
master method for you. So given such a
occurrence we are going to get an upper
ban on the running time. So the running
time on. Inputs of size N is going to be
upper bounded by one of three things. So
somewhat famously the master method has
three cases. So let me tell you about each
of them. The trigger, which determines
which case you're in, is a comparison
between two numbers. First of all A.
Recall A is the number of recursive calls
made and B raised to the D power. Recall B
is the factor by which the input size
shrinks before you re-curse. D is the
exponent in the amount of work done
outside the recursive call. So we're gonna
have one case for when they're equal,
we're gonna have one case for when A is
strictly smaller then B to the D And third
case is when A. Is strictly bigger than B.
To the D. And in the first case we get a
running time of, big O. Of N. To the D.
Times log in. Again this is D. The same D
that was in the final term of the
recurrence. Okay? That worked on the
outside of the recursive calls. So the
first case, the running time is the, is
the same as the running time in the
recurrence and outside the recursive calls
but we pick up an extra log in factor. In
second case where A is smaller than B to
the D. The running time is merely Big O of
N to the D. And this case might be
somewhat stunning if this could ever
occur. Because, of course, in recurrence,
what do you do? You do some recursion,
plus you do N to the D work outside of the
recursion. So in the second case, it
actually says the work is dominated by
just what's done outside the recursion in
the outermost call. The third case will
initially seem the most mysterious, when A
is strictly bigger than B to the D. We're
gonna get a running time of Big O, of N to
the log. Base B. Of a. For again recall A
is the number of recursive cause and B is
the factor by which the input size shrinks
before you recurse. So that's the master
method with its three cases. Let me give
this to you in a cleaner slide to make
sure there's no ambiguity in my
handwriting. So here's the exact same
statement, the master method. Once again,
with it's three cases depending on how A
compares to B to the D. So one final
comment. You'll notice that I'm being
asymmetrically sloppy with the two
logarithms that appear in these formulas.
So let me just explain why. In particular
you'll notice that in case one, with a
logarithm. I'm not specifying the base.
Why is that true? Well, it's because the
logrithm with respect to any two different
bases differs by a constant factor. So the
logrithm that is at base E, that is the
natural logrigthm, and the logrithm base
two, for example, differ by only a
constant factor independent of the
argument N. So you can switch this
logrithm to whatever consant base you
like. It only changes the leading constant
factor, which of course is being
suppressed in the bigger notation anyways.
On the other hand, in case three, where we
have a logarithm in the exponents. Once
it's in the exponent, we definitely care
about that constant. Constants is the
difference between, say, linear time and
quadratic time. So we need to keep careful
of the ba-, the logarithm base in the
exponent in case three. [inaudible], and
that base is precisely B, the factor by
which the input shrinks which each
[inaudible], with each recursive call. So
that's the precise statement of the master
method. And the rest of this lecture will
work toward understanding the master
method. So first, in the next video, we'll
look at a number of examples, including
resolving the running time of [inaudible]
recursive algorithm for integer
multiplication. Following those several
examples, we'll prove the master method.
And I know now, these three cases probably
look super mysterious. But if I do my job,
by the end of the analysis.