Solving the recurrence relation $T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n$

Question

How we calculate the answer of following recurrence?

$$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$

Any nice solution would be highly appreciated.

My solution is:

$n=3^m \to T(3^m)=4T(\frac{3^{m/2}}{3})+log^2 3^m = O(Log^2 n log n log n)$

Answer 1

Introduce the auxiliary (sub)sequence $(S(k))$, defined for every $k\geqslant1$ by $$S(k)=4^{-k}\cdot T(3^{2^k-2}),$$ then the recursion on $(T(n))$ becomes $$S(k)=S(k-1)+4^{-k}\cdot(\log(3^{2^k-2}))^2,$$ for every $k\geqslant2$, that is, $$S(k)=S(k-1)+4^{-k}\cdot(\log3)^2\cdot(2^k-2)^2=S(k-1)+(\log3)^2\cdot(1-2^{-(k-1)})^2.$$ Since $(\log3)^2\cdot(1-2^{-(k-1)})^2\to(\log3)^2\ne0$ when $k\to\infty$, this yields $$S(k)\sim(\log3)^2\cdot k,$$ that is, $$T(3^{2^k-2})\sim(\log3)^2\cdot k\cdot4^k.$$ Let $n=3^{2^k-2}$, then $2^k=2+\log_3n$ hence $2^k\cdot\log3\sim\log n$, thus, $4^k\cdot(\log3)^2\sim(\log n)^2$, and $k\sim(\log\log n)/\log2$, hence $$T(n)\sim(\log\log n)(\log n)^2/(\log2),$$ in particular, $$T(n)=\Theta((\log\log n)(\log n)^2).$$ One sees that $T(n)$ is $O((\log\log n)(\log n)^2)$ and that $T(n)$ is not $O((\log n)^2)$.