CODEWITHSUNDEEP
algorithmrecursiontime-complexitymaster-theorem
user3100258
user3100258

Reputation: 45

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

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.

Upvotes: 1

Views: 7865

Answers (2)

njwfish
njwfish

Reputation: 108

Ok, so the error here is in this line:

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

In fact, if you let S(m)=T(2^m)/2^m, then you will have S(m)=2S(m-1)+m, because of the division by 2^(m-1).

With this correction we have:

S(m) = 2S(m - 1) + m
     = 2S(2S(m - 2) + m) + m
     = 4S(m - 2) + (m − 1) + m
     = 4S(2S(m - 3) + (m - 2)) + (m − 1) + m
     = 8S(m - 3) + (m - 2) + (m - 1) + m

This gives us the general form:

S(m) = 2^m S(0) + m(m+1)/2

Plugging back in, we have then that:

T(2^m) = 2^m T(0) + m(m+1) 2^(m-1)

Then we can plug back in for n:

T(n) = nT(1) + n/2 (logn)(1 + logn) = O(n(logn)^2)

Upvotes: 1

Sumeet
Sumeet

Reputation: 8292

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)

Upvotes: 2

Related Questions