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.
Motivation - Question 1
Which recurrence best describes the running time of the Gauss' algorithm for integer multiplication?
𝑇(𝑛)≤2𝑇(𝑛/2)+𝑂(𝑛^2)
𝑇(𝑛)≤3𝑇(𝑛/2)+𝑂(𝑛)
𝑇(𝑛)≤4𝑇(𝑛/2)+𝑂(𝑛)
𝑇(𝑛)≤4𝑇(𝑛/2)+𝑂(𝑛^2)
网友评论