What is the time complexity of the following program?

int fun (int n) {
if (n <= 2)
return 1;
else
return fun(sqrt(n)) + n;
}


There were four choices given.

1. $\Theta(n^2)$
2. $\Theta(n \log n)$
3. $\Theta(\log n)$
4. $\Theta(\log \log n)$
-

The running time of the function on an input $n$ can be expressed as: $$T(n) = T(\sqrt n) + \mathcal{O}(1)$$

which implies the running time of the function and the number of recursions differ only by a constant.

The recursive chain ends when $n$ has been reduced to some value $k$, where $k \le 2$. The number of recursions, $r$, can be expressed as: $$k^{2^r} = n \implies r = \log_2 \log_k n$$

It follows that the running time is then:

$$\Theta(\log_2 \log_k n) = \Theta(\log \log n)$$

-
Hi Frahad, I too got the same result but through another method. But it's not given in the four options. Is it theta(log log n)?? If so, can you tell me why is that..? – Vishnu Vivek Nov 26 '12 at 4:14
And I still have another doubt. Why have you taken n as O(1). – Vishnu Vivek Nov 26 '12 at 5:37
Sorry, I missed the given options. The answer has been updated accordingly. Why do you believe $\mathcal{O}(1)$ should be $\mathcal{O}(n)$? Each recursion evaluates a condition, which takes constant time. – Farhad Yusufali Nov 26 '12 at 6:24

The time complexity here is proportional to the depth of the recursion tree. At each level, the square root of $n$ is taken. So how many times can the square root be taken before we get 2?

This can be calculated in the same way shown at this post.

$n = 2^{\log n}$

After taking the square root $k$ times, $n$ is equal to:

$2^{\log n/2^{k}}$

This is equal to 2 when:

$2^{\log n/2^k} = 2$

$\log n/2^k =1$

$\log n = 2^k$

$\log\log n = k$

So the time complexity is $\Theta(\log \log n)$.

-
Thanks @fgb, but still I have a doubt. From the program, the recurrence relation would be T(n) = T(sqrt(n)) + n. So doesn't the cost n have any significance. – Vishnu Vivek Nov 26 '12 at 5:36
You are are not doing anything with that last $n$. You are not calling the function on $n$. For example, if you would iterate some loop for $n$ steps, then the time-complexitiy for one call would have another $n$ - but you are not doing that, you are just adding $n$ to the result. – Nejc Nov 26 '12 at 9:36
@VISHNUVIVEK Do you want the time complexity of an algorithm that takes fun(n) steps, or do you want the time complexity of evaluating fun? – fgb Nov 26 '12 at 9:49