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