Time complexity of nested for loop

Question

What would be the time complexity of this following block of code void function(int n).

My attempt was that the outermost loop would run n/2 times and the inner two would run 2^q times. Then I equated 2^q with n and got q as 1/2(log n) with base 2. Multiplying the time complexities I get my value as O(nlog(n)) while the answer is O(nlog^2(n)).

void function(int n) { 
    int count = 0; 
    for (int i=n/2; i<=n; i++)  
        for (int j=1; j<=n; j = 2 * j)
            for (int k=1; k<=n; k = k * 2) 
                count++; 
} 

Answer 1

Time to apply the golden rule of understanding loop nests:

When in doubt, work inside out!

Let’s start with the original loop nest:

    for (int i=n/2; i<=n; i++)  
        for (int j=1; j<=n; j = 2 * j)
            for (int k=1; k<=n; k = k * 2) 
                count++; 

That inner loop will run Θ(log n) times, since after m iterations of the loop we see that k = 2^m and we stop when k ≥ n = 2^{lg n}. So let’s replace that inner loop with this simpler expression:

    for (int i=n/2; i<=n; i++)  
        for (int j=1; j<=n; j = 2 * j)
            do Theta(log n) work;

Now, look at the innermost remaining loop. With exactly the same reasoning as before we see that this loop runs Θ(log n) times as well. Since we do Θ(log n) iterations that each do Θ(log n) work, we see that this loop can be replaced with this simpler one:

    for (int i=n/2; i<=n; i++)
        do Theta(log^2 n) work;

And here that outer loop runs Θ(n) times, so the overall runtime is Θ(n log² n).

I think that, based on what you said in your question, you had the right insights but just forgot to multiply in two copies of the log term, one for each of the two inner loops.

Answer 2

In your code there are 3 nested loops.

1. First loop runs n/2 times which is almost equivalent to n while calculating complexity.
2. Second loop runs logn times.
3. Third loop runs logn times.

So, finally the time complexity will be O( n * logn * logn ) == O(nlog^2n).
Now, one may wonder how the run time complexity of the two inner loops is logn. This can be generalized as follows:
Since we are multiplying by 2 in each iteration, we need value of q such that:
n = 2 ^ q.

Taking log base 2 on both sides,

log2 n = log2 (2^q)
log2 n = q log2(2)
log2 n = q * 1 [ since, log2(2) is 1 ]

So, q is equal to logn.
So, overall time complexity is: O(n*log^2n).