3

Sorry about the formatting of the title I'm not sure of the codes to make it look better.

I need to find the recurrence relation of the following:

$$T(0) = 1$$

$$T(n) = 2T\left(\left\lfloor\sqrt{n}\right\rfloor\right)+\log(n)$$

I assume this is going to be done via substitution method and through induction, but I have no idea how to set it up/solve it.

The answer is $T(n)=\theta\left(\log\,n \cdot\log\log\,n\right)$

Community
  • 1
deasy
  • 65
  • What do you mean by $\theta$? (Is it about asymptotic growth?) - Also, note that if we let $f(n) = e^{T(n)}$, we get the reccurence as $f(n) = nf(\lfloor\sqrt{n}\rfloor)^2$. – Milo Brandt Oct 18 '14 at 01:52
  • Yeah, it is about asymptotic growth. – deasy Oct 18 '14 at 02:05

2 Answers2

2

Hint: Let $n = 2^m$. The recurrence becomes $$ T(2^m) = 2\,T(2^{m/2}) + m $$ (assuming logs to the base 2). Then let $T(2^m) = S(m)$, giving us the recurrence $$ S(m) = 2\,S(m/2)+m $$ This is a well-known recurrence with solution $S(m) = \Theta(m\log m)$, from which we can conclude (since $\log n = m$), $T(n) = \Theta(\log n\,\log\log n)$. Now just fill in the details.

Rick Decker
  • 8,718
2

Making the exponential tower one higher, let $n = 2^{2^m}$. Then $\lfloor \sqrt{n} \rfloor =\lfloor \sqrt{2^{2^m}} \rfloor =\lfloor 2^{2^{m-1}} \rfloor $ and $\log n =\log 2^{2^m} = 2^m $.

The recurrence becomes $T(2^{2^m}) =2T(2^{2^{m-1}})+2^m $.

Let $S(m) =T(2^{2^m}) $. Then $S(m) =2S(m-1)+2^ m $ or, dividing by $2^m$, $2^{-m}S(m) =2^{-(m-1)}S(m-1)+1 $. Letting $2^{-m}S(m) =U(m) $, $U(m) =U(m-1)+1 $.

Summing, $U(m) = m$ so $S(m) =m2^m $.

Finally, $T(m) =S(\log \log m) =(\log \log m)2^{\log \log m} =\log m \log \log m $.

This avoids appealing to a "well known recurrence".

marty cohen
  • 107,799