In this series of videos, we'll study the master method, which is a general
mathematical tool for analyzing the running time of divide-and-conquer
algorithms. We'll begin, in this video, motivating the method, then we'll give its
formal description. That'll be followed by a video working through six examples.
Finally, we'll conclude with three videos that discuss proof of the master method,
with a particular emphasis on the conceptual interpretation of the master
method's three cases. So, lemme say at the outset that this lecture's a little bit
more mathematical than the previous two, but it's certainly not just math for
math's sake. We'll be rewarded for our work with this powerful tool, the master
method, which has a lot of. The power it will give us good advice on which divide
and conquer algorithms are likely to run quickly and which ones are likely to run
less quickly, indeed it's sort of a general truism that. Novel algorithmic
ideas often require mathematical analyis to properly evaluate. This lecture will be
one example of that truism. As a motivating example, consider the
computational problem of multiplying two n-digit numbers. Recall from our first set
of lectures that we all learned the iterative grade school multiplication
algorithm, and that, that requires a number of basic operations, additions and
multiplications between single digits, which grows quadratically with the number
of digits n. On the other hand, we also discussed an interesting recursive
approach using the divide and conquer paradigm. So recall divide and conquer
necessitates identifying smaller subproblems. So for integer
multiplication, we need to identify smaller numbers that we wanna multiply. So
we proceeded in the obvious way, breaking each of the two numbers into its left half
of the digits, and its right half of the digits. For convenience, I'm assuming that
the number of digits N is even, but it really doesn't matter. Having decomposed X
and Y in this way, we can now expand the product and see what we get. So let's put
a box around this expression, and call it star. So we began with the sort of obvious
recursive algorithm, where we just evaluate the expression star in the
straightforward way. That is, star contains four products involving N over
two digit numbers. A, C, A, D, V, C, and B, D. So we make four recursive calls to
compute them, and then we complete the evaluation in the natural way. Namely, we
append zeros as necessary, and add up these three terms to get the final result.
The way wereason about the running time of recursive algorithms like this one is
using what's called a recurrence. So to intrduce a recurrence let me first make
some notation. T of N. This is going to be the quantity that we really care about,
the quantity that we want to upward boun. Namely this will be the worse case number
of operations that this recursive algorithm requires to multiply two end
digit numbers. A recurrence, then, is simply a way to express T of N in terms of
T of smaller numbers. That is, the running time of an algorithm in terms of the work
done by its recursive calls. So every recurrence has two ingredients. First of
all, it has a base case describing the running time when there's no further
recursion. And in this integer multiplication algorithm, like in most
divide and conquer algorithms, the base case is easy. Once you get down to a small
input, in this case, two one digit numbers, then the running time in just
constant. All you do is multiply the two digits and return the result. So I'm gonna
express that by just declaring the T of one, the time needed to multiply one digit
numbers, is bounded above by a constant. I'm not gonna bother to specify what this
constant is. You can think of it as one or two if you like. It's not gonna matter for
what's to follow. The second ingredient in a recurrence is the important one and it's
what happens in the general case, when you're not in the base case and you make
recursive calls. And all you do is write down the running time in terms of two
pieces. First of all, the work done by the recursive calls and second of all, the
work that's done right here, now. Work done outside of the recursive calls. So on
the left hand side of this general case we just write T of N and then we want
upper bound on T of N in terms of the work done in recursive goals and the work done
outside of recursive goals. And I hope it's self evident what the recurrence
should be in this recursive algorithm for integer multiplication, as we discussed
there's exactly four recursive calls and each is invoked on a pair of N over two
digit numbers so that gives four times the time needed to multiply ten over two digit
numbers. So what do we do outside of the recursive call well we've had the
recursive calls with a bunch of zero's and we add them up. And I'll leave it to you
to verify that grade school addition, in fact runs in time linear in the number of
digits. So putting it all together the amount of work we do outside of the
recursive calls is linear. That is it's big O. Of N. Let's move on to the second,
more clever, recursive algorithm for integer multiplication which dates back to
Gas. Gauss's insight was to realize that, in the expression, star, that we're trying
to evaluate, there's really only three fundamental quantities that we care about,
the coefficients for each of the three terms in the expression. So, this leads us
to hope that, perhaps, we can compute these three quantities using only three
recursive calls, rather than four. And, indeed, we can. So what we do is we
recursively compute A times C, like before, and B times D like before. But
then we compute the product of A plus B with C plus D. And the very cute fact. Is
if we number these three products one two and three that's the final quantity that
we care about the coefficients of the ten to the N over two term namely AD plus BC.
Is nothing more than the third product minus each of the first two. So that's the
new algorithm, what's the new occurrence? The base case obviously is exactly the
same as before. So the question then is, how does the general case change, and,
I'll let you answer this in the following quiz. So the correct response for this
quiz is the second one. Namely, the only thing that changes with respect to the
first recurrence, is that the number of recursive calls drops from four down to
three. A coupla quick comments. So, first of all, I'm being a little bit sloppy when
I say there's three recursive calls, each on digits, each on numbers with n over two
digits. When you take the sums a plus b and c plus d, those might well have n over
two plus one digits. Amongst friends, let's ignore that, let's just call it n
over two digits and each did recursive calls. As usual, the extra plus one is not
gonna matter in the final analysis. Secondly, I'm ignoring exactly. What the
constant factor is in the linear work done outside of the recursive calls. Indeed,
it's a little bit bigger in Gaus's algorithm than it is in the naive
algorithm with four recursive calls. But it's only a constant factor and that's
gonna be supressed in the big O notation. So let's look at this occurance and
compare it to two other recurrences, one bigger, one smaller. So first of all, as
we noted, it differs from the previous recurrence of the naive recursive
algorithm in having one fewer recursive calls. So we have no idea what the running
time is of either of these two recursive algorithms but we should be confident that
this one's. Certainly can only be better, that's for sure. Another point of contrast
is Merge Short. So think about what the recurrence would look like for the Merge
Short algorithm. It would be almost identical to this one, except instead of a
three, we'd have a two, right? Merge Short makes two recursive calls, each on an
array of half the size. And outside of the recursive calls, it does linear work,
mainly for the merged subroutine. We know the running time of Merge Short. It's N
log n. So this algorithm, Gaus's algorithm is gonna be worse, but we don't
know by how much. So while we have a couple clues about what the running time
of this algorithm might be more or less than, honestly, we have no idea what the
running time of Gaus's recursive algorithm for integer multiplication
really is. It is not obvious, we currently have no intuition for it. We don't know
what the solution to this recurrence is. But it will be one super special case of
the general master method, which we'll tackle next.