# Master theorem solving

I'm starting to study the master theorem, why does something like

$$T(n) = aT(n/b)+f(n)$$

solves to

$$f(n)^{\log_ba}$$ ?

I'm a bit confused on the resolution

-
What is confusing you exactly? A proof of this fact can be found in the book Introduction to Algorithms. – Daniel Pietrobon Aug 17 '12 at 12:13
It is important when asking a question to actually ask a question. Can you give us an example of what is confusing you? – Thomas Andrews Aug 17 '12 at 12:44
I don't know where the second formula came from, @DanielPietrobon is that explained where the second formula come from in the book you cited? – John Smith Aug 17 '12 at 12:59
Again, "where the second formula came from" is not a clear question. Are you looking for the history of the formula, a proof of why the formula works, or some other question? – Thomas Andrews Aug 17 '12 at 13:16
Is this what you're looking for? Or is there something in particular that is hanging you up? – mixedmath Aug 17 '12 at 18:30

The right way to think about this is that we reduce the original problem, of size $n$, to $a$ separate problems of size $n/b$, and we do this recursively. At stage $i$, there are $a^i$ problems of size $n b^{-i}$. For each such problem, we need to do something which costs $f(x)$ on a problem of size $x$. Hence, the total cost at level $i$ is $a^i f(n b^{-i})$.

This recursion has $\log_b n$ levels, so the total work consumed at all levels is $$\sum_{i=0}^{\log_b n} a^i f(n b^{-i})$$

Depending on the growth of $f$, this is basically a geometric series.

-

For an in depth explanation and proof of the "Master Theorem" or "Master Method" of finding asymptotic solutions to recurrences, see MIT OCW's Introduction to Algorithms, Lecture 2.

-

Master Theorem In the last section, we saw three different kinds of behavior for recurrences of the form T(n) = _ aT(n/2) + n if n > 1 d if n = 1. These behaviors depended upon whether a < 2, a = 2, and a > 2. Remember that a was the number of subproblems into which our problem was divided. Dividing by 2 cut our problem size in half each time, and the n term said that after we completed our recursive work, we had n additional units of work to do for a problem of size n. There is no reason that the amount of additional work required by each subproblem needs to be the size of the subproblem. In many applications it will be something else, and so in Theorem 5.1 we consider a more general case. Similarly, the sizes of the subproblems don’t have to be 1/2 the size of the parent problem. We then get the following theorem, our first version of a theorem called the Master Theorem. (Later on we will develop some stronger forms of this theorem.) Theorem 5.1 Let a be an integer greater than or equal to 1 and b be a real number greater than 1. Let c be a positive real number and d a nonnegative real number. Given a recurrence of the form T(n) = _ aT(n/b) + nc if n > 1 d if n = 1 then for n a power of b, 1. if logba < c, T(n) = Θ(nc), 2. if logb a = c, T(n) = Θ(nc log n), 3. if logba > c, T(n) = Θ(nlogb a). Proof: In this proof, we will set d = 1, so that the bottom level of the tree is equally well computed by the recursive step as by the base case. It is straightforward to extend the proof for the case when d _= 1. Let’s think about the recursion tree for this recurrence. There will be logb n levels. At each level, the number of subproblems will be multiplied by a, and so the number of subproblems at level i will be ai. Each subproblem at level i is a problem of size (n/bi). A subproblem of size n/bi requires (n/bi)c additional work and since there are ai problems on level i, the total number of units of work on level i is ai(n/bi)c = nc _ ai bci _ = nc _ a bc _i . Recall from above that the different cases for c = 1 were when the work per level was decreasing, constant, or increasing. The same analysis applies here. From our formula for work on level i, we see that the work per level is decreasing, constant, or increasing exactly when ( a bc )i 5.2. THE MASTER THEOREM 171 is decreasing, constant, or increasing. These three cases depend on whether ( a bc) is 1, less than 1, or greater than 1. Now observe that ( a bc) = 1 ⇔ a = bc ⇔ logb a = c logb b ⇔ logb a = c Thus we see where our three cases come from. Now we proceed to show the bound on T(n) in the different cases. In the following paragraphs, we will use the facts (whose proof is a straightforward application of the definition of 1ogartihms and rules of exponents) that for any x, y and z, each greater than 1, xlogy z = zlogy x and that logx y = Θ(log2 y). (See Problem 3 at the end of this section and Problem 4 at the end of the previous section.) In general, we have that the total work done is lo_gb n i=0 nc _ a bc _i = nc lo_gb n i=0 _ a bc _i In case 1, (part 1 in the statement of the theorem) this is nc times a geometric series with a ratio of less than 1. Theorem 4.4 tells us that nc lo_gb n i=0 _ a bc _i = Θ(nc). Exercise 5.2-1 Prove Case 2 of the Master Theorem. Exercise 5.2-2 Prove Case 3 of the Master Theorem. In Case 2 we have that a bc = 1 and so nc lo_gb n i=0 _ a bc _i = nc lo_gb n i=0 1i = nc(1 + logb n) = Θ(nc log n) . In Case 3, we have that a bc > 1. So in the series lo_gb n i=0 nc _ a bc _i = nc lo_gb n i=0 _ a bc _i , the largest term is the last one, so by Theorem 4.4,the sum is Θ _ nc _ a bc logb n

. But nc _ a bc _logb n = nc alogb n (bc)logb n = nc nlogb a nlogb bc = nc nlogb a nc = nlogb a. Thus the solution is Θ(nlogb a). We note that we may assume that a is a real number with a > 1 and give a somewhat similar proof (replacing the recursion tree with an iteration of the recurrence), but we do not give the details here.

                           By:ISRAFIL CSE

-