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?"

Practice

1. What is the main purpose of using loop labels in Rust?

easy

A. To create infinite loops without conditions.

B. To declare variables inside loops.

C. To name loops so you can break or continue specific loops inside nested loops.

D. To automatically parallelize loops for performance.

Solution

1. Step 1: Understand loop labels concept

   Loop labels let you assign a name to a loop, especially useful when loops are nested.

2. Step 2: Identify the use of labels

   Labels allow you to break or continue a specific loop by referring to its name, avoiding ambiguity.

3. Final Answer:

   To name loops so you can break or continue specific loops inside nested loops. -> Option C

4. Quick Check:

   Loop labels = control nested loops [OK]

Hint: Labels name loops for clear break/continue control [OK]

Common Mistakes:

• Thinking labels create infinite loops
• Confusing labels with variable declarations
• Assuming labels optimize performance automatically

2. Which of the following is the correct syntax to label a loop in Rust?

easy

A. label: loop { /* code */ }

B. loop label { /* code */ }

C. loop: label { /* code */ }

D. loop { label: /* code */ }

Solution

1. Step 1: Recall Rust loop label syntax

   In Rust, a loop label is written as 'label: before the loop keyword.

2. Step 2: Match syntax options

   label: loop { /* code */ } correctly places the label before the loop with a colon, e.g., 'label: loop {}.

3. Final Answer:

   label: loop { /* code */ } -> Option A

4. Quick Check:

   Label syntax = 'label: loop' [OK]

Hint: Labels come before loop with a colon [OK]

Common Mistakes:

• Placing label after loop keyword
• Using colon after loop instead of label
• Putting label inside loop body

3. What will be the output of this Rust code?

fn main() {
    let mut count = 0;
    'outer: loop {
        println!("Outer loop: {}", count);
        let mut inner_count = 10;
        loop {
            println!("  Inner loop: {}", inner_count);
            if inner_count == 9 {
                break 'outer;
            }
            inner_count -= 1;
        }
        count += 1;
    }
    println!("Done");
}

medium

A. Outer loop: 0
Inner loop: 10
Inner loop: 9
Inner loop: 8
Done

B. Outer loop: 0
Inner loop: 10
Done

C. Infinite loop with no output

D. Outer loop: 0
Inner loop: 10
Inner loop: 9
Done

Solution

1. Step 1: Trace outer loop first iteration

   count starts at 0, prints "Outer loop: 0". Then inner loop starts with inner_count = 10.

2. Step 2: Trace inner loop and break condition

   Inner loop prints 10, then 9. When inner_count == 9, it breaks the 'outer loop, exiting both loops.

3. Final Answer:

   Outer loop: 0 Inner loop: 10 Inner loop: 9 Done -> Option D

4. Quick Check:

   Break 'outer stops both loops at inner_count 9 [OK]

Hint: Break 'label exits named loop immediately [OK]

Common Mistakes:

• Thinking break only exits inner loop
• Missing that break 'outer exits both loops
• Assuming loops continue infinitely

4. Identify the error in this Rust code using loop labels:

fn main() {
    'start: loop {
        loop {
            break start;
        }
    }
}

medium

A. Missing apostrophe before label name in break statement.

B. Label 'start' is not defined before use.

C. Cannot break a labeled loop from an inner loop.

D. Syntax error: break statements cannot have labels.

Solution

1. Step 1: Check break statement syntax

   In Rust, breaking a labeled loop requires the label with an apostrophe, e.g., break 'start;.

2. Step 2: Identify the missing apostrophe

   The code uses break start; missing the apostrophe before the label name, causing a syntax error.

3. Final Answer:

   Missing apostrophe before label name in break statement. -> Option A

4. Quick Check:

   Label break syntax = break 'label [OK]

Hint: Always prefix label with apostrophe in break/continue [OK]

Common Mistakes:

• Omitting apostrophe in break label
• Assuming labels are variables
• Thinking break can't target outer loops

5. Given nested loops labeled 'outer and 'inner, how can you skip the current iteration of the outer loop from inside the inner loop?

hard

A. Use break 'inner; inside the inner loop.

B. Use continue 'outer; inside the inner loop.

C. Use continue; without label inside the inner loop.

D. Use break 'outer; inside the inner loop.

Solution

1. Step 1: Understand continue with labels

   Using continue 'outer; skips the current iteration of the loop labeled 'outer, jumping to its next iteration.

2. Step 2: Differentiate break and continue

   break exits the loop, while continue skips to the next iteration. To skip outer loop iteration from inner loop, use continue 'outer;.

3. Final Answer:

   Use continue 'outer; inside the inner loop. -> Option B

4. Quick Check:

   continue 'label skips that loop iteration [OK]

Hint: Use continue 'label to skip outer loop iteration [OK]

Common Mistakes:

• Using break instead of continue to skip iteration
• Omitting label in continue statement
• Confusing break and continue effects