Why does this loop return a value that's O(n log log n) and not O(n log n)?

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;
}

The question is to decide which of the following most closely approximates the return value of the function fun1?

(A) n^3
(B) n (logn)^2
(C) nlogn
(D) nlog(logn)

This was the explanation which was given :

int fun1 (int n)
{
    int i, j, k, p, q = 0;

    // This loop runs T(n) time 

    for (i = 1; i < n; ++i)
    {
        p = 0;

        // This loop runs T(Log Log n) time
        for (j=n; j > 1; j=j/2)
            ++p;

        // This loop runs T(Log Log n) time
        for (k=1; k < p; k=k*2)
            ++q;

    }
    return q;
}

But Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount.

for (int i = 1; i <=n; i *= c) {
    // some O(1) expressions
}

for (int i = n; i > 0; i /= c) {
    // some O(1) expressions
}

But it was mentioned that the inner loops take Θ(Log Log n) time each , can anyone explain me the reason ar is the answer wrong?

Answer 1

This question is tricky - there is a difference between what the runtime of the code is and what the return value is.

The first loop's runtime is indeed O(log n), not O(log log n). I've reprinted it here:

p = 0;
for (j=n; j > 1; j=j/2)
  ++p;

On each iteration, the value of j drops by a factor of two. This means that the number of steps required for this loop to terminate is given by the minimum value of k such that n / 2^k ≤ 1. Solving, we see that k = O(log₂ n).

Notice that each iteration of this loop increases the value of p by one. This means that at the end of the loop, the value of p is Θ(log n). Consequently, this next loop does indeed run in time O(log log n):

for (k=1; k < p; k=k*2) ++q; }

The reason for this is that, using similar reasoning to the previous section, the runtime of this loop is Θ(log p), and since p = Θ(log n), this ends up being Θ(log log n).

However, the question is not asking what the runtime is. It's asking what the return value is. On each iteration, the value of q, which is what's ultimately returned, increases by Θ(log log n) because it's increased once per iteration of a loop that runs in time Θ(log log n). This means that the net value of q is Θ(n log log n). Therefore, although the algorithm runs in time O(n log n), it returns a value that's O(n log log n).

Hope this helps!