Question

Consider the following function:
int unknown (int n)
{
int i, j, k =0;
for (i = n/2; j < = 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^3$log n)
• C. $\Theta$($n^3$)
• D. $\Theta$($n^2$log n)

Answer 1

The correct option is D $\Theta$($n^2$log n)

Outer loop execute for $\frac{n}{2}$ + 1 iterations. Inner loop execute for $lo{g}_2$n iterations. In every iteration of inner loop n/2 is added to k.
Return value = $\frac{n}{2}$ $\times$ number of outer loops $\times$ number of inner loops

= $\frac{n}{2}$ $\times$ ($\frac{n}{2}$ + 1)(log n)
= O($n^2$ log n)