Transcription of Master Theorem: Practice Problems and Solutions
{{id}} {{{paragraph}}}
Example: air traffic controller
Master Theorem: Practice Problems and Solutions
Master Theorem: Practice Problems and SolutionsMaster TheoremThe Master Theorem applies to recurrences of the following form:T(n) =aT(n/b) +f(n)wherea 1 andb >1 are constants andf(n) is an asymptotically positive are 3 cases:1. Iff(n) =O(nlogba ) for some constant >0, thenT(n) = (nlogba).2. Iff(n) = (nlogbalogkn) with1k 0, thenT(n) = (nlogbalogk+1n).3. Iff(n) = (nlogba+ ) with >0, andf(n) satisfies the regularity condition, thenT(n) = (f(n)).Regularity condition:af(n/b) cf(n) for some constantc <1 and all sufficiently ProblemsFor each of the following recurrences, give an expression for the runtimeT(n) if the recurrence can besolved with the Master Theorem. Otherwise, indicate that the Master Theorem does not (n) = 3T(n/2) + (n) = 4T(n/2) + (n) =T(n/2) + (n) = 2nT(n/2) + (n) = 16T(n/4) + (n) = 2T(n/2) +nlogn1most of the time,k= (n) = 2T(n/2) + (n) = 2T(n/4) + (n) = (n/2) + 1 (n) = 16T(n/4) +n!
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).
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: