Loop labels in Rust - Time & Space Complexity

Time Complexity: Loop labels

O(n^2)

Understanding Time Complexity

When using loop labels in Rust, it's important to understand how the loops run and how many times the code inside repeats.

We want to know how the total work grows as the input size changes when loops are labeled and nested.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn labeled_loops(n: usize) {
    'outer: for i in 0..n {
        for j in 0..n {
            if i + j > n {
                break 'outer;
            }
        }
    }
}
    

This code uses a labeled loop to break out of the outer loop from inside the inner loop based on a condition.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops where the inner loop runs up to n times for each outer loop iteration.
• How many times: The outer loop runs approximately n times, but breaks early when i + j > n.

How Execution Grows With Input

As n grows, the loops run more times, but the break can stop the loops early.

Input Size (n)	Approx. Operations
10	55
100	5050
1000	500500

Pattern observation: The total work grows approximately quadratically with n (about n(n+1)/2 inner loop iterations).

Final Time Complexity

Time Complexity: O(n^2)

This means the work grows quadratically with the input size, due to the nested loops and the break condition limiting iterations but still resulting in roughly n²/2 operations.

Common Mistake

[X] Wrong: "Because of the break with the label, the loops only run once or a few times regardless of n."

[OK] Correct: The break only happens when a condition is met, so the loops can still run many times depending on input size.

Interview Connect

Understanding how labeled loops affect execution helps you explain loop control clearly and reason about performance in nested loops.

Self-Check

"What if the break condition was removed? How would the time complexity change?"