Solving running time of T(n)=2T(n/2)+nlogn

Question

I'm trying to solve this in a certain way ,I already know that its complexity is BigTheta(nloglogn) ,but i don't get the same answer if i do the following:

let m = logn
then n = 2^m
we get T(2^m) = 2T(2^(m-1))+(2^m)*m
multiply by 1/(2^m)
we get T(2^m)/2^m = 2T(2^(m-1))/2^m + m
= T(2^(m-1))/(2^(m-1)) + m

Now if i let S(m)=T(2^m)/2^m I will have S(m)=S(m-1)+m.

Now I solve S(m)=S(m-1)+m by back substitution method.

S(m) = S(m-1)+m=S(m-2)+(m-1)+m = S(m-3)+(m-2)+(m-1)+m = S(m-4)+(m-3)+(m-2)+(m-1)+m=... = S(m-k)+(m-k+1)+..+(m-3)+(m-2)+(m-1)+m = ... = S(1)+2+...+m = m(m-1)/2 = BigTheta(m^2)

Plugging back m=logn and i get BigTheta((logn)^2) which is not the same.

Answer 1

You have followed the right approach my friend. There's a slight mistake though.

S(m) = S(m-1) + m

which is correct and we get S(m) = BigTheta(m^2).

Now S(m) = T(2^m)/(2^m) = BigTheta(m^2) . This means T(2^m) = T(n) = (2^m) * BigTheta(m^2).

Putting back the values we get T(n) = n*BigTheta(lognlogn) = BigTheta(n*lognlogn)