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.