0:00

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 let me 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 predictive power.

Â It'll give us good advice about 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 analysis to properly evaluate.

Â This lecture will be one example of that truism.

Â 0:52

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.

Â 1:12

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 sub-problems.

Â So for integer multiplication,

Â we need to identify smaller numbers that we want to multiply.

Â So we proceed 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.

Â 1:44

So let's put a box around this expression and call it *.

Â So we begin with the sort of obvious recursive algorithm where we just

Â evaluate the expression * in the straightforward way.

Â That is, * contains four products involving n over two digit numbers,

Â ac, ad, bc, and bd.

Â So we make four recursive calls to compute them.

Â And then we complete the evaluation in the natural way.

Â Namely, we append 0s as necessary, and

Â add up these three terms to get the final result.

Â 2:12

The way we reason about the running time of recursive algorithms like this one

Â is using what's called a recurrence.

Â So to introduce a recurrence, let me first make some notation T(n).

Â This is going to be the quantity that we really care about.

Â The quantity that we want to upper bound.

Â Namely this will be the worst case number of operations

Â that this recursive algorithm requires to multiply two n-digit numbers.

Â This is exactly what we want to upper bound.

Â A recurrence, then,

Â is simply a way to express T(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 is just constant.

Â All you do is multiply the two digits and return the result.

Â 3:08

So I'm going to express that by just declaring the T(1),

Â the time needed to multiply one digit numbers, as bounded above by a constant.

Â I'm not going to bother to specify what this constant is.

Â You can think of it as one or two if you like.

Â It's not going to 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.

Â 3:40

So on the left hand side of this general case, we just write T(n).

Â And then we want an upper bound on T(n) in terms of the work done by recursive calls

Â and the work done outside of recursive calls.

Â And I hope it's self evident what the recurrence should be in this

Â recursive algorithm for integer multiplication.

Â As we discussed, there are exactly four recursive calls.

Â And each is invoked on a pair of n/2 digit numbers.

Â So that gives us 4 times the time needed to multiply n/2 digit numbers.

Â So what do we do outside of the recursive call?

Â Well, we pad the results of the recursive calls with a bunch of zeros 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 O(n).

Â 4:27

Let's move on to the second, more clever, recursive algorithm for

Â integer multiplication, which dates back to Gauss.

Â Gauss's insight was to realize in the expression * 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.

Â 5:06

And the very cute fact is if we number these three products, one, two, and three.

Â That the final quantity that we care about,

Â the coefficient of the 10 to the n/2 term, namely ad + bc.

Â Is nothing more than the third product minus each of the first two.

Â 5:57

A couple of quick comments.

Â So first of all, I'm being a little bit sloppy when

Â I say there's three recursive calls, each on numbers with n/2 digits.

Â When you take the sums a + b and c + d, those might well have n/2 plus 1 digits.

Â Amongst friends, let's ignore that.

Â Let's just call it n/2 digits in each of the recursive calls.

Â As usual, the extra plus one is not going to 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 Gauss's algorithm than it is in the naive

Â algorithm with four recursive calls.

Â But it's only by a constant factor.

Â And that's going to be suppressed in the big O notation.

Â Let's look at this recurrence and compare it to two other reccurrences, 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 call.

Â So, we have no idea what the running time is on either of these

Â two recursive algorithms.

Â But we should confident that this one certainly can only be better.

Â That's for sure.

Â Another point of contrast is merge sort.

Â So think about what the recurrence would look like for the merge sort algorithm.

Â It would be almost identical to this one except instead of a three we'd have a two.

Â Right? Merge sort makes two recursive calls,

Â each on an array of half the size.

Â And outside of the recursive calls it does linear work, namely for

Â the merge sub-routine.

Â We know the running time of merge sort.

Â It's n log n.

Â So this algorithm, Gauss's algorithm, is going to be worse, but

Â we don't know by how much.

Â 7:25

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 Gauss'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.

Â