8

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)

ftsk33
  • 145
  • 1
  • 2
  • 4
  • 5
    [Verify it](http://www.wolframalpha.com/input/?i=T%28n%29+%3D+T%28n%5E%281%2F2%29%29+%2B+1) with Wolphram Alpha. – Ani Mar 03 '12 at 22:36

2 Answers2

18

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

Start unrolling the recursion: enter image description here.

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: enter image description here.

Solving it, you get enter image description here.

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.

Community
  • 1
  • 1
Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
9

hint: assume n = 22m or m = log2log2n, and you know 22m-1 * 22m-1 = 22m so, if you define S(m)=T(n) your S will be:

S(m) = S(m-1)+1 → S(m) = Θ(m) → S(m)=T(n) = Θ(log2log2n)

extend it for the general case.

In recursion like T(n) = T(n/2) + 1, in each iteration, we reduce the height of the tree to half. This leads to Θ(logn). In this case, however, we divide the input number by a power of two (not by two) so it turns out to be Θ(log log n ).

Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83