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

Accepted Answer

The correct answer is (B) Θ(n²log n). The outer loop runs from i=n/2 to i=n, i.e. Θ(n) iterations. The inner loop doubles j from 2 up to n, i.e. Θ(log n) iterations. Each inner-loop execution adds n/2 to k. Total value of k = (outer iterations) × (inner iterations) × (n/2) = Θ(n) × Θ(log n) × Θ(n) = Θ(n² log n).

Explanation