0:00

In this video, we'll begin the proof of the master method. The master method,

Â you'll recall, is a generic solution to recurrences of the given form, recurrences

Â in which there's a recursive calls, each on a sub-problem of the same size, size n

Â over b, assuming that the original problem had size n. And, plus, there is big O of n

Â to the d work done by the algorithm outside of these a recursive calls. The

Â solution that the master method provides has three cases, depending on how a

Â compares to b to the d. Now. This proof will be the longest one we've seen so far

Â by a significant margin. It'll span this video as well as the next two. So let me

Â say a few words up front about what you might want to focus on. Overall I think

Â the proof is quite conceptual. There's a couple of spots where we're going to have

Â to do some computations. And the computations I think are worth seeing once

Â in your life. I don't know that they're worth really committing to long term

Â memory. What I do think is worth remembering in the long term however, is

Â the conceptual meaning of the three cases of the master method. In particular the

Â proof will follow a recursionary approach just like we used in the running time

Â analysis of the Mertshot algorithm. And it worth remembering what three types of

Â recursion trees the three cases Is that the master method corresponds to. If you

Â can remember that, there will be absolutely no need to memorize any of

Â these three running times, including the third, rather exotic looking one. Rather,

Â you'll be able to reverse engineer those running times just from your conceptual

Â understanding of what the three cases mean and how they correspond to recursion trees

Â of different type. So, one final comment before we embark on the proof. So, as

Â usual, I'm uninterested in formality in its own sake. The reason we use

Â mathematical analysis in this course, is because it provides an explanation of,

Â fundamentally, why things are the way they are. For example, why the master method

Â has three cases, and what those three cases mean. So, I'll be giving you an

Â essentially complete proof of the master method, in the sense that it has all of

Â the key ingredients. I will cut corners on occasion, where I don't think it hinders

Â understanding, where it's easy to fill in the details. So, it won't be 100 percent

Â rigorous, I won't dot every I and cross every t, but. There will be a complete

Â proof, on the conceptual level. That being said, let me begin with a couple of minor

Â assumptions I"m going to make, to make our lives a little easier. So first, we're

Â gonna assume that the recurrence has the following form. So, here, essentially, all

Â I've done is I've taken our previous assumption about the format of a

Â recurrence, and I've written out all of the constants. So, I'm assuming that the

Â base case kicks in when the input size is one, and I'm assuming that the number of

Â operations in the base case is at most c, and that, that constant c is the same one

Â that was hidden in the big O notation of the general case of the recurrence. The

Â constant c here isn't gonna matter in the analysis, it's just all gonna be a wash,

Â but to make, keep everything clear, I'm gonna write out all the constants that

Â were previously hidden in the big O notation. Another assumption I'm going to

Â make. Now goes to our murtured analysis, is that N is a power of B. The general

Â case would be basically the same, just a little more tedious. At the highest level,

Â the proof of the master method should strike you as very natural. Really, all

Â we're going to do is revisit the way that we analyze Merge Short. Recall our

Â recursion tree method worked great, and gave us this [inaudible] log [inaudible],

Â and the running time of Merge Short. So we're just gonna mimic that recursion

Â tree, and see how far we get. So let me remind you what a recursion tree is. At

Â the roots, at level zero, we have the outermost, the initial indication of the

Â recursive algorithm. At level one, we have the first batch of recursive calls. At

Â level two, we have the recursive calls made by that first batch of recursive

Â calls, and so on. All the way down to the leaves of the tree, which correspond to

Â the base cases, where there's no further recursion. Now, you might recall, from the

Â Merge Sort analysis that we identified a pattern that was crucial in analyzing the

Â running time. And that pattern that we had to understand was, at a given [inaudible]

Â J, at a given level J of this recursion tree. First of all, how many distinct

Â subproblems are there at level J? How many different level J [inaudible] are there?

Â And secondly, what is the input size that each of those level J subproblems has to

Â operate on? So think about that a little bit and give your answer in the following

Â quiz. So the correct answer is the second one. At level J at. Of this recursion

Â tree, there are A to, to the J sub-problems and each has an input of size

Â of N over B to the J. So first of all, why are there A to the J sub-problems? Well,

Â when J equals zero at the root, there's just the one problem, the original

Â indication of the recursive algorithm. And then each. Call to the algorithm makes a

Â further calls. For that reason the number of sub problems goes up by a factor of A

Â with each level leading to A to the J sub problems at level J. Similarly, B is

Â exactly the factor by which the input size shrinks once you makea recursive call. So

Â J levels into the recursion. The input size has been shrunk J times by a fctor of

Â B each time. So the input size at level J is N over B to the J. That's also the

Â reason why, if you look at the question statement, we've identified the numbers of

Â levels as being log of base B. Of N. Back in Merge Short, B was two. We [inaudible]

Â on half the array. So the leaves all resided at level log base two of N. In

Â general, if we're dividing by a factor B each time, then it takes a log based B of

Â N times before we get down the base cases of size of one. So the number of levels

Â overall, zero through log base B event. For a total of log based B event plus one

Â levels. Here then is what the recursion tree looks like. At level zero we have the

Â root corresponding to the outer most call. And the input size here is N. The original

Â problem. Children of a node correspond to the recursive calls. Because there are A.

Â Recursive calls by assumption, there are A. Children or A. Branches. Level one is

Â the first batch of precursor calls. Each of which operates on an input of size N

Â over B. That level log base B. Of N. We've cut the input size by a factor of B. This

Â many times, so we're down to one. So that triggers the base case. So now, the plan

Â is to simply mimic our previous analysis of Merge Sort. So let's recall how that

Â worked. What we did is we zoomed in, in a given level. And for a given level J, we

Â counted the total amount of work that was done at level J subproblems, not counting

Â work that was gonna be done later by recursive calls. Then, given a bound on

Â the amount of work at a given level J, we just summed up overall, the levels, to

Â capture all of the work done by all of the, recursive indications of the

Â algorithm. So inspired by our previous success let's zoom in on a given level J.,

Â and see how much work gets done, with level J. Sub problems. We're going to

Â compute this in exactly the way we did in merge sort. And we were just going to look

Â at the number of problems that are at level J and we're going to multiply that

Â by a bound on the work done per sub-problem. We just identified the number

Â of level J sub-problems as A to the J. To understand the amount of work done for

Â each level j sub-problem, let's do it in two parts. So, first of all, let's focus

Â on the size of the input for each level j sub-problem. That's what we just

Â identified in the previous quiz question. Since the input size is being decreased by

Â a factor b each time, the size of each level j sub-problem is n over b to the j.

Â [inaudible] Now we only care about the size of a level J sub problem in as much

Â it determines the amount of work the number of operations that we perform per

Â level J sub problem. And to understand the relationship between those two quantities

Â we just return to the re currents. The recurrent says how much work gets done in

Â the specific sub problem well there's a bunch of work done by recursive calls the

Â A recursive calls and we're not counting that we're just counting the work done

Â here at A level J and the recurrence also tells us how much is done outside of the

Â recurrent calls. Namely it's no more than the constant C times the input size.

Â Raised to the d power. So here the input size is N over B to the J, so that gets

Â multiplied by the constant C. And it gets raised to the D power. Okay. So C. Times

Â quanity N. Over B. To the J. That's the emphasized. Raised to the D. Power. Next,

Â I wanna simplify this expression a little bit. And I wanna separate out the terms

Â which depend on the level number J, and the terms which are independent of the

Â level number J. So if you look at it A and B are both functions of J, where the C and

Â end of the D terms are independent of J. So let's just separate those out. And you

Â will notice that we have now our grand entrance of the ratio between A and B to

Â the D. And foreshadowing a little, recall that the three cases of the master method

Â are governed by the relationship between A and B to the D. And this is the first time

Â in the analysis where we get a clue that the relative magnitude of those two

Â quantities might be important. So now that we've zoomed in on a particular label J

Â and done the necessary computation to figure out how much work is done just at

Â that level, let's sum over all of the levels so that we capture all of the work

Â done by the algorithms. So this is just gonna be the sum of the epression we saw

Â on the previous slide. Now since C into the D doesn't depend on J, I can yank that

Â out in front of the sum, and I'll sum the expression over all J. That results in the

Â following. So believe it or not, we have now reached an important milestone in the

Â proof of the master method. Specifically, the somewhat messy looking formula here,

Â which I'll put a green box around, is going to be crucial. And the rest of the

Â proof will be devoted to interpreting and understanding this expression, and

Â understanding how it leads to the three different running time bounds in the three

Â different cases. Now I realize that at the moment this expression's star probably

Â just looks like alphabet soup, probably just looks like a bunch of mathematical

Â gibberish. But actually interpreted correctly this has a very natural

Â interpretation. So we'll discuss that in the next video.

Â