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(n86(a)+) for some > 0 and use master theo- rem to solve this recurrence.