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

algorithm math big-o analysis recurrence
ftsk33 picture ftsk33 · Mar 3, 2012 · Viewed 26.5k times · Source

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

Salvador Dali picture Salvador Dali · Dec 14, 2015

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.

Related questions

Is log(n!) = Θ(n·log(n))?

I am to show that log(n!) = Θ(n·log(n)). A hint was given that I should show the upper bound with nn and show the lower bound with (n/2)(n/2). This does not seem all that intuitive to me. …

Read More
What is the big-O of the function (log n)^k

What is the big-O complexity of the function (log n)k for any k?

Read More
Computing set intersection in linear time?

Is there an algorithm that, given two sets, computes their intersection in linear time? I can run two for loops to check all pairs of elements, recording elements that I find in both of the sets. However, the runninng time …

Read More