Master Theorem Section 7 3 of Rosen Spring 2010 CSCE 235 Introduction to Discrete Structures Course web page cse unl edu cse235 Questions cse235 cse unl edu Outline Motivation The Master Theorem Pitfalls 3 examples 4th Condition 1 example CSCE 235 Spring 2010 Master Theorem 2 Motivation Asymptotic Behavior of Recursive Algorithms When analyzing algorithms recall that we only care about the asymptotic behavior Recursive algorithms are no different Rather than solving exactly the recurrence relation associated with the cost of an algorithm it is sufficient to give an asymptotic characterization The main tool for doing this is the master theorem CSCE 235 Spring 2010 Master Theorem 3 Outline Motivation The Master Theorem Pitfalls 3 examples 4th Condition 1 example CSCE 235 Spring 2010 Master Theorem 4 Master Theorem Let T n be a monotonically increasing function that satisfies T n a T n b f n T 1 c where a 1 b 2 c 0 If f n is nd where d 0 then if a bd T n If a bd if a bd CSCE 235 Spring 2010 Master Theorem 5 Master Theorem Pitfalls You cannot use the Master Theorem if T n is not monotone e g T n sin x f n is not a polynomial e g T n 2T n 2 2n b cannot be expressed as a constant e g Note that the Master Theorem does not solve the recurrence equation Does the base case remain a concern CSCE 235 Spring 2010 Master Theorem 6 Master Theorem Example 1 Let T n T n 2 n2 n What are the parameters a 1 b 2 d 2 Therefore which condition applies 1 22 case 1 applies We conclude that T n nd n2 CSCE 235 Spring 2010 Master Theorem 7 Master Theorem Example 2 Let T n 2 T n 4 n 42 What are the parameters a 2 b 4 d 1 2 Therefore which condition applies 2 41 2 case 2 applies We conclude that CSCE 235 Spring 2010 Master Theorem 8 Master Theorem Example 3 Let T n 3 T n 2 3 4n 1 What are the parameters a 3 b 2 d 1 Therefore which condition applies 3 21 case 3 applies We conclude that Note that log23 1 584 can we say that T n n1 584 No because log23 1 5849 and n1 584 n1 5849 CSCE 235 Spring 2010 Master Theorem 9 Outline Motivation The Master Theorem Pitfalls 3 examples 4th Condition 1 example CSCE 235 Spring 2010 Master Theorem 10 Fourth Condition Recall that we cannot use the Master Theorem if f n the non recursive cost is not a polynomial There is a limited 4th condition of the Master Theorem that allows us to consider polylogarithmic functions Corollary If for some k 0 then This final condition is fairly limited and we present it merely for sake of completeness Relax CSCE 235 Spring 2010 Master Theorem 11 Fourth Condition Example Say we have the following recurrence relation T n 2 T n 2 n log n Clearly a 2 b 2 but f n is not a polynomial However we have f n n log n k 1 Therefore by the 4th condition of the Master Theorem we can say that CSCE 235 Spring 2010 Master Theorem 12 Summary Motivation The Master Theorem Pitfalls 3 examples 4th Condition 1 example CSCE 235 Spring 2010 Master Theorem 13
View Full Document
Unlocking...