9

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?

Start wearing purple
  • 53,234
  • 13
  • 164
  • 223
user1868607
  • 939
  • 5
    It doesn't make sense. $1 = T(1) = T(\sqrt{1}) + 1 = T(1)+1 = 2$. – Étienne Bézout Oct 24 '13 at 15:26
  • Note that if you hold the relationship for $n=1$, then you will have $T(1)=T(1)+1$ which is not possible for the reals. – Carlos Eugenio Thompson Pinzón Oct 24 '13 at 15:27
  • Forgetting about the boundary condition which doesn't work, rewrite the recurrence relation as $T(k^2) = T(k) + 1$ (that is, take $n = k^2$). – Étienne Bézout Oct 24 '13 at 15:28
  • Is it just $T(\sqrt{n})$ or rather one of $T(\lceil \sqrt{n} \rceil)$, $T(\lfloor \sqrt{n} \rfloor)$? – Adam Oct 24 '13 at 15:30
  • ... and you should look out for a solution where the resulting function has singularities at $n=1$ and $n=0$... – Gottfried Helms Oct 24 '13 at 15:31
  • @Adam it's just T(sqrt(n)) – user1868607 Oct 24 '13 at 15:48
  • @user1868607 then it doesn't make sense. $T(1)$ is unrelated to other values, because the only number $n$ such that $\sqrt{n}=1$ is $n=1$. What is the domain of $T$ and where did you find this relation? If it's relation for complexity of some algorithm, then i'm almost sure you want it to be ceiling or floor of $\sqrt{n}$ – Adam Oct 24 '13 at 16:29
  • @Adam Actually is an exercise for my Algorithm exam, It just says to resolve this recurrence relation... – user1868607 Oct 24 '13 at 20:21

2 Answers2

14

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:

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

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

Adam
  • 1,946
0

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

Mr.Young
  • 485
sam
  • 19