Does time complexity change when two nested loops are re-written into a single loop?

Question

Is the time complexity of nested for, while, and if statements the same? Suppose a is given as an array of length n.

for _ in range(len(a)):
    for _ in range(len(a)):
        do_something

The for statement above will be O(n²).

i = 0
while i < len(a) * len(a):
    do_something
    i += 1

At first glance, the above loop can be thought of as O(n), but in the end I think that it is also O(n²).

Am I right?

Jeane

The number of loops is only related to the time complexity; it does not determine it. – Rexer

If in doubt, just count for some small n e.g. n=1,2,4,8,16. This should give you a good idea. – Brushwood

You seem to be asking if n*n = n^2. Why the uncertainty? – Natie

Try "for _ in range(len(a)): break". – Chubb

It depends on what n is, what is it? – Titulary

@ilkkachu and carstens doesn't "Suppose a is given as an array of length n" suffice to describe what n is? – Imbrication

@YuvalFilmus Good one, and the only somewhat interesting thing here. The upvotes/attention are ridiculous. – Hepta

"Does time complexity change" and "am I right" have opposite answers. The accepted answer says "yes" which is the wrong answer to the question in the title. – Asphyxia

"At first glance, the above loop can be thought of as O(n)" No, it can't. Being a single loop doesn't automatically make it O(n), first glance or otherwise. The loop i = 1; while i < len(a): i *= 2 is O(log n). The conditions of the loop matter. – Graecoroman

All the other answers are pretty good already, but I especially like @MrSmith42's answer, because depending on whether do_something is very fast, the overhead of the loop itself might matter, as loops in Python are relatively slow. However some quick testing indicates that it does not make a difference: Two nested loops of total length n2 are as slow as one of length n2. List comprehensions are way faster (again, if do_something is very fast). – Kenley

If the length of the array/list (len(a)) is n, then len(a) * len(a) is by definition n², and that's how many iterations the loop has and O(n²) is the complexity of the loop. The only way it can be thought of as O(n) is if you define n = len(a) * len(a), which would be non-standard and fairly confusing. Just because it looks similar to a loop that's O(n) doesn't make it O(n). – Drivel

Answer 1

Am I right?

Yes!

The double loop:

for _ in range(len(a)):
    for _ in range(len(a)):
        do_something

has a time complexity of O(n) * O(n) = O(n²) because each loop runs until n.

The single loop:

i = 0
while i < len(a) * len(a):
    do_something
    i += 1

has a time complexity of O(n * n) = O(n²), because the loop runs until i = n * n = n².

Imbrication

Answer 2

It is indeed still O(n^2). That is especially clear when you look at the loop which has len(a)*len(a) iterations.

You "flattened" the loops, but didn't change the amount of work, therefore it's just a "stylistic" change and has no impact on complexity.

Submicroscopic

Answer 3

We need to determine time complexity based on the number of operations being carried out by the constructs IMHO. It wouldn't be correct to generalize and say certain loops have a particular time complexity.

The time complexity of nested for loops generally would be O(n squared) - not always. Some involved nested for loops can also have just O(n) complexity. a single if statement would generally be O(1) since you are only doing basic comparisons. while loop could be anything depending on your exit condition.

while it could be useful to keep generalizations such as these in mind, we should always check the number of operations carried out to determine complexity.

Redness

Answer 4

Let me complement the other answers.

Does time complexity change when two nested loops are re-written into a single loop?

If they do the same work, complexity does not change. :-) If it does, then (at least) one of them is doing unnecessary work.

I apologize if going too far, but let me guess: Your thinking was:

• nested loops --> multiply, i.e. "n * n" (or "n * m"), where "n" is "the usual".
• single loop --> use "n" as-is, where "n" is "the usual". I am guessing in most exercises you have seen "n" for "size".

If that is your thinking, it just needs one adjustment: for the single loop, if "n" is the length of the loop, note that n = len(a) * len(a); if you change the meaning of "n" from one problem to the other you cannot compare (for the nested loops, n = len(a)). In any case, both codes have O(len(a) * len(a)) complexity, which is what you already found.

Omophagia

Answer 5

Yes, you're right, in general, though there is one small caveat worth mentioning.

In certain circumstances, such as accessing a disk or swapping pages into memory, it may make a difference - a big difference in some cases - whether reads are sequential within some sort of block, with an overhead incurred when accessing a different one. This can, sometimes, be very sensitive to the order of the loops in a ≥2D matrix.

By way of specific example, let's take a case where we have 128-byte pages of data, we can only hold one at a time, the latest page is cached, we want to make a 128x128 array and process each element, we don't care about the order of processing, but swapping pages incurs a delay 60x that of processing an element, and that processing takes 1s, so the delay is 60s == 1 minute. See why I picked x60? That's probably conservative if we're talking about, say, an OG 1x CD-ROM drive, the internet, lots of things, even memory when you have a "cache miss" though it may not be so dramatic.

My C is a bit rusty, and don't gripe about using magic numbers instead of constants, but you might typically do something along the lines of:

  uchar *buffer;
  int x, y;

  buffer = malloc(128 * 128);
  for(x=0 ; x<128 ; x++) {
    for(y=0 ; y<128 ; y++) {
      process_thingie(buffer[x*128 + y]);
    }
  }

so that takes 128*128 ~= 16k seconds ~= 4½ hours for the processing, and you're accessing each page one at a time, so that's another 128 minutes, call it a total of 6½ hours.

Instead, you could ignore the 2D aspect entirely - as in your question:

  for(i=0 ; i<128*128; i++)
    process_thingie(buffer[i]);

which gives the same results, 16k records, swapping each page in once, there you go no problem:

"Yes. You're right."

BUT. Let's say for whatever reasons, you get the inner/outer loops reversed:

  for(y=0 ; y<128 ; y++) {
    for(x=0 ; x<128 ; x++) {
      process_thingie(buffer[x*128 + y]);
    }
  }

(or just change x*128 + y to y*128 + x, same thing)

Well, that's very different. Each subsequent access has a stride of 128 bytes from the previous one, so we're obligated to swap in a new page on every iteration

That takes 128*128 ~= 16k seconds ~= 4½ hours for the processing, but with a swap every time, that's ALSO 16k minutes, for a total of about 11½ DAYS

technically it's still O(n²)... there's just another n hiding. Either implementation will scale at O(n²) relative to itself

CD-ROM game developers, for example, had to concern themselves with the physical placement of file on the disk (not quite the same but see this discussion of related issues in Myst),

Nowadays this is rarely such a concern, SSDs are crazy fast, and optimizing compilers (I think?) are usually smart enough to see what's up and swap the two loops (yeah), but they certainly can not catch everything, there may be some good reason you need to access the data in this order, you might need optimum performance for a certain task.

This does still come up in real life, programmers do sometimes need to be aware of it - I think this is one of the things game console developers still need to obsess over.

Perretta

Answer 6

Time Complexity denotes the Approx. upper bound time for any Program. Let calculate mathematically Time Complexity for both and check.

For For Loop:

for _ in range(len(a)):
    for _ in range(len(a)):
        do_something

The outer for loop is running O(len(a)) times and inner for loop is running O(len(a)).Which is running independently of outer for loop for O(len(a)) time.

take n=len(a)

We can derive the below Function:

F(n) = 1*n +2*n +3*n +4*n +..........+(n-1)*n+n*n (if n starts from 1)
F(n) = n(1+2++3+4+....+(n-1)+n)
F(n) = n*(n+(n+1)/2)  (Sum of n Natural Numbers)
F(n) = n^2 + 2*n + n/2 (After Solving the Equation)
F(n) = O(n^2)

For While loop

i = 0
while i < len(a) * len(a):
    do_something
    i += 1

We can directly derive that since it will run in:

len(a)*len(a) = n*n=O(n^2)

We can say that Both has approximately equal run time hence Complexity remains the same.

Cowberry