Transcription of Master Theorem: Practice Problems and Solutions
1 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! (n) = 2T(n/2) + (n) = 3T(n/2) + (n) = 3T(n/3) + (n) = 4T(n/2) + (n) = 3T(n/4) + (n) = 3T(n/3) + (n) = 6T(n/3) + (n) = 4T(n/2) + (n) = 64T(n/8) (n) = 7T(n/3) + (n) = 4T(n/2) + (n) =T(n/2) +n(2 cosn) (n) = 3T(n/2) +n2= T(n) = (n2) (Case 3) (n) = 4T(n/2) +n2= T(n) = (n2logn) (Case 2) (n) =T(n/2) + 2n= (2n) (Case 3) (n) = 2nT(n/2) +nn= Does not apply (ais not constant) (n) = 16T(n/4) +n= T(n) = (n2) (Case 1) (n) = 2T(n/2) +nlogn= T(n) =nlog2n(Case 2) (n) = 2T(n/2) +n/logn= Does not apply (non-polynomial difference betweenf(n) andnlogba) (n) = 2T(n/4) + T(n) = ( ) (Case 3) (n) = (n/2) + 1/n= Does not apply (a <1) (n) = 16T(n/4) +n!
2 = T(n) = (n!) (Case 3) (n) = 2T(n/2) + logn= T(n) = ( n) (Case 1) (n) = 3T(n/2) +n= T(n) = (nlg3) (Case 1) (n) = 3T(n/3) + n= T(n) = (n) (Case 1) (n) = 4T(n/2) +cn= T(n) = (n2) (Case 1) (n) = 3T(n/4) +nlogn= T(n) = (nlogn) (Case 3) (n) = 3T(n/3) +n/2 = T(n) = (nlogn) (Case 2) (n) = 6T(n/3) +n2logn= T(n) = (n2logn) (Case 3) (n) = 4T(n/2) +n/logn= T(n) = (n2) (Case 1) (n) = 64T(n/8) n2logn= Does not apply (f(n) is not positive) (n) = 7T(n/3) +n2= T(n) = (n2) (Case 3) (n) = 4T(n/2) + logn= T(n) = (n2) (Case 1) (n) =T(n/2) +n(2 cosn) = Does not apply. We are in Case 3, but the regularity conditionisviolated. (Considern= 2 k, wherekis odd and arbitrarily large. For any such choice ofn, you canshow thatc 3/2, thereby violating the regularity condition.)3
