TIL: Nested for/while loops can have O(N) time complexity in some cases (DSA for technical interviews)

The time complexity of a nested loop in Python depends on how the loops are structured. A while loop inside a for loop can still result in O(N) complexity in certain cases. In the first example, the while loop executes only once per iteration of the for loop and does constant-time work, resulting in O(N) complexity. In the second example, the while loop runs a constant number of times for each iteration of the for loop, again resulting in O(N) complexity. In the third example, the while loop's condition means that it will only increment a variable up to N in total, resulting in O(N) complexity. The key takeaway is that if the number of iterations of the inner while loop is independent of the for loop, 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. An example of O(N^2) complexity is when the while loop runs N times for each iteration of the for loop. In this case, the for loop runs N times and the while loop runs N times for each iteration of the for loop, resulting in O(N^2) complexity. The structure of the nested loops determines the overall time complexity.