edited by
31,724 views
50 votes
50 votes

What is the $\text{time complexity}$ of the following recursive function?

int  DoSomething (int n) {
    if (n <= 2)
        return 1;
    else 
        return (DoSomething (floor (sqrt(n))) + n);
}
  1. $\Theta(n^2)$

  2. $\Theta(n \log_2n)$

  3. $\Theta(\log_2n)$

  4. $\Theta(\log_2\log_2n)$

edited by

8 Answers

4 votes
4 votes
The recurrence relation for this is following:

    $T(n)=T(n^{1/2})+n$ ......(1)

   put  $n=n^{1/2}$

  we get,

   $T(n^{1/2})=T(n^{1/4})+n^{1/2}$

  put this in (1), we get,

  $T(n)=T(n^{1/4})+n^{1/2}+n$

similarly,

  $T(n)=T(n^{1/2^{k}})+n^{1/2^{k-1}}+......+n$

This will stop when  $n^{1/2^{k}}=2$

Taking log of base 2 both side,we get

$1/2^{k} logn=log2

logn=2^{k}

log log n=k$

T(n)=O(log log n)
2 votes
2 votes
The program is not going to end when started with n > 2. A suitable base condition is required for the program to stop.

Time complexity for this program should be infinity.
0 votes
0 votes

This is my solution. Please let me know if there is any mistake.

0 votes
0 votes

soln

sir pls verify this solution @Arjun sir and @SACHIN MITTAL 1 sir

Answer:

Related questions

64 votes
64 votes
15 answers
1
Arjun asked Jul 6, 2016
36,697 views
Consider the following segment of C-code:int j, n; j = 1; while (j <= n) j = j * 2;The number of comparisons made in the execution of the loop for any $n 0$ is:$\lceil \...
64 votes
64 votes
8 answers
3
Kathleen asked Sep 21, 2014
26,380 views
In the following C function, let $n \geq m$.int gcd(n,m) { if (n%m == 0) return m; n = n%m; return gcd(m,n); }How many recursive calls are made by this function?$\Theta(\...