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.

  • $\begingroup$ Is it $T : \mathbb{R} \to \mathbb{R}$, or $T : \mathbb{N} \to \mathbb{R}$? You used $n$ as an argument, which suggests that it is $T : \mathbb{N} \to \mathbb{R}$, but in that case, the square-root ruins everything, and the problem becomes ill-posed. $\endgroup$ – Rod Carvalho Sep 13 '12 at 3:05
  • $\begingroup$ same opinion, and why not write using TeX ? $\endgroup$ – Integral Sep 13 '12 at 3:06

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.

  • 3
    $\begingroup$ Honestly, your Math is a bit too beyond my league. But what you're trying to say is that T(1) = 1 can't be the base condition, right? $\endgroup$ – GrowinMan Sep 13 '12 at 3:31
  • $\begingroup$ If we start with $T(1)=1$, then by the recurrence we have $T(1)=T(\sqrt{1})+1=2$. That shows we cannot have $T(1)=1$, for that would imply that $1=2$! In fact, $T(1)$ cannot exist, for if it is $a$ then the same argument gives $a=a+1$. $\endgroup$ – André Nicolas Sep 13 '12 at 3:39
  • $\begingroup$ For the argument, all I used is the fact that the log to the base $2$ of $2^x$ is $x$. $\endgroup$ – André Nicolas Sep 13 '12 at 3:40
  • $\begingroup$ But you could use any other natural number right? Any number on the form $x^{x^m}$, $x$ natural, would work to start with. $\endgroup$ – Integral Sep 13 '12 at 4:22
  • $\begingroup$ We could start with any integer $c\gt 1$, and then go up to $c^{2^m}$ in $m$ steps. Note that it is $2^m$ in the exponent, that part doesn't change. Or, if we use the floor function to round $\sqrt{n}$, we can start anywhere $\gt 2$ and go down until we hit $2$ or $3$. $\endgroup$ – André Nicolas Sep 13 '12 at 4:35

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.


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$


$\therefore A\ln2=1$


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


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.

  • $\begingroup$ I don’t suppose that the (very late to the table) downvoter would care to explain what’s wrong? $\endgroup$ – Brian M. Scott Jan 24 '15 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.