Master Theorem:Practice Problems and SolutionsMaster TheoremThe Master Theorem applies to recurrences of the following form:T (n) = aT (n/b) + f (n)where a ≥ 1 and b > 1 ar e constants and f(n) is an asymptotically positive function.There are 3 cases:1. If f(n) = O(nlogba−) for some constant > 0, then T (n) = Θ(nlogba).2. If f(n) = Θ(nlogbalogkn) with1k ≥ 0, then T (n) = Θ(nlogbalogk+1n).3. If f(n) = Ω(nlogba+) with > 0 , and f(n) satisfies the regularity condition, then T (n) = Θ(f(n)).Regularity condition: af(n/b) ≤ cf(n) for some constant c < 1 and all sufficiently large n.Practice ProblemsFor each of the following recurrences, give an expression for the runtime T (n) if the recurrence can besolved with the Master Theorem. Otherwise, indicate that the Master Theorem does not apply.1. T (n) = 3T (n/2) + n22. T (n) = 4T (n/2) + n23. T (n) = T (n/2) + 2n4. T (n) = 2nT (n/2) + nn5. T (n) = 1 6T (n/4) + n6. T (n) = 2T (n/2) + n log n1most of the time, k = 017. T (n) = 2T (n/2) + n/ log n8. T (n) = 2T (n/4) + n0.519. T (n) = 0.5T (n/2) + 1/n10. T (n) = 16T (n/4) + n!11. T (n) =√2T (n/2) + log n12. T (n) = 3T (n/2) + n13. T (n) = 3T (n/3) +√n14. T (n) = 4T (n/2) + cn15. T (n) = 3T (n/4) + n lo g n16. T (n) = 3T (n/3) + n/217. T (n) = 6T (n/3) + n2log n18. T (n) = 4T (n/2) + n/ log n19. T (n) = 64T (n/8) − n2log n20. T (n) = 7T (n/3) + n221. T (n) = 4T (n/2) + log n22. T (n) = T (n/2) + n(2 − cos n)2Solutions1. T (n) = 3T (n/2) + n2=⇒ T (n) = Θ(n2) (Case 3)2. T (n) = 4T (n/2) + n2=⇒ T (n) = Θ(n2log n) (Case 2)3. T (n) = T (n/2) + 2n=⇒ Θ(2n) (Case 3)4. T (n) = 2nT (n/2) + nn=⇒ Doe s not apply (a is not constant)5. T (n) = 1 6T (n/4) + n =⇒ T (n) = Θ(n2) (Case 1)6. T (n) = 2T (n/2) + n log n =⇒ T (n) = n log2n (Case 2)7. T (n) = 2T (n/2) + n/ log n =⇒ Does no t apply (non-polynomial difference between f(n) and nlogba)8. T (n) = 2T (n/4) + n0.51=⇒ T (n) = Θ(n0.51) (Case 3)9. T (n) = 0.5T (n/2) + 1/n =⇒ Does not apply (a < 1)10. T (n) = 16T (n/4) + n! =⇒ T (n) = Θ (n!) (Case 3)11. T (n) =√2T (n/2) + log n =⇒ T (n) = Θ(√n) (Case 1)12. T (n) = 3T (n/2) + n =⇒ T (n) = Θ(nlg 3) (Case 1)13. T (n) = 3T (n/3) +√n =⇒ T (n) = Θ(n) (Case 1)14. T (n) = 4T (n/2) + cn =⇒ T (n) = Θ(n2) (Case 1)15. T (n) = 3T (n/4) + n lo g n =⇒ T (n) = Θ(n log n) (Case 3)16. T (n) = 3T (n/3) + n/2 =⇒ T (n) = Θ(n log n) (Ca se 2)17. T (n) = 6T (n/3) + n2log n =⇒ T (n) = Θ(n2log n) (Case 3)18. T (n) = 4T (n/2) + n/ log n =⇒ T (n) = Θ(n2) (Case 1)19. T (n) = 64T (n/8) − n2log n =⇒ Does not apply (f(n) is not po sitive)20. T (n) = 7T (n/3) + n2=⇒ T (n) = Θ(n2) (Case 3)21. T (n) = 4T (n/2) + log n =⇒ T (n) = Θ(n2) (Case 1)22. T (n) = T (n/2) + n(2 − cos n) =⇒ Does not apply. We are in Case 3, but the regularity condition isviolated. (Consider n = 2πk, where k is odd and arbitrarily large. For any such choice of n, you canshow that c ≥ 3/2, thereby violating the reg ularity
View Full Document
Unlocking...