Competitive programming concept

Sequential Loops vs Nested Loop

Two Sequential Loops (One After Another)

for i in range(n):
    # Do something

for j in range(m):
    # Do something

• Time Complexity: O(n) + O(m) = O(n + m)
• The loops run one after another, so their complexities add up.
• If n ≈ m, the complexity simplifies to O(n).

Nested Loop

for i in range(n):
    for j in range(m):
        # Do something

• Time Complexity: O(n * m)
• The inner loop runs m times for each iteration of the outer loop, leading to a multiplicative complexity.
• If n ≈ m, it simplifies to O(n²).

Takeway

• Two sequential loops (O(n + m)) grow much slower than a nested loop (O(n * m)).
• If n and m are large, O(n * m) can become infeasible, while O(n + m) remains manageable.