Find tight bounds to $T(n)=2T(\frac n 2) +\frac{n}{\log n}$
The upper bound: $\displaystyle 2T(\frac n 2) +\frac{n}{\log n} \le T(\frac n 2) +n = \sum_{i=0}^{\log n}\frac n {2^i} \le n\sum_{i=0}^{\log n}\frac 1 {i}=\Theta (n\log \log n)$.
But I can't figure out how to do the lower bound, I either get stuck like this:
$\displaystyle T(n)\ge T(\frac n 2)+\frac 1 {\log n} = \sum_{i=0}^{\log n} \frac 1 {\log n - i}$
Or get an expression too small.
Note, I don't want to solve it, just find tight bounds.
Set $n=2^k$ and $g(k) = T(n)$. We then have \begin{align} g(k) & = 2g(k-1) + \dfrac{2^k}k = 4g(k-2) + \dfrac{2^k}{k-1} + \dfrac{2^k}k = 2^k g(0) + \sum_{l=1}^k \dfrac{2^k}l = 2^kg(0) + 2^k H_k\\ & \sim ng(0) + n\log(k) + n\gamma = n(g(0)+\gamma) + n\log(\log(n)) \end{align}