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