What would be the time complexity for this nested loop?

Question

I have been having a debate with a couple of folks regarding the time complexity of this nested for loop algorithm:

for (i=1;i<=n;i*=2){
  for (j=1;j<=i;j++) {
    // some O(1) operation
  }
}

Now I believe that the complexity of the algo is O(NlogN), reason being that the complexity of outer loop is O(logN) and that of inner loop is O(N).

However, a couple of folks have calculated the complexity of this algo to be O(N) using some method involving AP/GP.

What's the complexity of this algo? If it actually is O(N), what's the intuition behind it?

Isn't exactly the same question as https://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop? — funnydman, Sep 05 '22 at 16:08
Updated the outer for loop condition, had incorrectly written it as `i++`. — Divyadeep Singh, Sep 05 '22 at 16:10
Does this answer your question? [Time complexity of nested for-loop](https://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop) — wohlstad, Sep 05 '22 at 16:15
@funnydman `i*=2` here is not the same as `i++` [there](https://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop). (OP updated code) — chux - Reinstate Monica, Sep 05 '22 at 16:17
hey no. the question is supposed to have `i*=2`, please ignore `i++`. — Divyadeep Singh, Sep 05 '22 at 16:23

trincot · Accepted Answer · 2022-09-05T18:23:21.593

The outer loop has a loop variable that is always a power of 2. The outer loop will make 1+⌊log_₂⌋ iterations.

Per iteration of the outer loop, the inner loop's body is executed as many times as the value of . So, in total, the number of executions of that inner body is expressed by the following sum:

2⁰ + 2¹ + ... + 2^{⌊log_₂⌋}

This is a geometric series. This can be written as a closed-form formula:

(1 − 2^{1 + ⌊log_₂⌋}) / (1 − 2)

Simplified:

2⋅2^{⌊log_₂⌋} − 1

And because the exponentiation compensates the logarithm, this is linear order of magnitude in terms of :

2⋅2^{⌊log_₂⌋} − 1 = O(2 − 1) = O()

Intuition

One key here is that the logarithm and exponentiation absorb each other.

To get a feel for it, note how the number of iterations of the outer loop does not change whether is 16, 17, 18, 19, 20, ... or even 31. In all these cases the outer loop executes 5 times, and the inner loop executes 1+2+4+8+16 = 31 times. Compared to when is 16, the number of outer iterations is only increased by one when doubles. The result is that the inner body execution also approximately doubles then... so those two "events" really go hand in hand... linearly.

See this table for different values of :

	number of inner body executions
1	1
2	3
3	3
4	7
5	7
6	7
7	7
8	15
9	15
10	15
11	15
12	15
13	15
14	15
15	15

What would be the time complexity for this nested loop?

1 Answers1

Intuition