What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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$ .

Answer 4

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.