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 
 A: You are given that $$T(\sqrt{n})+A\log\log n\leqslant T(n)\leqslant T(\sqrt{n})+B\log\log n$$ for every $n$, for some constants $A$ and $B$. As in your post, let $$R(q)=T(2^{2^q})$$ then 
$$
R(q-1)+A\cdot(q\log 2+\log\log2)\leqslant R(q)\leqslant R(q-1)+A\cdot(q\log 2+\log\log2)
$$
hence there exists $A'$ and $B'$ such that $$A'q\leqslant R(q)-R(q-1)\leqslant B'q$$ for every $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)}.
$$
A: 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)$$
A: $T(n)=T(\sqrt n)+Θ(log(log(n))$
put  $n=2^m$
$T(2^m)=T(\sqrt 2^m)+Θ(log(log(2^m))$
$T(2^m)=T(2^{m/2})+Θ(log(m))$
assume $T(2^m) = S(m)$
then,
$S(m)=S(m/2)+Θ(log(m))$
now put $m=2^r$
$S(2^r)=S({2^r}/2)+Θ(log(2^r))$
assume $S(2^r)=P(r)$
$P(r)=P(r-1)+Θ(r)$
$P(r)=P(r-2) ++Θ(r-1) +Θ(r)$
..
$P(r)=P(0) ++Θ(1)+Θ(2)... +Θ(r-1)+Θ(r)$
or
$P(r)=P(0)+Θ(r^2)$
putting back the value of r and m and getting relation in terms of T and n.
$T(n)=T(2) + Θ({(log(log(n))}^2)$
or
$T(n)=Θ({(log(log(n))}^2)$
