Loop with break in Rust - Time & Space Complexity

Time Complexity: Loop with break

O(n)

Understanding Time Complexity

We want to understand how the time a loop takes changes when it can stop early using a break.

How does stopping early affect how long the code runs?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn find_first_even(numbers: &[i32]) -> Option {
    for &num in numbers {
        if num % 2 == 0 {
            return Some(num); // break early when even number found
        }
    }
    None
}
    

This code looks through a list to find the first even number and stops as soon as it finds one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the list elements one by one.
• How many times: Up to the first even number or the whole list if none found.

How Execution Grows With Input

Execution depends on where the first even number appears.

Input Size (n)	Approx. Operations
10	Between 1 and 10 checks
100	Between 1 and 100 checks
1000	Between 1 and 1000 checks

Pattern observation: The loop may stop early, so the work can be less than the list size, but in the worst case it checks every item.

Final Time Complexity

Time Complexity: O(n)

This means the time grows linearly with the size of the list in the worst case.

Common Mistake

[X] Wrong: "Because the loop can break early, the time complexity is always constant O(1)."

[OK] Correct: Sometimes the loop must check every item if no early break happens, so the worst case still grows with input size.

Interview Connect

Understanding how early breaks affect loops helps you explain code efficiency clearly and shows you think about best and worst cases.

Self-Check

"What if we changed the loop to always check every element without break? How would the time complexity change?"

Practice

1. What does the break keyword do inside a loop in Rust?

easy

A. It restarts the loop from the beginning.

B. It stops the loop immediately and exits it.

C. It skips the current iteration and continues the loop.

D. It pauses the loop until a condition is true.

Solution

1. Step 1: Understand the role of break in loops

   The break keyword is used to stop the loop immediately, no matter where it is in the loop.

2. Step 2: Compare with other loop controls

   Unlike continue which skips to the next iteration, break exits the loop completely.

3. Final Answer:

   It stops the loop immediately and exits it. -> Option B

4. Quick Check:

   break = stop loop [OK]

Hint: Remember: break means stop the loop now [OK]

Common Mistakes:

• Confusing break with continue
• Thinking break pauses instead of stops
• Assuming break restarts the loop

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

easy

A. break()

B. exit loop;

C. break;

D. stop;

Solution

1. Step 1: Recall Rust loop break syntax

   In Rust, to exit a loop, you simply write break; with a semicolon.

2. Step 2: Check other options for syntax errors

   break() is invalid because break is a keyword, not a function. exit loop; and stop; are not Rust keywords.

3. Final Answer:

   break; -> Option C

4. Quick Check:

   Correct break syntax = break; [OK]

Hint: Use break with semicolon to exit loops [OK]

Common Mistakes:

• Using break as a function call
• Writing break without semicolon
• Using non-existent keywords like exit or stop

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

let mut count = 0;
loop {
    count += 1;
    if count == 3 {
        break;
    }
    println!("{}", count);
}

medium

A. 1 2

B. 1 2 3

C. 3

D. 0 1 2

Solution

1. Step 1: Trace the loop iterations and print statements

   Loop starts with count = 0. Each loop adds 1 to count. When count reaches 3, break stops the loop. The print happens only if count is not 3.

2. Step 2: List printed values

   When count=1, prints 1; count=2, prints 2; count=3 triggers break before print, so 3 is not printed.

3. Final Answer:

   1 2 -> Option A

4. Quick Check:

   Print before break stops at 3, so output is 1 2 [OK]

Hint: Break stops before printing 3, so only 1 and 2 print [OK]

Common Mistakes:

• Assuming break prints the last value
• Counting from 0 instead of 1
• Ignoring that break stops loop before print

4. Identify the error in this Rust code snippet:

let mut i = 0;
loop {
    if i == 5 {
        break
    }
    println!("{}", i);
    i += 1;
}

medium

A. Missing semicolon after break

B. Variable i is not mutable

C. println! macro is used incorrectly

D. Loop condition is missing

Solution

1. Step 1: Check syntax around break statement

   In Rust, statements must end with a semicolon. The break statement here lacks a semicolon.

2. Step 2: Verify other parts of the code

   Variable i is mutable, println! is correctly used, and loop without condition is valid in Rust.

3. Final Answer:

   Missing semicolon after break -> Option A

4. Quick Check:

   break needs semicolon to avoid syntax error [OK]

Hint: Always put semicolon after break [OK]

Common Mistakes:

• Forgetting semicolon after break
• Thinking loop needs condition
• Misreading println! syntax

5. You want to sum numbers from 1 to 10 but stop adding when the sum reaches or exceeds 20. Which Rust code correctly uses a loop with break to do this?

hard

A. let mut sum = 0;
let mut n = 1;
loop {
sum += n;
if sum >= 20 {
break;
}
n += 1;
}
println!("{}", sum);

B. let mut sum = 0;
for n in 1..=10 {
sum += n;
if sum >= 20 {
break;
}
}
println!("{}", sum);

C. let mut sum = 0;
let mut n = 1;
while n <= 10 {
sum += n;
if sum >= 20 {
break;
}
n += 1;
}
println!("{}", sum);

D. let mut sum = 0;
let mut n = 1;
loop {
if n > 10 {
break;
}
sum += n;
if sum >= 20 {
break;
}
n += 1;
}
println!("{}", sum);

Solution

1. Step 1: Understand the problem requirements

   Sum numbers from 1 to 10, but stop if sum reaches or exceeds 20. Use loop with break.

2. Step 2: Analyze each option for correctness

   let mut sum = 0; let mut n = 1; loop { sum += n; if sum >= 20 { break; } n += 1; } println!("{}", sum); breaks after adding sum >= 20 but does not stop when n > 10, so it does not enforce the limit to 10. let mut sum = 0; for n in 1..=10 { sum += n; if sum >= 20 { break; } } println!("{}", sum); uses for loop, not loop. let mut sum = 0; let mut n = 1; while n <= 10 { sum += n; if sum >= 20 { break; } n += 1; } println!("{}", sum); uses while loop, not loop. let mut sum = 0; let mut n = 1; loop { if n > 10 { break; } sum += n; if sum >= 20 { break; } n += 1; } println!("{}", sum); correctly breaks if n > 10 or sum >= 20, stopping properly.

3. Final Answer:

   Correctly uses loop with break to stop at sum >= 20 or n > 10. -> Option D

4. Quick Check:

   let mut sum = 0; let mut n = 1; loop { if n > 10 { break; } sum += n; if sum >= 20 { break; } n += 1; } println!("{}", sum); [OK]

Hint: Check all break conditions to avoid infinite loops [OK]

Common Mistakes:

• Missing break for loop exit condition
• Using wrong loop type
• Not checking both sum and count limits