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)