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

Improve this question
$\endgroup$
13
  • 1
    $\begingroup$ Give base case ? $\endgroup$
    – hanugm
    Commented Aug 19, 2014 at 9:37
  • $\begingroup$ And is this discrete? Should it be, say, $\lfloor \tfrac13\sqrt{n}\rfloor\,$? $\endgroup$
    – David Richerby
    Commented Aug 19, 2014 at 10:13
  • $\begingroup$ Dear @hanu, we have no base case. $\endgroup$
    – Mina Simin
    Commented Aug 19, 2014 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
    Commented Aug 19, 2014 at 10:37
  • 1
    $\begingroup$ The last line in your post should be $=O(\log^2n\log\log n)$. $\endgroup$
    – Rick Decker
    Commented Aug 19, 2014 at 14:58

0

Reset to default

Browse other questions tagged or ask your own question.