GATE CSE 2015 Set 1 | Question: 31

Question

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}$?

• A. $n^3$
• B. $n(\log n)^2$
• C. $n \log n$
• D. $n \log(\log n)$

Comments

What the hell, J and K loops are not nested. I got so confused, as in GO book this question got split between pages and me like an idiot applying stirling approximation.

Anyways if they were nested then the answer would've been:

$O(n\hspace{1mm}log\hspace{1mm}n\hspace{1mm}loglog\hspace{1mm}n)$

Answer 1

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

Comments

most closely approximates the return value of the function fun1 . try with all other option they give worst approximation.

---

The complexity would be O(n)* (O( logn ) + O( lglgn ))

so the complexity of the program is O(nlogn)

But the return value of the program is O(nlglgn). Correct me if wrong .

---

if p=0 at starting not given then p will be nlogn at last loop, and k loop will run for loglogn+log(2logn)+log(3logn)+..log(nlogn) times, am i right? return val would be nlogn then?

Answer 2

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)

Comments

time complexity of this program is O(n log n)  and returning value is O(n log log n)

---

@Dexter

return value taking all values of i,j,k, as k is depend on p.

But, in time complexity, we are only concern with minimum time.

So, time taken by j loop will not matter here.

So, time complexity will be O(n log n).

explained Arjun Sir in previous command. rt?

---

time complexity = n(logn + loglogn) = nlogn ???

Answer 3

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

Comments

Can you please explain more how you get this q=1∗1+2∗2+4∗3+8∗4+16∗5+32∗6+....n∗logn for single loop of i.

---

q value of 2nd assumption is wrong, it should be ..

O(n^2 log(logn)). .. approximately

Answer 4

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