edited by
20,556 views
57 votes
57 votes

Consider the following C function.

int fun1 (int n) { 
     int i, j, k, p, q = 0; 
     for (i = 1; i < n; ++i) 
     {
        p = 0; 
       for (j = n; j > 1; j = j/2) 
           ++p;  
       for (k = 1; k < p; k = k * 2) 
           ++q;
     } 
     return q;
}

Which one of the following most closely approximates the return value of the function $\text{fun1}$?

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

7 Answers

Best answer
92 votes
92 votes

$i$ loop is executing $n$ times, $j$ loop is executing $\log\ n$ times for each $i$, and so value of $p$ is $\log n$ when $j$ loop exits for all iterations of the $i$ loop.

$k$ loop is executing $\log\ p$ times, which is $\log\log\ n$ times for each iteration of $i$. In each of these iteration, $q$ is incremented. So, over all iterations of $i$, $q$ will be incremented $n\log\log\ n$ times.

So, D choice. 

edited by
43 votes
43 votes

Here for loop of i is executing n times

j is executing log n time

Now, k is incrementing log p times

what that p is?

p is no of time j executes

j executes log n times

So, value of p is also log n

So, from here k executes log log n times

So, return value of fun1 is n log log n

Complexity of program O(n log n)

11 votes
11 votes
int fun1 (int n) { 
     int i, j, k, p, q = 0; 
     for (i = 1; i < n; ++i) {
        p = 0; 
       for (j = n; j > 1; j = j/2) 
           ++p;   //this "for loop" is ending here
      for (k = 1; k < p; k = k * 2) 
           ++q;
     } 
     return q;
}

p is incrementing $logn$ times hence $p=logn$

and after the loop ends, inner "for loop" is also computing $logp$ i.e. $log(logn)$ times.

so final value of $q=n*O(log(logn))$ 

But what if program is like this:-

int fun1 (int n) { 
     int i, j, k, p, q = 0; 
     for (i = 1; i < n; ++i) {
        p = 0; 
       for (j = n; j > 1; j = j/2) {
           p++; //here  loop is not ending here  
      for (k = 1; k < p; k = k * 2) 
           ++q;
     } 
     }
     return q;
}

then for one single value of $i$ value of $q$ will be like this

$q=1*1+2*2+4*3+8*4+16*5+32*6+....n*logn$

$q=\sum_{i=1}^{logn}$$2^{i}*i$

$q=n+O(nlogn)$

after every loop we are resetting the value of $p=0$

So, final value of $q=n^{2}*O(logn)$

7 votes
7 votes
int fun1 (int n) {
     int i, j, k, p, q = 0;
     for (i = 1; i < n; ++i)    // O(n)
     {
        p = 0;
       for (j = n; j > 1; j = j/2)     // O(logn)
           ++p; 
       for (k = 1; k < p; k = k * 2)     // O(logp) = O(loglogn)
           ++q;
     }
     return q;
}

The return value, ie, q gets the value approximately equal to $loglogn$ for each iteration of the outer-loop.

Hence, overall, q will get the value $nloglogn$

 

Option D


Note that the second and third for-loops aren't nested with respect to each other.

They coexist as inner loops with the first loop being the outer loop.

So, time complexity would be $O(n*(logn+loglogn))=O(nlogn)$ and not $O(n*logn*loglogn)$

edited by
Answer:

Related questions