edited by
20,573 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

4 votes
4 votes
Ans c)

Here for outer loop we have n time run.

Then we have two inner loop and we have to find the complexity of each loop seperately. So, for the j loop we have logn complexity and for k loop we have loglogn complexity.

Now,

Total complexity is,

n( logn + loglogn).

So we get nlogn as answer
1 votes
1 votes

outermost loop i runs for 'n' times

second loop will run for logn times. and for each i, logn times = nlogn.

as second loop ran for logn times 'p' value is incremented upto logn.

hence innermost loop wil run for loglogn times. (because each time k = k*2 ... hence loop will run upto loglogn times)

Hence complexity will be O(nloglogn)

0 votes
0 votes

Take Example and solve

I took n to be 32 which is a power of 2

so got p=log(n) and q=log(logn)

 

See yourself

 

Answer:

Related questions