Loop construct in Rust - Time & Space Complexity

Time Complexity: Loop construct

O(n)

Understanding Time Complexity

Loops are a basic way to repeat actions in code. Understanding how loops affect time helps us know how fast or slow a program runs as input grows.

We want to see how the number of steps changes when the loop runs more times.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn sum_numbers(numbers: &[i32]) -> i32 {
    let mut total = 0;
    for &num in numbers {
        total += num;
    }
    total
}
    

This code adds up all numbers in a list and returns the total sum.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each number to the total inside the for-loop.
• How many times: Once for every number in the input list.

How Execution Grows With Input

Each number in the list causes one addition. So, if the list gets bigger, the work grows in the same way.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

Pattern observation: The number of steps grows directly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the number of items.

Common Mistake

[X] Wrong: "The loop runs only once, so time is constant."

[OK] Correct: The loop runs once for each item, so more items mean more work, not just one step.

Interview Connect

Knowing how loops affect time helps you explain your code clearly and shows you understand how programs grow with input size.

Self-Check

"What if we used two nested loops over the same list? How would the time complexity change?"

Practice

1. What does the loop keyword do in Rust?

easy

A. It runs the loop a fixed number of times.

B. It creates an infinite loop that runs until break is called.

C. It runs the loop only once.

D. It creates a loop that runs only if a condition is true.

Solution

1. Step 1: Understand the loop keyword

   The loop keyword in Rust creates a loop that repeats forever unless stopped.

2. Step 2: Identify how to stop the loop

   To stop a loop, you must use break inside it; otherwise, it runs infinitely.

3. Final Answer:

   It creates an infinite loop that runs until break is called. -> Option B

4. Quick Check:

   loop = infinite loop until break [OK]

Hint: Remember: loop runs forever unless broken [OK]

Common Mistakes:

• Thinking loop runs a fixed number of times
• Confusing loop with for or while
• Assuming loop stops automatically

2. Which of the following is the correct syntax to create an infinite loop in Rust?

easy

A. loop { println!("Hello"); }

B. while True { println!("Hello"); }

C. for i in 0.. { println!("Hello"); }

D. repeat { println!("Hello"); }

Solution

1. Step 1: Check Rust syntax for infinite loops

   Rust uses the keyword loop to create an infinite loop.

2. Step 2: Verify each option

   while True { println!("Hello"); } uses while True which is invalid syntax in Rust. for i in 0.. { println!("Hello"); } uses for with an infinite range, but 0.. is not valid without an end. repeat { println!("Hello"); } uses repeat which does not exist in Rust. loop { println!("Hello"); } correctly uses loop.

3. Final Answer:

   loop { println!("Hello"); } -> Option A

4. Quick Check:

   Correct infinite loop syntax = loop [OK]

Hint: Use loop keyword for infinite loops in Rust [OK]

Common Mistakes:

• Using while True which is invalid in Rust
• Trying to use repeat which doesn't exist
• Using for without a proper range

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. 0 1 2

C. 1 2 3

D. No output (infinite loop)

Solution

1. Step 1: Trace the loop iterations

   Initially, count = 0. In the first loop, count becomes 1, which is printed. Then count becomes 2 and printed. When count becomes 3, the loop breaks before printing.

2. Step 2: List printed values

   Only 1 and 2 are printed before the break stops the loop.

3. Final Answer:

   1 2 -> Option A

4. Quick Check:

   Loop prints until count == 3, so prints 1 and 2 [OK]

Hint: Check when break happens before printing [OK]

Common Mistakes:

• Printing count after break condition
• Starting count from 0 but expecting 0 to print
• Assuming infinite loop without break

4. Identify the error in this Rust loop code:

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

medium

A. 'println!' macro syntax is wrong.

B. Missing semicolon after 'break'.

C. 'loop' keyword is used incorrectly.

D. Variable 'i' is not incremented, causing an infinite loop.

Solution

1. Step 1: Check loop control variable

   The variable i is initialized but never changed inside the loop.

2. Step 2: Understand loop behavior

   Since i never increments, i == 5 is never true, so break is never reached, causing an infinite loop.

3. Final Answer:

   Variable 'i' is not incremented, causing an infinite loop. -> Option D

4. Quick Check:

   Loop needs variable increment to reach break [OK]

Hint: Always update loop variables to avoid infinite loops [OK]

Common Mistakes:

• Forgetting to increment loop variable
• Assuming break works without condition change
• Misunderstanding loop syntax

5. How can you use a loop to sum numbers from 1 to 5 in Rust?

hard

A. Use loop with a counter but never update sum.

B. Use loop without break and add numbers forever.

C. Use a loop with a counter and break when counter > 5, adding each to sum.

D. Use loop with a counter but break immediately without adding.

Solution

1. Step 1: Plan the loop with counter and sum

   Initialize a counter at 1 and sum at 0. Use loop to add counter to sum.

2. Step 2: Use break to stop after 5

   Increment counter each loop. When counter > 5, use break to exit loop.

3. Step 3: Result is sum of 1 to 5

   This method correctly sums numbers 1+2+3+4+5 = 15.

4. Final Answer:

   Use a loop with a counter and break when counter > 5, adding each to sum. -> Option C

5. Quick Check:

   Loop + counter + break = sum 1 to 5 [OK]

Hint: Increment counter and break after limit to sum [OK]

Common Mistakes:

• Not breaking loop causing infinite sum
• Not incrementing counter
• Not adding counter to sum