What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$? This looks like a question asked earlier, but it isn't.
$$T(n)=\begin{cases} T (\sqrt{n}) + 1 \quad & \text{ if } n>1 \\
 1 & \text{ if }n=1\end{cases}$$
My professor gave this to me in class yesterday. This is where I'm stuck: 
$$T(n) =  T(n^{1/2})+1 =  T(n^{1/4})+2 = T(n^{1/8})+3
= \dots =   T(n^{1/ 2 ^k})+k$$
Now this will continue till
$$n^{1/ 2 ^k}=1$$
How do I proceed ahead? If I take log on both sides, then RHS becomes zero.
How do I solve the relation?
I don't want to use the Master theorem, I want to know where and why am I stuck.
 A: We have a recurrence that is ostensibly over the integers. But if $n$ is an integer, then $\sqrt{n}$ is not necessarily an integer. One way of getting an informal answer is to imagine that we start with an integer $n$ of the form $2^{2^m}$. Then $\sqrt{n}=2^{2^{m-1}}$.  (To find the square root, we divide the exponent by $2$.)
So going up from $2^{2^0}$ to $2^{2^m}$, we have incremented $T$ by $m$.  If we start with $T(2)=0$, then 
$$T\left(2^{2^m}\right)=m.$$
If $T(2)$ has some other value $a$, then $T\left(2^{2^m}\right)=a+m$.
Note that $m=\log_2\left(\log_2\left(2^{2^m}\right)\right).$ 
So for this value of $n$, and $T(2)=0$, we have $T(n)=\log_2(\log_2(n))$. If $T(2)=a$, just add $a$. 
Remark: The above calculation can be carried out in basically the same way if we assume that $T(n)=T(\lfloor\sqrt{n}\rfloor)+1$. The conclusion is that for large $n$, $T(n)$ behaves like $\lg\lg n$. And $\lg\lg n$ grows glacially slowly.
A: First, this belongs to a recurrence relation of the form http://eqworld.ipmnet.ru/en/solutions/fe/fe2308.pdf
Let $n_1=\ln n$ , $T_1(n_1)=T(n)$ ,
Then $T_1(n_1)=T_1\left(\dfrac{n_1}{2}\right)+1$
Then, this belongs to a recurrence relation of the form http://eqworld.ipmnet.ru/en/solutions/fe/fe2303.pdf
Let $n_2=\ln n_1$ , $T_2(n_2)=T_1(n_1)$ ,
Then $T_2(n_2)=T_2(n_2-\ln2)+1$
In fact this belongs to a recurrence relation of the form http://eqworld.ipmnet.ru/en/solutions/fe/fe1108.pdf.
The general solution of this recurrence relation is $T_2(n_2)=\Theta(n_2)+T_{2,p}(n_2)$ , where $\Theta(n_2)$ is an arbitrary periodic function with period $\ln2$
Luckily we can find $T_{2,p}(n_2)$ by method of undetermined coefficients:
Let $T_{2,p}(n_2)=An_2$ ,
Then $T_{2,p}(n_2-\ln2)=A(n_2-\ln2)$
$\therefore An_2-A(n_2-\ln2)\equiv1$
$A\ln2\equiv1$
$\therefore A\ln2=1$
$A=\dfrac{1}{\ln2}$
$\therefore T_2(n_2)=\Theta(n_2)+\dfrac{n_2}{\ln2}$ , where $\Theta(n_2)$ is an arbitrary periodic function with period $\ln2$
$T(n)=\Theta(\ln\ln n)+\dfrac{\ln\ln n}{\ln2}=\Theta(\ln\ln n)+\log_2\ln n$ , where $\Theta(n)$ is an arbitrary periodic function with period $\ln2$
Note that $n$ cannot directly substitute $1$ as the recursion cannot form when $n=1$ .
A: We shall find  functions $x\mapsto T(x)$, defined for all real $x>1$, that satisfy the given recurrence relation. 
Replace the unknown function $T$ by
$$g(\alpha):=T\bigl(\exp(2^\alpha)\bigr)\qquad(-\infty<\alpha<\infty)\ .$$
Then, according to the recurrence relation for $T$, the function $g$ satisfies
$$g(\alpha)=T\bigl(\sqrt{\exp(2^\alpha)}\bigr)+1=T\bigl(\exp(2^{\alpha-1})\bigr)+1=g(\alpha-1)+1\ ,$$
or
$$f(\alpha):=g(\alpha)-\alpha=g(\alpha-1)-(\alpha-1)=f(\alpha-1)\qquad(\alpha\in{\mathbb R})\ .$$
This shows that $$g(\alpha)=\alpha +f(\alpha)\ ,$$
where now $f$ is an arbitrary function of period $1$.
In order to return to the variable $x$ we have to solve the equation $\exp(2^\alpha)=x$ for $\alpha$ and obtain $\alpha={\log\log x\over\log 2}$. As the steps leading to $g$ can be reversed, it follows that
$$T(x)=g\Bigl({\log\log x\over\log 2}\Bigr)={\log\log x\over\log 2}+ f\Bigl({\log\log x\over\log 2}\Bigr)\qquad(x>1)$$
is the general solution of our problem. 
A: If you’re really asking for the asymptotic behavior of the sequence $\langle T(n):n\in\Bbb Z^+\rangle$, see André’s answer. If you’re looking for an exact closed form solution, you’ll need to make some adjustment in the recurrence to replace $\sqrt n$ by an integer. As an example, you could assume that there’s an implied floor function in the recurrence: $T(n)=T(\lfloor\sqrt n\rfloor)$ for $n>1$. Now suppose that $m^2\le n<(m+1)^2$ for some positive integer $m$; then $m\le\sqrt n<m+1$, so $\lfloor\sqrt n\rfloor=m$, and $T(n)=T(m)+1$. This means that $T$ will be constant over the entire interval $\left[m^2,(m+1)^2\right)$. 
Now make a little table:
$$\begin{array}{r|cc}
m&1&&&2&&&&&3&&&&&&&4\\ \hline
n&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\ \hline
T(n)&1&2&2&3&3&3&3&3&4&4&4&4&4&4&4&5
\end{array}$$
This should give you a very good idea of what $T$ does under the given assumption, but I’ll leave it to you to translate that behavior into a concrete formula.
