Question regarding time complexity of nested for loops

Question

Let n be a power of 2.

int sum = 0;
for (int i = 1; i < n; i *= 2)
   for (int j = 0; j < n; j++)
      sum += 1

Is the time complexity O(N) or O(nlogn). Thanks!

The time complexity of a nested loop is normally `O(n^2)`. Possible duplicate of this?: https://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop — The Coding Fox, Feb 28 '22 at 13:58
O(NlogN) innit. Outer loop is O(log N) since if you double N then you get one extra iteration. Inner loop is O(N) since if you double n then you double the number of iterations. The fact that `n` is constrained to be a power of 2 is a red herring. — Bathsheba, Feb 28 '22 at 13:59
With optimization turn on, less, (as second loop can easily be replaced by `sum += n;`) ;-) — Jarod42, Feb 28 '22 at 14:00
@Jarod42 And a talented mathematician will give you an O(1) solution. — Bathsheba, Feb 28 '22 at 14:01
The sum does not matter in this case. It is just an example to find the time complexity. Thanks! @Jarod42 — shillos, Feb 28 '22 at 14:02
But note that a good optimising compiler will adopt @Jarod42 's optimisation. — Bathsheba, Feb 28 '22 at 14:02
@Bathsheba I am 100% sure that I and you are correct. It is quite obvious that it is nlogn right? — shillos, Feb 28 '22 at 14:04
@shillos: It is to me, yes. Remember that Big O is all about the asymptotic behaviour. Informally then, if you have a large value of `n` in your head, think about what happens if you double it. — Bathsheba, Feb 28 '22 at 14:05
@Bathsheba Sure! I have even done the calculation using sum notation and still gives nlogn. It is obvious. Should I argue about it? — shillos, Feb 28 '22 at 14:08

score 1 · Accepted Answer · answered Feb 28 '22 at 16:41

So first of all, it isn't necessary to know what kind of number is n is, since the asymptotic complexity is dependent of any arbitrary n(as long it is a positive integer).

We also know that the inner loop will do n iterations, hence we can denote the inner loop the time complexity of O(n).

About the outer loop. We know that at each iteration we double the values of i. Since i isn't zero at the initialization, it will for sure be increased by it doubling it. Since we are actually doubling i at each iteration we know that we reach n with exponentially increasingly larger iteration steps(for i=1, 2, 4, 8, 16, 32, 64, 128...). Hence the number of steps to reach n will become smaller while we get closer to it. Now knowing this we see that we are doing at most log(n) iterations to reach n.

Why? -> Well this might be mathematically informal, but I hope this is fine. In order to compute the number of iterations, one has to solve this equation: 2^x = n, where x is the number of iteration. We can see this basically by the explanation above. At each iteration step we double i until we reach n. The solution for x is than: x < log_2(n)

Hence the time complexity of the outer loop is O(log(n)).

Know this, one can simply multiply the complexities to O(log(n)n).

Question regarding time complexity of nested for loops

1 Answers1