How to solve recurrence T(n) = 2T(n/2) + n/log(n) using substitution method

Question

The guess solution to the

$$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$

is $\Theta(n \log{\log n})$. This is my solution: $$ T(n) \leq 2c\left(\frac{n}{2}\right) \log{\log {\frac{n}{2}}} + \frac{n}{\log n} \\ \leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\ \leq cn \log{\log {n}} + \frac{n}{\log n} $$

that fails to for the $T(n) \leq cn \log{\log {n}}$

Now I try to solve the $T(n) \leq c(\log \log n - \frac{n}{\log n})$, we have $$ T(n) \leq 2c\left(\left(\frac{n}{2}\right) \log \log {\frac{n}{2}} - \frac{\frac{n}{2}}{\log {\frac{n}{2}}}\right) + \frac{n}{\log n}\\ \leq cn \log \log {\frac{n}{2}} - \dfrac{n}{\log n - 1} + \dfrac{n}{\log n}\\ \leq cn \log \log {n} - \dfrac{n}{\log n - 1} + \dfrac{n}{\log n}\\ $$ and it will never be $\leq cn \log \log {n} - \dfrac{n}{\log n}$

How can I solve the recurrence?

Answer 1

$$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) &= \frac{n}{\log n} + 2 \frac{\frac{n}{2}}{\log \frac{n}{2}} + 4 \frac{\frac{n}{4}}{\log \frac{n}{4}} + \dots \\ & = \frac{n}{\log n} + \frac{n}{\log \frac{n}{2}} + \frac{n}{\log \frac{n}{4}} + \dots + n\\ & = n \left[\frac{1}{\log n} + \frac{1}{\log(n) - 1} + \frac{1}{\log(n) - 2 } + \dots + 1\right]\\ & = n \sum_{i = 0}^{\log n - 1} \frac{1}{\log(n) - i}\\ & = 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) & \leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\ & \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) & \leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\ & \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} < \log_2 \log_2 n$$

For $n > 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 $$