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 1 If f n O nlogb a for some constant 0 then T n nlogb a 2 If f n nlogb a logk n with1 k 0 then T n nlogb a logk 1 n 3 If f n nlogb a with 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 1 T n 3T n 2 n2 2 T n 4T n 2 n2 3 T n T n 2 2n 4 T n 2n T n 2 nn 5 T n 16T n 4 n 6 T n 2T n 2 n log n 1 most of the time k 0 1 7 T n 2T n 2 n log n 8 T n 2T n 4 n0 51 9 T n 0 5T n 2 1 n 10 T n 16T n 4 n 11 T n 2T n 2 log n 12 T n 3T n 2 n 13 T n 3T n 3 n 14 T n 4T n 2 cn 15 T n 3T n 4 n log n 16 T n 3T n 3 n 2 17 T n 6T n 3 n2 log n 18 T n 4T n 2 n log n 19 T n 64T n 8 n2 log n 20 T n 7T n 3 n2 21 T n 4T n 2 log n 22 T n T n 2 n 2 cos n 2 Solutions 1 T n 3T n 2 n2 T n n2 Case 3 2 T n 4T n 2 n2 T n n2 log n Case 2 3 T n T n 2 2n 2n Case 3 4 T n 2n T n 2 nn 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 n log n T n n log2 n Case 2 7 T n 2T n 2 n log n Does not apply non polynomial difference between f n and nlogb a 8 T n 2T n 4 n0 51 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 11 T n 2T n 2 log n T n n Case 1 12 T n 3T n 2 n T n nlg 3 Case 1 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 n log n T n n log n Case 3 16 T n 3T n 3 n 2 T n n log n Case 2 17 T n 6T n 3 n2 log n T n n2 log n Case 3 18 T n 4T n 2 n log n T n n2 Case 1 19 T n 64T n 8 n2 log n Does not apply f n is not positive 20 T n 7T n 3 n2 T n n2 Case 3 21 T n 4T n 2 log n T n n2 Case 1 22 T n T n 2 n 2 cos n Does not apply We are in Case 3 but the regularity condition is violated Consider n 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
View Full Document
Unlocking...