# Recurrence $T(n)=T(\sqrt n) + \Theta(\log(\log(n))$

I need to find the bounds of the above recurrence .

I've tried the following however got stuck :

$T(n)=T(\sqrt{n})+Θ(\log(\log(n) )=$

$n=2^m,\quad m=\log(n)$

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

Now define: $S(m)=T(2^m)$ then:

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

Now define : $q=\log(m)$ , $m=2^q$

And we get :$S(2^q)=S(2^q/2)+Θ(q)$

And finally , define : $R(q)=S(2^q )\Longrightarrow R(q)=R(q-1)+Θ(q)$

But how can I continue from here ?

Regards

EDIT:

$R(q-1)=R(q-2)+Θ(q-1)⟹R(q)=R(q-2)+Θ(q)+Θ(q-1)$

$R(q-2)=R(q-3)+Θ(q-2)⟹R(q)=R(q-3)+Θ(q)+Θ(q-1)+Θ(q-2)$

What am I suppose to do with all the : $Θ(q)+Θ(q-1)+Θ(q-2)$ ?

Thanks

-
You really shouldn't forget the constant in the big-$O$ notation. The recurrence $R$ you derive is one of the simplest recurrences: I bet you actually have it memorized, but didn't think to think about it! If you really can't see it, try writing out the first few terms explicitly in terms of $R(0)$.... – Hurkyl Apr 5 '12 at 21:21
@Hurkyl: I've made some changes , and would appreciate if you could check them out . – ron Apr 5 '12 at 21:55
While your work is no longer wrong, you've taken a step backwards. You can't do anything with $\Theta(q) + \Theta(q-1) + \cdots$, because any strange thing could be happening with the constants hidden in the big-$\Theta$ notation. You have to take advantage of the fact it all originated with the original $\Theta(\log \log n)$. I.E. that you know there are M and N so that $T(\sqrt{n}) + M \log \log n \leq T(n) \leq T(\sqrt{n}) + N \log \log N$. – Hurkyl Apr 5 '12 at 23:59
@Hurkyl : You mean that all the $define$S that I've made are not necessary ? – ron Apr 6 '12 at 0:07
No, you have the right underlying idea. See Didier's answer where he finished up the proof, rather than suggesting how you might see it for yourself. (The main thing I was hoping you'd notice is that you'd recognize $C q + C (q-1) + C (q-2) + \cdots$ as being a sum of consecutive integers) – Hurkyl Apr 6 '12 at 0:49

You know that $T(\sqrt{n})+A\log\log n\leqslant T(n)\leqslant T(\sqrt{n})+B\log\log n$ for some constants $A$ and $B$. As in your post, let $R(q)=T(2^{2^q})$, then $$R(q-1)+A(q\log 2+\log\log2)\leqslant R(q)\leqslant R(q-1)+A(q\log 2+\log\log2),$$ hence there exists $A'$ and $B'$ such that $A'q\leqslant R(q)-R(q-1)\leqslant B'q$. Summing this from $1$ to $q$, one gets $$\frac{A'}2q^2\leqslant A'\sum_{k=1}^qk\leqslant R(q)-R(0)\leqslant B'\sum_{k=1}^qk\leqslant B'q^2.$$ Finally, $$\color{red}{T(n)=\Theta((\log\log n)^2)}.$$

-

After you get $S(m) = S(m/2) + \log(m)$, you can use the Master Theorem:

$f(m) = \log m = \Theta(m^{\log_2 1}\times (\log m)^1) = \Theta(\log m)$. Therefore

$$S(m) = \Theta(m^{\log_2 1}\times (\log m)^2)=\Theta((\log m)^2)$$

Or:

$$T(n) = \Theta((\log \log n)^2)$$

-