Recursive equation time complexity

Question

How to apply back substiution method on following recursive equation to find time complexity:

T(n)= 2 T(n/2) + (n/log n) , where "n" is input.

Answer 1

T(n)=2T(n/2) + n/log(n)

T(n/2)=2T(n/4) + (n/2)/(log n/2)

Substituting back in first equation,

T(n)=2^2T(n/2^2) + n/log(n/2) + n/log(n)

Now we can generalize the above as:

T(n)=2^k T(n/2^k) + n/log(n/2^k-1) + n/log(n/2^k-2) + . . . + n/log(n/2) + n/log(n)

Assuming T(1) =1,

then, k=log(n).

Now the equation becomes,

T(n)=n.(1) + n [ 1/1 + 1/2 + ... + 1/k-1 + 1/k] /// here i have reduced 1/log(n/2^k-1) to 1/1 as 2^k=n and log2 =1.

T(n) = n+n[log(k)]

Substituting value of k as log(n), we get,

T(n)= n + nlog(log(n)).

Hence complexity is O(n.loglogn).

We can verify this by master's theorem also. (It will come under case 2 in it.)

Comments

Using the master's theorem, do we take (n/log n) as f(n). Because I'm not getting the same complexity using the master's theorem.

---

Shweta Nair apply carefully master theorem ..You will get right answer

T(n)=O(nloglogn)