What is the time complexity of the following program?

Question

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

Answer 1

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

Answer 2

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