How to solve recurrence T(n) = 2T(n/2) + n/log(n) using substitution method
$$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$

Would yield the following summation (assuming $n$ is a power of 2 and base case is $n=2$):

$$
\begin{align}
T(n) &amp;= \frac{n}{\log n} + 2 \frac{\frac{n}{2}}{\log \frac{n}{2}} + 4 \frac{\frac{n}{4}}{\log \frac{n}{4}} + \dots \\
&amp; = \frac{n}{\log n} + \frac{n}{\log \frac{n}{2}} + \frac{n}{\log \frac{n}{4}} + \dots + n\\
&amp; = n \left[\frac{1}{\log n} + \frac{1}{\log(n) - 1} + \frac{1}{\log(n) - 2 } + \dots + 1\right]\\
&amp; = n \sum_{i = 0}^{\log n - 1} \frac{1}{\log(n) - i}\\
&amp; = n \cdot H_{\log n}\\
\end{align}
$$

Where $H_n$ is the $n$th Harmonic number. It's known that $H_n = \Theta(\log n)$. 

We can thus conclude
$$T(n) = \Theta( n \log \log n )$$

Now with this being said; I believe this issue in your logic is the following steps:
$$
\begin{align}
T(n) &amp; \leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\
&amp; \leq cn \log{\log {n}} + \frac{n}{\log n}
\end{align}
$$
The jump from step 1 to step 2, while not incorrect, is not tight. Which is why you're not meeting the necessary conclusion. It should be something like:
$$
\begin{align}
T(n) &amp; \leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\
&amp; \leq cn \left[\log \log \frac{n}{2} + \frac{1}{\log n}\right]
\end{align}
$$
It can then be proven by induction that:

$$\log_2 \log_2 \frac{n}{2} + \frac{1}{\log_2 n} &lt; \log_2 \log_2 n$$

For $n &gt; 2$. The proof is pretty straightforward and I'll leave it as an exercise for the reader, but it then follows that:

$$
T(n)  \leq cn \log\log n
$$