Can you help me to solve the recurrence relation $T(n) = T(\sqrt n) + 1 $? I have this recurrence relation to solve :

$T(n) = T(\sqrt n) + 1 $

I have tried to expand the recursion but I stopped here:

\begin{align}
T(n) &amp;= T(n^{\frac12})+1\\
     &amp;= T(n^{\frac14})+1+1\\
     &amp;\text{after $i$ replacements I have}\\
     &amp;= T(n^{\frac1{2^i}}) + i\\
\end{align}
I know that $T(1) = 1$

And now? How can I get to the solution?
If it's related to algorithm complexity, then in this context $\sqrt{n}$ is likely to mean $\lfloor\sqrt{n}\rfloor$ (or $\lceil\sqrt{n}\rceil$). So assume that $T(1) = 1$ and $T(n) = T(\lfloor\sqrt{n}\rfloor)+1$ for $n&gt;1$. Consider $n=2^{2^k}$:
$$T(2^{2^k})=T(\lfloor\sqrt{2^{2^k}}\rfloor)+1 = T(2^{2^{k-1}}) +1 = T(2^{2^{k-2}}) + 2 = \dots=T(2^{2^0}) + k = T(2) + k$$
Now $T(2) = T(\lfloor\sqrt{2}\rfloor) + 1=T(1) + 1 = 2$. So we ended up with
$$T(2^{2^k})=k+2$$
Notice that $T(2^{2^{k+1}}-1)=T(2^{2^k})$ and for $n\leq m$ we have $T(n)\leq T(m)$ (easy to prove by induction). This gives us $T(n)=\lfloor\log_2{(\log_2{n})}\rfloor+2$ for $n&gt;1$.
Let n= 2^m
sqrt(n) = 2^(m/2)
m = logn

replacing T(2^m)= T(2^(m/2)) + 1

now take s(m)= T(2^m)
therefore, s(m)= s(m/2) + 1
now
applying Master rule : n^log(base2)1 = n^0 = 1 equals to f(n)=1
Therefore, t(n)=s(m)= 1.logm = log m =log(log n). [Ans.]