For loop in Rust - Time & Space Complexity

Time Complexity: For loop

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run a for loop changes as the amount of data grows.

Specifically, how does the number of steps increase when the loop runs over more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for loop that visits each number in the list.
• How many times: Once for every number in the input list.

How Execution Grows With Input

As the list gets bigger, the loop runs more times, adding one step per item.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line as the list gets longer.

Common Mistake

[X] Wrong: "The loop runs a fixed number of times no matter the list size."

[OK] Correct: The loop actually runs once for each item, so bigger lists take more time.

Interview Connect

Understanding how loops grow with input size helps you explain your code clearly and shows you know how programs behave with more data.

Self-Check

"What if we replaced the for loop with two nested for loops over the same list? How would the time complexity change?"

Practice

1. What does a for loop do in Rust?

easy

A. Declares a variable

B. Defines a new function

C. Repeats actions for each item in a collection

D. Stops the program immediately

Solution

1. Step 1: Understand the purpose of a for loop

   A for loop runs code repeatedly for each item in a list or range.

2. Step 2: Match the description to the options

   Only Repeats actions for each item in a collection describes repeating actions over items in a collection.

3. Final Answer:

   Repeats actions for each item in a collection -> Option C

4. Quick Check:

   For loop = repeat over items [OK]

Hint: For loops repeat actions over collections [OK]

Common Mistakes:

• Confusing for loop with function definition
• Thinking for loop declares variables
• Believing for loop stops program

2. Which of these is the correct syntax for a for loop iterating over numbers 1 to 3 in Rust?

easy

A. for i = 1 to 3 { println!("{}", i); }

B. for i in 1..=3 { println!("{}", i); }

C. for (i in 1..3) println!("{}", i);

D. for i in range(1,3) { println!("{}", i); }

Solution

1. Step 1: Recall Rust for loop syntax

   Rust uses for variable in range { } with ranges like 1..=3 to include 3.

2. Step 2: Check each option

   for i in 1..=3 { println!("{}", i); } uses correct Rust syntax with inclusive range. Others use invalid syntax or functions not in Rust.

3. Final Answer:

   for i in 1..=3 { println!("{}", i); } -> Option B

4. Quick Check:

   Rust for loop uses in and ranges [OK]

Hint: Use 'for var in start..=end' for inclusive ranges [OK]

Common Mistakes:

• Using 'to' instead of 'in' keyword
• Using parentheses around loop variable
• Using Python or other language range syntax

3. What is the output of this Rust code?

let mut sum = 0;
for i in 1..4 {
    sum += i;
}
println!("{}", sum);

medium

A. 6

B. 10

C. 9

D. 7

Solution

1. Step 1: Identify the loop range and iterations

   The loop runs for i = 1, 2, 3 because 1..4 excludes 4.

2. Step 2: Calculate the sum of iterations

   sum = 0 + 1 + 2 + 3 = 6

3. Final Answer:

   6 -> Option A

4. Quick Check:

   1+2+3 = 6 [OK]

Hint: Remember range excludes the end number [OK]

Common Mistakes:

• Including 4 in the sum
• Starting sum at 1 instead of 0
• Confusing inclusive and exclusive ranges

4. Find the error in this Rust for loop code:

for i in 0..5
    println!("{}", i);
}

medium

A. Variable i is not declared

B. Range syntax is incorrect

C. println! macro is used incorrectly

D. Missing curly braces around loop body

Solution

1. Step 1: Check loop syntax

   Rust requires curly braces { } around the loop body if it has more than one statement or to be explicit.

2. Step 2: Identify the missing brace

   The code has a closing brace '}' without an opening brace '{' before println!().

3. Final Answer:

   Missing curly braces around loop body -> Option D

4. Quick Check:

   For loop body needs braces [OK]

Hint: Always use braces {} for loop bodies [OK]

Common Mistakes:

• Forgetting opening brace
• Assuming range syntax is wrong
• Thinking variable needs declaration outside loop

5. How can you use a for loop in Rust to print only even numbers from 2 to 10 inclusive?

hard

A. for i in 2..=10 { if i % 2 == 0 { println!("{}", i); } }

B. for i in 2..10 { if i % 2 = 0 { println!("{}", i); } }

C. for i in 2..=10 { if i / 2 == 0 { println!("{}", i); } }

D. for i in 2..=10 { if i % 2 != 0 { println!("{}", i); } }

Solution

1. Step 1: Understand the range and condition

   We want numbers from 2 to 10 inclusive, so use 2..=10. To print even numbers, check if remainder when divided by 2 is zero.

2. Step 2: Check each option's condition

   for i in 2..=10 { if i % 2 == 0 { println!("{}", i); } } correctly uses i % 2 == 0. for i in 2..10 { if i % 2 = 0 { println!("{}", i); } } uses assignment (=) instead of comparison (==). for i in 2..=10 { if i / 2 == 0 { println!("{}", i); } } uses division instead of modulo. for i in 2..=10 { if i % 2 != 0 { println!("{}", i); } } prints odd numbers.

3. Final Answer:

   for i in 2..=10 { if i % 2 == 0 { println!("{}", i); } } -> Option A

4. Quick Check:

   Use modulo == 0 for even check [OK]

Hint: Use 'if i % 2 == 0' inside for loop [OK]

Common Mistakes:

• Using '=' instead of '==' in condition
• Using division instead of modulo
• Printing odd numbers by mistake