# Big O Solving recurrences

Hello So I am having trouble solving this recurrence: $t(n) = t(\sqrt{n}) + 1$. The master method does not apply here. Ive done some research and it seems you have to manipulate the domain and range. Some of the manipulations I have seen are let $n = 2^m$ where $m = \lg n$ but im not sure how this was done. Any insight into how I can solve this recurrence would be truly appreciated.

-

First, the original recurrence relation reads as follows:

\begin{align} t(n) &= t(\sqrt{n}) + 1.\tag{1}\end{align}

We can transform the $1/2$ in the exponent ($\sqrt{n} = n^{1/2}$) to a $1/2$ as a multiplicative factor, by using $n = 2^m$ as you already suggested. Let $u(m) := t(2^m) = t(n)$. Then:

\begin{align} u(m) = t(2^m) = t(n) &\stackrel{(1)}{=} t(\sqrt{n}) + 1 = t(2^{m/2}) + 1 = u(m/2) + 1.\tag{2}\end{align}

Now you could try to solve this, or you could even take it one step further. Let $m = 2^k$, and $v(k) := u(2^k) = u(m)$. Then:

$$v(k) = u(2^k) = u(m) \stackrel{(2)}{=} u(m/2) + 1 = u(2^{k-1}) + 1 = v(k - 1) + 1.\tag{3}$$

We can now easily solve $(3)$ and plug the solution back into $u$ and $t$ to obtain:

$$v(k) = k + v(0) \quad \Rightarrow \quad u(m) = \log m + u(1) \quad \Rightarrow \quad \boxed{t(n) = \log \log n + t(2)}.$$

(Note that I disregarded minor things like rounding up or down. Logarithms are to the base $2$.)

-