Master TheoremOutlineMotivation: Asymptotic Behavior of Recursive AlgorithmsSlide 4Master TheoremMaster Theorem: PitfallsMaster Theorem: Example 1Master Theorem: Example 2Master Theorem: Example 3Slide 10‘Fourth’ Condition‘Fourth’ Condition: ExampleSummaryMaster TheoremSection 7.3 of RosenSpring 2010CSCE 235 Introduction to Discrete StructuresCourse web-page: cse.unl.edu/~cse235Questions: [email protected] TheoremCSCE 235,Spring 20102Outline•Motivation•The Master Theorem–Pitfalls–3 examples•4th Condition–1 exampleMaster TheoremCSCE 235,Spring 20103Motivation: 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 theoremMaster TheoremCSCE 235,Spring 20104Outline•Motivation•The Master Theorem–Pitfalls–3 examples•4th Condition–1 exampleMaster TheoremCSCE 235,Spring 20105Master Theorem•Let T(n) be a monotonically increasing function that satisfies T(n) = a T(n/b) + f(n) T(1) = cwhere a 1, b 2, c>0. If f(n) is (nd) where d 0 thenif a < bdT(n) = If a = bdif a > bdMaster TheoremCSCE 235,Spring 20106Master 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?Master TheoremCSCE 235,Spring 20107Master Theorem: Example 1•Let T(n) = T(n/2) + ½ n2 + n. What are the parameters? a = b = d =Therefore, which condition applies? 1221 < 22, case 1 applies•We conclude thatT(n) (nd) = (n2)Master TheoremCSCE 235,Spring 20108Master Theorem: Example 2•Let T(n)= 2 T(n/4) + n + 42. What are the parameters? a = b = d =Therefore, which condition applies? 241/22 = 41/2, case 2 applies•We conclude thatMaster TheoremCSCE 235,Spring 20109Master Theorem: Example 3•Let T(n)= 3 T(n/2) + 3/4n + 1. What are the parameters? a = b = d =Therefore, which condition applies? 3213 > 21, case 3 applies•We conclude that•Note that log231.584…, can we say that T(n) (n1.584)No, because log231.5849… and n1.584 (n1.5849)Master TheoremCSCE 235,Spring 201010Outline•Motivation•The Master Theorem–Pitfalls–3 examples•4th Condition–1 exampleMaster TheoremCSCE 235,Spring 201011‘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 k0 then•This final condition is fairly limited and we present it merely for sake of completeness.. Relax Master TheoremCSCE 235,Spring 201012‘Fourth’ Condition: Example•Say we have the following recurrence relationT(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 thatMaster TheoremCSCE 235,Spring 201013Summary•Motivation•The Master Theorem–Pitfalls–3 examples•4th Condition–1
View Full Document