How to find the complexity of T(n)=T(sqrt(n)) + 1 ?

Question

Please tell me the complete steps how to solve this problem.

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

Comments

https://gateoverflow.in/11211/how-to-find-the-complexity-of-t-n-t-sqrt-n-1

---

$T(2) = 1$

What I don’t understand is how can we make such approximations? How can we validate this is true?

Answer 1

By backward substitution, We may finally get like this,

k T(n^(1/2^k))+k-1

and given that T(2)=1

So, n^(1/2^k)=2

1/2^k . logn = 1

2^k = logn

K.log2 = log(log n)

So, our equation will be,

log(logn)[1]+log(log n) -1

O(log log n)

I followed this same procedure even in GATE, but I did very minor mistake and I wrote equation like this, "k T(n^(1/k))+k-1 and my whole answer changed to log(n) only which is technically right for me, but question wise not! Such a big mistake!!!!