Solving $T(n) = 4T(n/2) + \Theta(n^2 / \log n)$.

Question

I am trying to solve

$$T(n) = 4T(n/2) + \Theta(n^2 / \log n)$$

Edit: I know the solution is $\Theta(n^2 \log \log n)$, i just dont know how to get there.

Any help is greatly appreciated! Thanks!

Answer 1

You're not supposed to prove that (even if it's true). You need to use the extended version of the Master Theorem (or you can also use the generalisation: Akra-Bazzi). You're in the case where $c = \log_ba= 2$, and $f(n) = \Theta(n^c\log^{-1}n)$, this is a special case, it yields $T(n) = \Theta(n^c\log(\log n))$. Refer to: https://en.m.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms) Specifically 2b.

Answer 2

I know the solution is [T]heta(n^2 log logn), [I] just dont know how to get there.

A simple and completely self-contained way to "get there" is to consider the change of variable $$S(k)=4^{-k}T(2^k)$$ Then the recursion becomes $$S(k)=S(k-1)+\Theta\left(\frac1k\right)$$ from which one gets $S(k)=\Theta(H_k)$ with $$H_k=\sum_{\ell=1}^k\frac1\ell\sim\log k$$ Coming back from $H_k$ to $S(k)$ and from $S(k)$ to $T(2^k)$, this yields $$T(2^k)=4^k\cdot\Theta\left(\log k\right)=\Theta\left(4^k\log k\right)$$ Considering that $4^k=(2^k)^2$ and that $\log k=\Theta(\log\log 2^k)$, this rigorous result is usually extended without proof (although the implication does not hold without some supplementary regularity hypothesis) to $$T(n)=\Theta\left(n^2\log\log n\right)$$