<s>[INST] How to solve this recurrence $T(n)=2T(n/2)+n/\log n$ How can I solve the recurrence relation  $$T(n)=2T\left(\frac n2\right)+\frac{n}{\log n}$$?
I am stuck up after few steps..
I arrive till
$$T(n) = 2^k T(1) + \sum_{i=0}^{\log(n-1)} \left(\frac{n}{\log n} - i\right)$$
How to simplify this log summation?
 [/INST] Your summation is wrong, and you should have replaced $k$ with $log(n)$ in your last expression.
Here are detailed steps of this recurrence relation:
$$
\\
T(n) = 2T(\frac{n}{2}) + \frac{n}{\log n}
\\
T(n) = 2(2T(\frac{n}{4}) + \frac{\frac{n}{2}}{\log \frac{n}{2}}) + \frac{n}{\log n} = 2^2T(\frac{n}{2^2}) + \frac{n}{\log(n) - 1} + \frac{n}{\log n}
\\
T(n) = 2(2(2T(\frac{n}{8}) + \frac{\frac{n}{4}}{\log \frac{n}{4}}) + \frac{\frac{n}{2}}{\log \frac{n}{2}}) + \frac{n}{\log n} = 2^3T(\frac{n}{2^3}) + \frac{n}{\log(n) - 2}  + \frac{n}{\log(n) - 1} + \frac{n}{\log n}
\\
...
\\
T(n) = 2^kT(\frac{n}{2^k}) + \sum_{i = 0}^{ k - 1}\frac{n}{\log(n) - i}
\\
\text{When } \frac{n}{2^k} = 1 \Rightarrow n = 2^k \Rightarrow k = \log_2(n)
\\
T(n) = 2^{\log_2(n)}T(1) + \sum_{i = 0}^{ \log_2(n) - 1}\frac{n}{\log(n) - i}
\\
T(n) = \Theta (n) + \sum_{i = 0}^{ \log_2(n) - 1}\frac{n}{\log_2(n) - i}
\\
T(n) \approx  \Theta (n) + \sum_{j = 1}^{ \log_2(n)}\frac{n}{j}
\\
T(n) \approx  \Theta (n) + nH_{\log_2(n)}
\\
T(n) \approx  \Theta (n) + n \ln(\log_2(n))
\\
\text{And finally }
T(n)\ \in \Theta(n \ln(\log_2(n)))
$$
</s>