This content originally appeared on DEV Community and was authored by Intent Engineering
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).
This content originally appeared on DEV Community and was authored by Intent Engineering
Intent Engineering | Sciencx (2024-10-23T01:31:45+00:00) TIL: Nested for/while loops can have O(N) time complexity in some cases (DSA for technical interviews). Retrieved from https://www.scien.cx/2024/10/23/til-nested-for-while-loops-can-have-on-time-complexity-in-some-cases-dsa-for-technical-interviews-2/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.