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

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?

• $\log(x)$ is a function taking an input, I'm not familiar with the notation $\log^n$. Do you perhaps mean $\log n$ or $\log(n)$? – ryan May 12 '17 at 3:24
• @ryan you are right – M a m a D May 12 '17 at 3:34

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