GATE Overflow Test Series | Mock GATE | Test 1 | Question: 46

Question

Consider the following C function.

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

Which one of the following is the approximate value returned by the above function?

• A. $\Theta(n)$
• B. $\Theta(2^n)$
• C. $\Theta(2^{(n \log n))}$
• D. $\Theta(\log n)$

Comments

Won’t ans be $n^2$ without semicolon? Because at each iteration, we have the value of p as $log_{2}(n)$ and q as $2^{log_{2}(n)}$ which is just $n$...

---

“q=q<<=1;” means “q=q=<<1;“

“q<<=1;”means “q=q<<1;”

right?

---

@shashankrustagi no

Answer 1

In second inner loop there is semicolon after for loop statement. Hence the value of $q$ will double according to outer loop only i.e $n$ times. So, final value of $q$ becomes $2^n$.

Option B.