Time complexity of $T(n)= 2T(\left\lfloor\sqrt n\right\rfloor) + \log^3(n)$

Question

I have to solve the time complexity of the above recurrence. My steps so far are:

let $n= 2^m$

$T(2^m)= 2T(2^{m/2})+ \log^3(2^m)$

$S(m)= T(2^m)$

$S(m)= 2S(m/2)+ \log^3(2^m)$

This solves to $S(m)= \Theta(m \log(m))$

This means for T:

$T(n)= \Theta(\log(n)*\log\log(n))$

I'm not so sure about this. Could you help me?

Answer 1

When you have $$ S(m)=2S\left(\frac m2\right)+\log^3(2^m)=m^3\underbrace{\log^3(2)}_{k}+2S\left(\frac m2\right) $$

You can substitute couple more steps to see the pattern: $$ S(m)=km^3+2S(m/2)=km^3+2k\left(\frac m2\right)^3+4S(m/4)=\\km^3+2k\left(\frac m2\right)^3+4k\left(\frac m4\right)^3+8S(m/8)=\ldots= km^3\underbrace{\left(1+\frac1{2^2}+\frac1{4^2}+\ldots\right)}_{\log m\text{ terms}} $$

We can see that the coefficient is between $1$ and $\sum_0^\infty4^{-n}=4/3$. In other words, it is constant. Thus, $S(m)=\Theta(m^3)$