# Solve Recurrence Equation Problem [duplicate]

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 to substitute $n=3^m$, giving $$T(3^m)=4T\left(\frac{3^{m/2}}{3}\right)+\log^2 3^m = F(m)=4F((m/2)-1)+m^2=O(m^2logm)= O(\log^2 n \log n \log n)\,.$$

• Give base case ? – hanugm Aug 19 '14 at 9:37
• And is this discrete? Should it be, say, $\lfloor \tfrac13\sqrt{n}\rfloor\,$? – David Richerby Aug 19 '14 at 10:13
• Dear @hanu, we have no base case. – Mina Simin Aug 19 '14 at 10:13
• @DavidRicherby The reference question does not explain how to deal with the $\sqrt{n}$. This question may be a better target. – FrankW Aug 19 '14 at 10:37
• The last line in your post should be $=O(\log^2n\log\log n)$. – Rick Decker Aug 19 '14 at 14:58