Question

NOTE: The first three are rules and do not have to be solved. Just there for the master theorem.

Master Theorem. Let T(n) = aT(n/b) + f(n) for some constants a ≥ 1, b > 1.

(Rule 1). If f(n) = O(n logb a− ) for some constant > 0, then T(n) = Θ(n logb a ).

(Rule 2). If f(n) = Θ(n logb a ), then T(n) = Θ(n logb a log n).

(Rule 3). If f(n) = Ω(n logb a+ ) for some constant > 0, and af(n/b) ≤ cf(n) for some constant c < 1, for all large n, then T(n) = Θ(f(n)).

1. Consider the recurrences: T(n) = 2T(n/2) + n log n. Either solve it using the Master method as given above, or explain why it can’t be solved using the Master method. If it can not be solved using Master method, use Recurrence tree method to solve it. Show your steps. If you use extended version of Master theorem to solve the same problem, does the solution thus obtained agree with the solution obtained by recurrence method?

Answer 1