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?

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².

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.