TIL: nested for/while loop(s) is O(N)?! for coding interview

In Python (and in general algorithm analysis), the time complexity of a nested loop depends on how the loops are structured. If you have a while loop inside a for loop, the overall complexity can still be O(N) in certain cases due to how the loops interact.

Here are a few examples that explain why a while loop inside a for loop can still result in O(N) complexity:

Example 1: Constant-Time Inner While Loop

for i in range(N):
    while some_condition:
        # Do constant-time work (O(1))
        break

In this case:

• The for loop runs N times.
• The while loop executes only once per iteration of the for loop because of the break statement.
• The work done inside the while loop is constant time, so the complexity for each for loop iteration is O(1).
• Therefore, the overall complexity is O(N)×O(1)=O(N).

Example 2: Inner While Loop's Work Depends on the Outer Loop

for i in range(N):
    while i < 5:
        # Do constant-time work (O(1))
        i += 1

In this case:

• The for loop runs N times.
• The while loop runs only a constant number of times (at most 5) for each iteration of the for loop.
• Again, the complexity remains O(N).

Example 3: While Loop Consumes the Range in Total

i = 0
for _ in range(N):
    while i < N:
        # Do constant-time work (O(1))
        i += 1

In this case:

• The for loop runs N times.
• The while loop's condition (i < N) means that i will only increase up to N in total, across all iterations.
• Even though it's nested, the while loop will increment i a total of N times overall, not N×N.
• Therefore, the complexity is still O(N).

Key Takeaway:
If the number of iterations of the inner while loop is independent of the for loop (or if the total work done by the while loop across the for iterations is bounded by N), then the combined complexity can remain O(N).

The complexity would only be O(N^2) if the inner while loop ran N times for each iteration of the outer for loop. For example,

for i in range(N):
    j = 0
    while j < N:
        # Do constant-time work (O(1))
        j += 1

• The for loop runs N times.
• The while loop runs N times for each iteration of the for loop. Therefore, the complexity is O(N^2).