In this video we'll put the master method
to use by instantiating it for six
different examples. But first let's recall
what the master method says. So the master
method takes as input recurrences of a
particular format, in particular
recurrences that are paramerized by three
different constants, A, B and D. A refers
to the number of recursive calls, or the
number of sub-problems that get solved. B
is the factor by which the sub-problem
size is smaller than the original problem
size. And D is the exponent in the running
time of the work done outside of the
recursive calls. So the recurrence has the
form T of N. The running time [inaudible]
put up [inaudible], N is no more than A,
the number of subproblems, times the time
required to solve each subproblem, which
is T of N over B. Cuz the input size of a
subproblem is a number B + O of N to the
D. The work outside of the recursive
calls. There's also a base case, which I
haven't written down. So once the problem
size [inaudible], drops below a particular
constant, then there should be no more
recursion, and you can just solve the
problem immediately, that is in constant
time. No, given a recurrence in this
permitted format, the running time is
given. By one of three formulas. Depending
on the relationship between A. The number
of [inaudible] calls. And B raised to the
D power. Case one of the master method is
when these two quantities are the same, A
equals B to the D. Then the running time
is N to the D log N. No more than that. In
case two, the number of recursive calls,
a, is strictly smaller than b to the d.
Then, we get a better running time
upper-bound, of o of n to the d, and, when
a is bigger than b to the d, we get this
somewhat funky-looking running time of o
of n, raised to the log base b of a power.
We'll understand what that, where that
formula comes from a little later. So,
that's the master method. It's a little
hard to interpret the first time you see
it, so let's look at some concrete
examples. Let's begin with an out rhythm
that we already know the answer to, that
we already know the running time. Namely
let's look at merge short. So again what's
so great about the master method is all we
have to do is identify the values of the
three relevent parameters A, B, and D, and
we're done. We just plug them in then we
get the answer. So A remember is the numbr
of recursive calls. So in merge sort
recall we get two recursive calls. B is
the factor by which the sub problem size
is smaller than that in the original. Well
we recurse on half the array so the sub
problem size if half that of the original.
So B is equal to two. And recall that
outside of the recursive calls all merge
sort does is merge. And that's a linear
time subroutine. So exponent D is one
reflection of factor with linear time. So
remember the key trigger which determines
which of the three cases is the
relationship between A and B and the D. So
A obviously is two. And B to the D is also
equal to two. So this puts us in case one.
And remember in case one. Now that the
running time is bounded above by O of N to
the D log N. In our case D equals one, so
this is just O of N log N. Which of
course, we already knew. Okay? But at
least this is a sanity check, the master
method is at least reconfirming facts
which we've already proven by direct
means. So let's look at a second example.
The second example is going to be for the
binary search [inaudible] in a sorted
array. Now we haven't talked explicitly
about binary search, and I'm not planning
to, so if you don't know what binary
search is please read about it in a
textbook or just look it up on the web and
it'll be easy to find descriptions. But
the upshot is, this is basically how you'd
look up a phone number in a phone book.
Now I realize probably the youngest
viewers of this video haven't actually had
the experience of using a physical
telephone book but for the rest of you. As
you know, you don't actually start with
the A's, and then go to the B's, and then
go to the C's, if you're looking for a
given name. You more sensibly split the
telephone book in the middle. [inaudible].
Then you recurse on the left or the right
half, as appropriate, depending on if the
element you're looking for is bigger or
less than the middle element. Now the
master method applies equally well to
binary search and it tells us what its
running time is. So in the next quiz,
you'll go through that exercise. So the
correct answer is the first one. To see
why let's recall what A, B and D mean. A
is the number of recursive calls now in
binary search you only make one recursive
call this is unlike merge sort, remember
you just compare the element you're
looking for to the middle element, if it's
less than the middle element you recourse
on the left half if it's bigger than the
middle element you recourse on the right
half. So in any case there's only one
recursive call so A is merely one in
binary search. Now in any case you recurs
on half the array so [inaudible] B = two
you recurs on a value of half the size,
and outside of the recursive call the only
thing you do is one comparison you just
determine whether the element you're
looking for is bigger than or less than
the middle element. Of the array that you
were first on. So that's constant time
outside of the recursive call, giving us a
value for D. Of zero. Just like merge
short this is again case one of the master
method, because we have A. Equal, B. To
the D. Both in this case are equal to one.
So this gives us a recurrence, a solution
to our occurrence of big O of N to the D
log N. Since D=zero, this is simply login.
And again, many of you probably already
know that the running time of binary
search is login, or you can figure that
out easily. Again, this is just using the
master method as a sanity check to
reconfirm that it's giving us the answers
that we expect. Let's now move on to some
harder examples, beginning with the first
recursive algorithm for integer
multiplication. Remember, this is where
we. Recurse on four different products of
N over two digit numbers and then
recombine them in the obvious way using
padding by zero and some linear time
conditions. So [inaudible] the first
[inaudible] which does not make use of
[inaudible] but we do the four different
recursive calls [inaudible]. We have a the
number of recursive calls is equal to
four. Now, in each case whenever we take a
product of two smaller numbers, the
numbers have n over two digits, so that's
half as many digits as we started with. So
just like in the previous two examples, b
is going to be equal to two. The input
size drops by a by a fact of two when we
re curse. Now how much work do we do
outside of re curse or calls? Well again,
all it is doing is additions and padding
by zeros and that can be done in linear
time. Linear time corresponds to a
parameter value of d equal to one. So next
we determine which case of the master
method we're in. A equals four. B to the
D=2, which, in this case, is less than A.
So this corresponds to case three of the
master method. And this is where we get
the somewhat strange formula for the
running time of the recurrence. T on N is
big [inaudible] to the log based B of A.
Which, with our parameter values, is N to
the log base two of four, also known as O
of N squared. So let's compare this to the
simple algorithm that we all learned back
in grade school. Recall that the iterative
algorithm for multiplying two integers.
Also take an N squared number of
operations. So, this was a clever idea to,
to attack the problem recursively. But at
least in the absence of [inaudible], where
you just naively compute each of the four,
necessary, products separately. You do not
get any improvement over the [inaudible]
algorithm that you learn in grade school.
Either way, it's an N squared number of
operation. But, what if we do make use of
[inaudible], where we do only three
recursive calls instead of four? Surely,
the running time won't be any worse than N
squared. And hopefully, it's going to be
better. So I'll let you work out the
details on this next quiz. So the correct
answer to this quiz is the fourth option.
It's not hard to see what the relevant
values of A, B, and D are. Remember, the
whole point of [inaudible] trick it to
reduce the number of recursive calls from
four down to three. So the value of A is
going to be three. As usual, we're
recurring on a problem size which is half
of that of the original, in this case, N
over two digit numbers. So B remains two,
and just like in the more naive recursive
algorithm, we only do linear work outside
of the recursive calls. All that's needed
to do some additions and patterns by zero.
So that puts [inaudible] parameter values
A, B, and D. Then we have to figure out
which case. The master method of that is
so we have A equal three. B raised to the
D equal to two. So A has dropped by one
relative to the more naive algorithm. But
we're still in case three of the master
method. A is still bigger than B to the D,
so the running time is still governed by
that rather exotic looking formula.
Namely, T of N is big O of N to the log.
Base B which in our case is two of A which
is now three instead of four okay so the
master method just tells us the solution
to this recurrence, the running time of
this algorithm is big O to the N to the
log base two of three so what is
[inaudible] log base two of three well
plug it in your computer or calculator and
you'll find it's roughly 1.59 so we get a
running time of N to the 1.59. Which is
certainly better than N squared. It's not
as fast as N lo gin, not as fast as the
Merge Sort recurrence, which makes only
two recursive calls. But it's quite a bit
better than quadratic. So, summarizing,
you did, in fact, learn a sub optimal
algorithm for integer multiplication way
back in grade school. You can beat the
[inaudible] algorithm using a combination
of recursion, plus [inaudible] to save on
the number of recursive calls. Let's
quickly move on to our final two examples.
Example #five is for those of you that
watched the video on [inaudible] matrix
multiplication algorithm. So recall the
[inaudible] and properties of [inaudible]
algorithm. The key idea is similar to
[inaudible] multiplication. First you set
up the problem recursively. One observes
that the naive way to solve the problem
recursively would be to eat sub problems.
But if you're clever about saving some
computations, you can get it down to just
seven recursive calls, seven subproblems.
So A in [inaudible] argument is equal to
seven. As usual each sub-problem size is
half that of the original one so P is
going to be equals two and the amount of
work done outside of the recursive calls
is linear in the matrix size so quadratic
in N quadratic in the mention because
there's a quadratic number of entries in
terms of the dimension so N squared work
outside the recursive calls equal to the
value of D equal to two. So as far as
which case of the master method we're in
it's the same as the last examples, A =
seven, D = four. Which is less than a, so
once again we're in case three. And now
the running time of Strassen's algorithm.
T of N is viggo of N to the log base two
seven, which is more or less N to the
2.81. And again this is a win. Once we
use, the, the savings to get down to just
seven [inaudible] calls. This beats the
naive [inaudible] algorithm which recall,
would require a cubic ton. So that's
another win for clever divide and conquer.
And [inaudible] multiplication via
[inaudible] algorithm. And once again, the
master's method, just by plugging in
parameters, it tells us exactly what the
right answer to this recurrence is. So for
the final example, I feel a little guilty,
because I've shown you five examples, and
none of'em have triggered case two. We've
had two in case one of the master method,
and three now in case three. So this'll be
sort of a fictitious recurrence, just
[inaudible] case two. But, you know, there
are examples of recurrences that come up,
where case two is the relevant one. So
let's just look at a. At the following
recurrence. So this recurrence is just
like merge sort. We recurse twice. There's
two recursive calls, each on half the
problem size. The only difference is in
this recurrence we're working a little bit
harder on the combine step. Instead of
linear time outside of the recursive
calls, we're doing a quadratic amount of
work, okay? So. A equals two. B equals two
and D equals two, so B to the D was equal
to four, strictly bigger than A And that's
exactly the trigger for case two. Now
[inaudible] with the running time in case
two, it's simply end with a d, where d is
the exponent and the combined step, in our
case d is two, so we get a running time of
n squared. And you might find this a
little bit intuitive by giving the merge
sort, all we do with merge sort is change
the combined step from linear to
quadratic. And merge sort has a running
time of [inaudible] and squared log in,
and that is over estimate. So master
method gives us the tighter [inaudible]
that it's only quadratic work. So, put
differently the running time of the entire
algorithm is governed by the work outside
of the recursive calls just in the outer
most call to algorithm. Just at the root
of the recursion trim.