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 fun1?

Accepted Answer

The correct answer is (D) n log(log n). The outer loop runs Θ(n) times. For each outer iteration, the middle loop repeatedly halves j from n down past 1, running Θ(log n) times, so p ends up Θ(log n). The inner loop then repeatedly DOUBLES k from 1 while k<p, running Θ(log p) = Θ(log(log n)) times, incrementing q by that amount each outer iteration. Total q ≈ n · log(log n).

Explanation