masters theorem

Question

Solution using back substitution method

T(n) = 2T(n/2) + nlogn   ?

detailed solution please.

ans is nlognlogn or n(logn)^2

Comments

In my opinion, nlognlogn and n(logn)^2 are one and the same, aren't they?

---

nloglogn  == n*lon(log n)

but , n(logn)² = n* logn * log n,

both things are different.

Answer 1

Using Master's theorem, it's $O(n(logn)^2)$

By Substitution method, 

Answer 2

Ans is (nloglogn)