Transcription of Master Theorem: Practice Problems and Solutions
{{id}} {{{paragraph}}}
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.
7. T(n) = 2T(n/2)+n/logn 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)+logn 12. T(n) = 3T(n/2)+n 13. T(n) = 3T(n/3)+
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document:
{{id}} {{{paragraph}}}