2. Consider the recurrence T(n) = 2T(n/2) + f(n) in which f(n) = { n3 if...

 

Transcribed Image Text:

2. Consider the recurrence T(n) = 2T(n/2) + f(n) in which f(n) = { n3 if [log(n)] is even n² otherwise (a) Prove that T(n) = O(n³) by induction. logb (b) Show that f(n) = N(n¹º86(a)+€) for some € > 0 and use master theo- rem to solve this recurrence. 2. Consider the recurrence T(n) = 2T(n/2) + f(n) in which f(n) = { n3 if [log(n)] is even n² otherwise (a) Prove that T(n) = O(n³) by induction. logb (b) Show that f(n) = N(n¹º86(a)+€) for some € > 0 and use master theo- rem to solve this recurrence.