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

Question

What is time complexity of

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

I cannot solve it by recursion tree or any other method.

we have the base T(1) = 1

I may think about sandwich theorem but dont know how to use.

Answer 1

Let $b$ be the base of the logarithm, and let $n = b^m$. Then

$$ T(b^m) = 4 \cdot T\left( b^{m/2 - \log 3} \right) + \log^2 n $$

which suggests setting

$$ S(m) = T(b^m) \qquad \qquad T(n) = S(\log n)$$

and then first solving the recurrence

$$ S(m) = 4 \cdot S\left(\frac{m}{2} - \log 3 \right) + m^2 $$

where I've assumed by $\log^2 n$ you mean $(\log n)^2$ rather than $\log \log n$.

Answer 2

The following is an upper bound, which probably is good enough for any analysis.

We have $$T(n)\leq4 \cdot T \left(\frac{n}{3} \right) + n$$ Using Master Theorem we get $O(n^{\log_34})$.