3
$\begingroup$

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

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