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

I meant an arbitrary constant like Q as there is no relation between j,k and n so you don't know how many times it would run — Naman Sood
– Naman Sood, Commented Dec 18, 2018 at 7:42

templatetypedef · Accepted Answer · 2018-12-18 07:46:42Z

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.

linuxfan says Reinstate Monica · Accepted Answer · 2018-12-18 08:01:12Z

2

In your code there are 3 nested loops.

First loop runs n/2 times which is almost equivalent to n while calculating complexity.
Second loop runs logn times.
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).

edited Dec 18, 2018 at 8:01

linuxfan says Reinstate Monica

4,7282 gold badges23 silver badges42 bronze badges

answered Dec 18, 2018 at 7:50

BishalG

1,43413 silver badges27 bronze badges

Comments

gsamaras · Accepted Answer · 2018-12-18 07:49:26Z

1

First loop takes: n/2

Second loop: log(n)

Third loop: log(n)

Notice that because the step of the inner loops is multiplied by two, their respective counters grow exponentially, reaching n in a log(n), in terms of time complexity.

Then, also notice that constants like 1/2 can safely be ignored in that case, which results in O(n * log(n) *log(n)), thus:

O(nlog²n)

edited Dec 18, 2018 at 7:49

answered Dec 18, 2018 at 7:45

gsamaras

73.7k50 gold badges210 silver badges330 bronze badges

Collectives™ on Stack Overflow

Time complexity of nested for loop

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related