Master theorem solving

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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