2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.