# How to solve the recurrence $T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n}$ in terms of $\Theta$?

I'm attempting to solve the recurrence relation:

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

in terms of its asymptotic behavior ($$\Theta$$), specifically using the first case of the Master's Theorem. We know that if $$O(n^{2-\epsilon}) = \frac{n}{\lg n}$$ is correct, then $$T(n) = \Theta(n^2)$$. However, is this correct? And how can I demonstrate it?

If you want to see it explicitly here is the calculation:

$$T(n)=4T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$ implies that the total number of recursions we do is $$\log_2 n$$. At the pass of the recursion $$i$$, we have $$4^iT\left(\frac{n}{2^i}\right)$$ plus all the other terms deriving by the non-recursive term given by $$\sum_{j=1}^i 4^{j-1}\frac{n/2^{j-1}}{\log(n/2^{j-1})}$$.

Putting all together and assuming that the recursion for $$n=1$$ is $$T(1)=c=O(1)$$, we have:

$$T(n)=c\cdot 4^{\log_2 n} + \sum_{i=0}^{(\log_2 n) -1} 4^i \cdot \frac{n/2^{i}}{\log(n/2^{i})} \ .$$ Simplifying $$4^{\log_2 n}$$ as $$n^2$$ and the fractions inside the summation, we obtain:

$$T(n) = c \, n^2 + n \cdot \sum_{i=0}^{(\log_2 n) -1} \frac{2^i}{\log(n/2^{i})} \ .$$

We can now conclude with a double inequality:

• From one side, it is obvious that $$T(n)\geq n^2$$, so we have $$T(n)=\Omega(n^2)$$.
• On the other hand, we have, from the formula above, that: $$T(n) \ \leq \ c \, n^2 + n\cdot \sum_{i=0}^{(\log_2 n) -1} 2^i \ = \ c \, n^2 + n\cdot\bigl( 2^{\log_2 n} -1 \bigr) \\ \ = \ c \, n^2 + n(n-1) \ \leq \ c \, n^2 + n^2 = (c+1)n^2 \ .$$ With this, we can conclude also that $$T(n)=O(n^2)$$.

Finally, we have $$T(n)=\Theta(n^2)$$.