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.

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

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.

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.

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.