algorithm - Reccurrence T(n) = T(n^(1/2)) + 1

Question

I've been looking at this reccurrence and wanted to check if I was taking the right approach.

T(n) = T(n^(1/2)) + 1
= T(n^(1/4)) + 1 + 1
= T(n^(1/8)) + 1 + 1 + 1
...
= 1 + 1 + 1 + ... + 1 (a total of rad n times)
= n^(1/2)

So the answer would come to theta bound of n^(1/2)

Answer 1

Here is how you can find the answer without any hints, just by using math.

Start unrolling the recursion: .

The recursion will at some point stop, so we have to find a reasonable stopping point. Trying 0, 1, 2, you can see that 2 looks good, because you can easily solve the equation: .

Solving it, you get .

So the recursion will continue log(log(n)) times and this is your time complexity.

P.S. a little bit harder recurrence was solved here.