Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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)$
share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.