Time Complexity for $T(n) = T(\sqrt{n}) + 1$

Question

$$T(n) = T(\sqrt{n}) + 1$$

I am trying to find the time complexity of the given equation. I tried everything that I know but I could not find the answer.

What I've tried:

$k = lg(n)$ and $n=2^k$ -> $\sqrt{n} = 2^{k/2}$

Thanks in advance.

Answer 1

As you did, define $f(k)= T(2^k)$, which gives $f(k)= f(k/2) + 1$.

To solve this, define $g(i) = f(2^i)$, which gives $g(i) = g(i-1) + 1$.