GATE CSE 2013 | Question: 31

Question

Consider the following function:

int unknown(int n){ 

int i, j, k=0; 
for (i=n/2; i<=n; i++) 
    for (j=2; j<=n; j=j*2) 
        k = k + n/2; 
 return (k); 

} 

The return value of the function is

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

Answer 1

The i loop will run for $n/2$ times while the j loop will run for $log n$ times .
the value of k is incremented by n/2 everytime so the correct answer will be $(n^{2} log n) /4$ which is assymptotically  ϴ$(n^{2} log n)$