What is the time complexity of the following program?

Problem Detail: 

Please help me calculate the time complexity of the following program.

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

Please explain.

There were four choices given.

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

Asked By : Vishnu Vivek

Answered By : Farhad Yusufali

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)$$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6901