The GATE Grind

GATE 2015 CS – Question 64

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice

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

  1. $n^3$
  2. $n(\log n)^2$
  3. $n \log n$
  4. $n \log(\log n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $n \log(\log n)$

Explanation

The first inner loop halves `j` from $n$ down to 1, so `p` ends up as about $\log n$. The second inner loop doubles `k` up to `p`, so it runs about $\log p = \log \log n$ times. The outer loop repeats this $n$ times, so `q` is about $n \log(\log n)$.