Labeled statements for nested loops in Swift - Time & Space Complexity

Time Complexity: Labeled statements for nested loops

O(n)

Understanding Time Complexity

When using labeled statements in nested loops, it helps control which loop to break or continue. We want to understand how this affects the total work the program does as input grows.

How does the number of steps change when loops are nested and labeled?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

outerLoop: for i in 1...n {
    for j in 1...n {
        if i * j > n {
            break outerLoop
        }
        print(i, j)
    }
}
    

This code uses a labeled break to exit the outer loop early when a condition is met inside the inner loop.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The nested loops where the inner loop runs for each outer loop iteration.
• How many times: The inner loop runs fewer times as the product i * j grows, but in the worst case, it can run up to n times for each i.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	About 10 to 20 operations before break
100	About 100 to 200 operations before break
1000	About 1000 to 2000 operations before break

Pattern observation: The total steps grow roughly proportional to n, not n squared, because the break stops loops early.

Final Time Complexity

Time Complexity: O(n)

This means the total work grows linearly with the input size because the labeled break stops the loops early.

Common Mistake

[X] Wrong: "Nested loops always mean the program runs in n squared time."

[OK] Correct: Because the labeled break can stop loops early, the total steps can be much less than n squared.

Interview Connect

Understanding how labeled breaks affect loops shows you can reason about code flow and efficiency, a skill useful in many programming tasks.

Self-Check

"What if we replaced the labeled break with a simple break inside the inner loop? How would the time complexity change?"