Question

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

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

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

(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)).

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

Solution:

I believe that we can use master theorem with this recurrence T(n) = 2T(n/2) + nlogn

The provided recurrence is of the form T (n) = a T(n/b) + theta (n^k log^pn) where a>=1, b >1, k >=0, p is a real number, then:

in your example the value of a=2 and b=2 and k=1, and this means that a is equal to b^k

the value of p > -1, then T (n) = Theta (n^log_ba log ^p+1 n)

So, after applying the master theorem:

T (n) = Theta ( n ^ log₂2 log ² n) => Theta (nlog²n )

Please give thumbsup or do comment in case of any query. Thanks.