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) &= T(n^{\frac12})+1\\
     &= T(n^{\frac14})+1+1\\
     &\text{after $i$ replacements I have}\\
     &= T(n^{\frac1{2^i}}) + i\\
\end{align}
I know that $T(1) = 1$
And now? How can I get to the solution?
 A: If it's related to the 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>1$.
Consider $n=2^{2^k}$:
$$\begin{align}
T\left(2^{2^k}\right)
&= T\left(\left\lfloor\sqrt{2^{2^k}}\right\rfloor\right)+1 \\
&= T\left(2^{2^{k-1}}\right) + 1 \\
&= T\left(2^{2^{k-2}}\right) + 2 \\
&= \dots \\
&=T\left(2^{2^0}\right) + k \\
& = T(2) + k \\
&= T(1) + k + 1 \\
&= k+2
\end{align}$$
Now notice that:

*

*$T\left(2^{2^{k+1}}-1\right)=T\left(2^{2^k}\right)$ (to see it just expand left hand side as above),


*$T(n)\leq T(m)$ for $n\leq m$ (can be proven by induction).
From this we can conclude that $T(n)=\lfloor\log_2{(\log_2{n})}\rfloor+2$ for $n>1$.
A: Let $n= 2^m$. Then
$$
\sqrt{n} = 2^{m/2} \quad\text{and}\quad m = \log n.
$$
Replacing $n=2^m$ in $T(n)$ gives
$$
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_21} = n^0 = 1
$$
equals to $f(n)=1.$ Therefore,
$$
T(n)=s(m)= 1,
$$
and
$$
\log m = \log(\log n).
$$
