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!

Answer 2

Answer would be (D) O(n * log(log n)). The reason is described below :-

The first for loop encompasses other 2 for loops which are based on the values of j and k respectively. Also, j is getting halved from n, until it is greater than 1. So, p will be equal to greatest integer(log n). And, k is doubling till it equals p --- where p has been set from previous loop and would be equal to [log n], where [x] is equal to greatest integer of x.

So, the third loop will run for log (log n) time, so value of q will be log (log n). And, hence, both the inner loops being part of the outer for-loop which runs for n times.

Approximate value of q = n* log (log n)) = O(n log(log n)) .

Answer 3

The only thing wrong i see here concerns the second loop: for (j=n; j>1; j=j/2) You say in comments : This loop runs Θ(Log Log n) time

As I see it, this loop runs O(Log n) times

The running times for the first and third loops are correct (O(n) and O(Log Log n)).

EDIT: I agree with the previous answer. I did not notice that the question is about the return value, not the running time!