Teorema Maestro

Master Theorem:

Practice Problems and Solutions

Master Theorem

The Master Theorem applies to recurrences of the following form:

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

where a 1 and b> 1 are constants and f(n)is an asymptotically positive function.

There are 3 cases:

logb

a- )logb

a).

1. If f(n)= O(nfor some constant > 0, then T(n)= (n

2. If f(n)= (nlogb

a logk n)with1 k 0, then T(n)= (nlogb

a logk+1 n).

logb

a+ )

3. If f(n)=

(nwith > 0, and f(n)satisfies the regularity condition, then T(n)= (f(n)).

Regularity condition: af(n/b) cf(n)for some constant c< 1 and all sufficiently large n.

Practice Problems

For each of the following recurrences, give an expression for the runtime T(n) if the recurrence can be

solved with the Master Theorem. Otherwise, indicate that the Master Theorem does not apply.

2

1. T(n)=3T(n/2)+n

2

2. T(n)=4T(n/2)+n

3. T(n)= T(n/2)+2n

n

4. T(n)=2nT(n/2)+n

5. T(n)=16T(n/4)+n

6. T(n)=2T(n/2)+nlogn

1most of the time, k =0

1

7. T(n)=2T(n/2)+n/ logn

0.51

8. T(n)=2T(n/4)+n

9. T(n)=0.5T(n/2)+1/n

10. T(n)=16T(n/4)+n!

p

11. T(n)=2T(n/2)+logn

12. T(n)=3T(n/2)+n

p

13. T(n)=3T(n/3)+ n

14. T(n)=4T(n/2)+cn

15. T(n)=3T(n/4)+nlogn

16. T(n)=3T(n/3)+n/2

17. T(n)=6T(n/3)+n2 logn

18. T(n)=4T(n/2)+n/ logn

19. T(n)=64T(n/8)-n2 logn

2

20. T(n)=7T(n/3)+n

21. T(n)=4T(n/2)+logn

22. T(n)= T(n/2)+n(2-cosn)

Solutions

2

1. T(n)=3T(n/2)+n=) T(n)= (n2)(Case 3)

2

2. T(n)=4T(n/2)+n=) T(n)= (n2 logn)(Case 2)

3. T(n)= T(n/2)+2n =) (2n)(Case 3)

n

4. T(n)=2nT(n/2)+n=) Does not apply(a is not constant)

5. T(n)=16T(n/4)+n =) T(n)= (n2)(Case 1)

6. T(n)=2T(n/2)+nlogn =) T(n)= nlog2 n (Case 2)

logb

a)

7. T(n)=2T(n/2)+n/ logn =) Does not apply(non-polynomialdifferencebetween f(n)and n

0.51

8. T(n)=2T(n/4)+n=) T(n)= (n0.51)(Case 3)

9. T(n)=0.5T(n/2)+1/n=) Does not apply(a< 1)

10. T(n)=16T(n/4)+n!=) T(n)= (n!)(Case 3)

pp

11. T(n)=2T(n/2)+logn =) T(n)= ( n)(Case 1)

lg

12. T(n)=3T(n/2)+n =) T(n)= (n3)(Case 1)

p

13. T(n)=3T(n/3)+ n =) T(n)= (n)(Case 1)

14. T(n)=4T(n/2)+cn =) T(n)= (n2)(Case 1)

15. T(n)=3T(n/4)+nlogn =) T(n)= (nlogn)(Case 3)

16. T(n)=3T(n/3)+n/2=) T(n)= (nlogn)(Case 2)

17. T(n)=6T(n/3)+n2 logn =) T(n)= (n2 logn)(Case 3)

18. T(n)=4T(n/2)+n/ logn =) T(n)= (n2)(Case 1)

19. T(n)=64T(n/8)-n2 logn =) Does not apply(f(n)is not positive)

2

20. T(n)=7T(n/3)+n=) T(n)= (n2)(Case 3)

21. T(n)=4T(n/2)+logn =) T(n)= (n2)(Case 1)

22. T(n)= T(n/2)+n(2- cosn)=) Does not apply. We are in Case 3, but the regularity condition is

violated. (Considern =2 k, where k is odd and arbitrarily large. For any such choice of n, you can

show that c 3/2, thereby violating the regularity condition.)

3

...