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?
 A: $$S(k)=2^{-k}\cdot T(2^k)\implies S(k)=S(k-1)+\frac1{k\log2}
$$
$$
S(k)=S(0)+\frac{H_k}{\log2}\implies T(2^k)=\Theta(2^k\cdot\log k)$$
...Which does not imply that $T(n)=\Theta(n\cdot\log\log n)$, although this might be the conclusion suggested in your textbook.
A: Suppose you have $T(0) = 0$ and $T(1) = 1$ and your recurrence for $n\ge 2$ is
$$T(n) = 2 T(\lfloor n/2 \rfloor) + \frac{n}{\lfloor\log_2 n\rfloor}.$$
This gives the following exact formula for $T(n)$ where $n\ge 2:$
$$T(n) = 2^{\lfloor \log_2 n \rfloor}
+ \sum_{j=0}^{\lfloor \log_2 n \rfloor - 1} \frac{1}{\lfloor \log_2 n \rfloor - j}
\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k$$
where we suppose that the binary representation of $n$ is
$$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$
The reader is invited to verify this formula which is not at all difficult.
Now for an upper bound consider a string of one digits which gives
$$T(n) \le 2^{\lfloor \log_2 n \rfloor}
+ \sum_{j=0}^{\lfloor \log_2 n \rfloor - 1} \frac{1}{\lfloor \log_2 n \rfloor - j}
\sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k
\\ = 2^{\lfloor \log_2 n \rfloor}
+ \sum_{j=0}^{\lfloor \log_2 n \rfloor - 1} \frac{1}{\lfloor \log_2 n \rfloor - j}
(2^{\lfloor \log_2 n \rfloor+1} - 2^j)
 \\=  2^{\lfloor \log_2 n \rfloor}
+ 2^{\lfloor \log_2 n \rfloor+1}
\sum_{j=0}^{\lfloor \log_2 n \rfloor - 1} \frac{1}{\lfloor \log_2 n \rfloor - j}
- \sum_{j=0}^{\lfloor \log_2 n \rfloor - 1} \frac{2^j}{\lfloor \log_2 n \rfloor - j}
\\= 2^{\lfloor \log_2 n \rfloor}
+ 2^{\lfloor \log_2 n \rfloor+1} H_{\lfloor \log_2 n \rfloor}
- \sum_{j=1}^{\lfloor \log_2 n \rfloor} \frac{2^{\lfloor \log_2 n \rfloor - j}}{j}
\\= 2^{\lfloor \log_2 n \rfloor}
+ 2^{\lfloor \log_2 n \rfloor+1} H_{\lfloor \log_2 n \rfloor}
- 2^{\lfloor \log_2 n \rfloor} \sum_{j=1}^{\lfloor \log_2 n \rfloor} \frac{2^{- j}}{j}.$$
Observe that the remaining sum term converges to a number, so that we get the following asymptotics for the upper bound:
$$2^{\lfloor \log_2 n \rfloor} (1+2H_{\lfloor \log_2 n \rfloor} -\log 2).$$
This upper bound is actually attained and hence cannot be improved upon, just like the lower bound, which we now compute and which occurs for a one digit followed by a string of zero digits, giving
$$ T(n) \ge 2^{\lfloor \log_2 n \rfloor}
+ \sum_{j=0}^{\lfloor \log_2 n \rfloor - 1} \frac{1}{\lfloor \log_2 n \rfloor - j}
2^{\lfloor \log_2 n \rfloor}
=  2^{\lfloor \log_2 n \rfloor} (1+H_{\lfloor \log_2 n \rfloor}).$$
Joining the dominant terms of the upper and the lower bound we get a complexity of
$$\Theta\left(2^{\lfloor \log_2 n \rfloor} \times H_{\lfloor \log_2 n \rfloor}\right)
= \Theta\left(2^{\log_2 n} \log \log n\right)= \Theta\left(n\log \log n\right).$$
This MSE link points to a chain of similar computations.
A: 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)))
$$
