0:00

So having motivated and hyped up the generality of the master method and

Â its use for

Â analyzing recursive algorithms, let's move on to its precise mathematical statement.

Â Now, the master method is, in some sense, exactly what you want.

Â It's what I'm going to call a black box for solving recurrences.

Â Basically, it takes an input a recurrence in a particular format and

Â it spits out as output a solution to that recurrence,

Â an upper bound on the running time of your recursive algorithm.

Â 0:24

That is, you just plug in a few parameters of your recursive algorithm, and

Â boom, out pops its running time.

Â Now, the master method does require a few assumptions,

Â and let me be explicit about one of them right now.

Â Namely, the master method, at least the one I'm going to give you,

Â is only going to be relevant for

Â problems in which all of the subproblems have exactly the same size.

Â So for example, in merge sort, there are two recursive calls, and

Â each is on exactly one half of the array.

Â So merge sort satisfies this assumption, both subproblems have equal size.

Â Similarly, in both of our integer multiplication algorithms,

Â all subproblems were on integers with n over 2 digits,

Â with half as many digits, so those will all also obey this assumption.

Â If for some reason you had a recursive algorithm that recursed on

Â a third of the array and then on the other two-thirds of the array,

Â the master method that I'm going to give you will not apply to it.

Â 1:11

There are generalizations of the master method that I'm going to show you

Â which can accommodate unbalanced subproblem sizes, but

Â those are outside the scope of this course.

Â This will be sufficient for almost all of the examples we're going to see.

Â One notable exception, for those of you that watched the optional video on

Â a deterministic algorithm for linear time selection, that will be

Â one algorithm which has two recursive calls on different subproblem sizes.

Â So to analyze that recurrence,

Â we'll have to use a different method, not the master method.

Â 1:55

So recurrences have two ingredients.

Â There's the relatively unimportant, but still necessary, base case step.

Â And we're going to make the obvious assumption, which is just satisfied by

Â every example we're ever going to see in this course, which is that at some point,

Â once the input size drops to a sufficiently small amount,

Â then the recursion stops, and the subproblem is solved in constant time.

Â Since this assumption is pretty much always satisfied in every problem

Â we're going to see, I'm not going to discuss it much further.

Â Let's move on to the general case where there are recursive calls.

Â So we assume the recurrence is given in the following format.

Â The running time on an input of length n is bounded above by some number

Â of recursive calls, let's call it a different recursive calls.

Â And then each of these subproblems has exactly the same size, and

Â it's 1 over b fraction of the original input size.

Â So there's a recursive calls, each on an input of size n over b.

Â Now, as usual, there's the case where n over b is a fraction and not an integer.

Â And as usual, I'm going to be sloppy and ignore it.

Â And as usual, that sloppiness has no implications for the final conclusion.

Â Everything that we're going to discuss is true for

Â the same reasons in the general case where n over b is not an integer.

Â Now, outside the recursive calls, we do some extra work.

Â And let's say that it's O(n to the d) for some parameter d.

Â So in addition to the input size n,

Â there are three letters here which we need to be very clear on what their meaning is.

Â So first of all, there's a, which is the number of subproblems,

Â the number of recursive calls.

Â 3:41

b is some constant strictly greater than 1.

Â So for example,

Â if you recurse on half of the original problem, then b would be equal to 2.

Â It better be strictly bigger than 1 so that eventually you stop recursion, so

Â that eventually then you terminate.

Â Finally, there's d, which is simply the exponent in the running time of the,

Â quote, unquote combine step, that is,

Â the amount of work which is done outside of the recursive calls.

Â And d could be as small as 0,

Â which would indicate constant amount of work outside of the recursive calls.

Â 4:24

And in fact, let me just redraw the d so that you don't confuse it with the a.

Â So again, a is the number of recursive calls and d is the exponent and

Â the running time governing the work done outside of the recursive calls.

Â Now, one comment about that final term, that big O(n to the d).

Â On the one hand, I'm being sort of sloppy.

Â I'm not keeping track of the constant that's hidden inside the big-O notation.

Â I'll be explicit with that constant when we actually prove the master method.

Â But it's really not going to matter.

Â It's just going to carry through the analysis without affecting anything.

Â So you can go ahead and ignore that constant inside the big-O.

Â Obviously, the constant in the exponent, namely d, is very important.

Â So depending on what d is, depends on whether that amount of time is constant,

Â linear, quadratic, or so on.

Â So certainly we care about the constant d.

Â 5:28

So given such a recurrence, we're going to get an upper bound on the running time.

Â So the running time on inputs of size n is going to be upper bounded by

Â one of three things.

Â So somewhat famously, the master method has three cases.

Â So let me tell you about each of them.

Â The trigger,

Â which determines which case you're in, is a comparison between two numbers.

Â First of all, a, recall, a is the number of recursive calls made.

Â And b raised to the d power.

Â Recall, b is the factor by which the input size shrinks before you recurse.

Â d is the exponent in the amount of work done outside of the recursive call.

Â So we're going to have one case for when they're equal,

Â we're going to have one case for when a is strictly smaller than b to the d.

Â And the third case is when a is strictly bigger than b of the d.

Â And in the first case, we got a running time of big O of n to the d times log n.

Â 6:25

And again, this is d, the same d that was in the final term of the recurrence.

Â Okay, the work done outside of the recursive calls.

Â So the first case,

Â the running time is the same as the running time in the recurrence,

Â outside of the recursive calls, but we pick up an extra log n factor.

Â In the second case, where a is smaller than b to the d,

Â the running time is merely big-O of n to the d.

Â And this case might be somewhat stunning that this could ever occur,

Â because of course, in recurrence, what do you do?

Â You do some recursion, plus you do n to the d work outside of the recursion.

Â So in the second case, it actually says that the work is dominated by

Â just what's done outside the recursion in the outermost call.

Â The third case will initially seem the most mysterious.

Â When a is strictly bigger than b to the d,

Â we're going to get a running time of big-O of n to the log base b of a.

Â Where, again, recall, a is the number of recursive calls and

Â b is the factor by which the input size shrinks before you recurse.

Â So that's the master method with its three cases.

Â Let me give this to you in a cleaner slide to make sure there's no

Â ambiguity in my handwriting.

Â So here's the exact same statement, the master method

Â once again with its three cases, depending on how a compares to b to the d.

Â 7:44

So one thing you'll notice about this version of the master method is that it

Â only gives upper bounds.

Â So we only say that the solution to the recurrence is big-O of some function.

Â And that's because if you go back to our recurrence,

Â we used big-O rather than theta in the recurrence.

Â And this is in the spirit of the course, where as algorithm designers,

Â our natural focus is on upper bounds, on guarantees for

Â the worst case running time of an algorithm.

Â And we're not going to focus too much most of the time on proving stronger bounds in

Â terms of theta notation.

Â Now, a good exercise for

Â you, to check if you really understand the proof of the master method after we go

Â through it will be to show that if you strengthen the hypothesis and

Â you assume the recurrence has the form T of n equals a times T of n over b plus

Â theta of n to the d, then in fact, all three of these big-O's in the statement of

Â the master method become thetas and the solution becomes asymptotically exact.

Â So one final comment.

Â You'll notice that I'm being asymmetrically sloppy with the two

Â logarithms that appear in these formulas.

Â So let me just explain why.

Â In particular, you'll notice that in case one, with the logarithm,

Â I'm not specifying the base.

Â Why is that true?

Â Well, it's because the the logarithm, with respect to any two different bases,

Â differs by a constant factor.

Â So the logarithm base e, that is, the natural logarithm, and the logarithm base

Â 2, for example, differ by only a constant factor independent of the argument n.

Â So you can switch this logarithm to whatever constant base you like,

Â it only changes the leading constant factor,

Â which of course is being suppressed in the big-O notation anyways.

Â On the other hand, in case three, where we have a logarithm in the exponent,

Â once it's in the exponent, we definitely care about that constant.

Â Constants is the difference between, say, linear time and quadratic time.

Â So we need to keep careful track of the logarithm base

Â in the exponent in case three, and that base is precisely b,

Â the factor by which the input shrinks with each recursive call.

Â So that's the precise statement of the master method,

Â and the rest of this lecture will work toward understanding the master method.

Â So first, in the next video, we'll look at a number of examples, including resolving

Â the running time of Gauss's recursive algorithm for integer multiplication.

Â Following those several examples, we'll prove the master method.

Â And I know now these three cases probably look super mysterious,

Â but if I do my job, by the end of the analysis,

Â these three cases will seem like the most natural thing in the world, as

Â will these somewhat exotic looking formula for exactly what the running time is.

Â