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. 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 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. 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. 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. 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. 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). 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. 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 + b with c + d. 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. So that's the new algorithm, what's the new recurrence? 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 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. 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.
