DOC PREVIEW
UNL CSCE 235 - Master Theorem

This preview shows page 1-2-3-4 out of 13 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 log231.584…, can we say that T(n)   (n1.584)No, because log231.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 k0 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

UNL CSCE 235 - Master Theorem

Documents in this Course
Logic

Logic

77 pages

Proofs

Proofs

82 pages

Induction

Induction

85 pages

Proofs

Proofs

52 pages

Sets

Sets

8 pages

Recursion

Recursion

16 pages

Proofs

Proofs

82 pages

Functions

Functions

71 pages

Recursion

Recursion

50 pages

Functions

Functions

54 pages

Graphs

Graphs

56 pages

Induction

Induction

32 pages

Relations

Relations

60 pages

Graphs

Graphs

10 pages

Recursion

Recursion

80 pages

Recursion

Recursion

81 pages

Functions

Functions

16 pages

Recursion

Recursion

16 pages

Sets

Sets

52 pages

Relations

Relations

60 pages

Load more
Download Master Theorem
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Master Theorem and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Master Theorem 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?