Iterating over collections in Rust - Time & Space Complexity

Time Complexity: Iterating over collections

O(n)

Understanding Time Complexity

When we go through items in a collection one by one, it takes time. We want to know how this time grows as the collection gets bigger.

The question is: How does the work change when the list has 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 numbers in a list and returns the total sum.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each number in the list.
• How many times: Once for every item in the list.

How Execution Grows With Input

As the list gets bigger, the time to add all numbers grows in a straight line.

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

Pattern observation: Doubling the list size doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time grows directly with the number of items in the list.

Common Mistake

[X] Wrong: "Looping over a list always takes the same time no matter how big it is."

[OK] Correct: The bigger the list, the more items to check, so it takes more time.

Interview Connect

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

Self-Check

"What if we used two nested loops to compare every item with every other item? How would the time complexity change?"

Practice

1. What does the following Rust code do?

let numbers = [1, 2, 3];
for num in numbers {
    println!("{}", num);
}

easy

A. Causes a compile error because arrays can't be iterated

B. Prints each number in the array on a new line

C. Prints the whole array as one line

D. Prints the length of the array

Solution

1. Step 1: Understand the for loop over an array

   The for loop visits each element in the array named 'numbers'.

2. Step 2: Action inside the loop

   Each element is printed on its own line using println! macro.

3. Final Answer:

   Prints each number in the array on a new line -> Option B

4. Quick Check:

   for loop over array prints elements one by one [OK]

Hint: For loops visit each item in order [OK]

Common Mistakes:

• Thinking arrays can't be iterated
• Expecting the whole array printed at once
• Confusing print! with println!

2. Which of these is the correct syntax to iterate over a vector named v in Rust?

easy

A. for i in v { println!("{}", i); }

B. for i to v { println!("{}", i); }

C. foreach i in v { println!("{}", i); }

D. loop i in v { println!("{}", i); }

Solution

1. Step 1: Recall Rust for loop syntax

   Rust uses 'for variable in collection' to iterate over items.

2. Step 2: Check each option

   for i in v { println!("{}", i); } matches correct syntax; others use invalid keywords.

3. Final Answer:

   for i in v { println!("{}", i); } -> Option A

4. Quick Check:

   Rust uses 'for ... in ...' loops [OK]

Hint: Remember: for variable in collection [OK]

Common Mistakes:

• Using 'to' instead of 'in'
• Using 'foreach' which is not Rust syntax
• Using 'loop' incorrectly

3. What is the output of this Rust code?

let v = vec![10, 20, 30];
let mut sum = 0;
for &num in &v {
    sum += num;
}
println!("{}", sum);

medium

A. 60

B. 303020

C. Error due to borrowing

D. 0

Solution

1. Step 1: Understand iteration with references

   The loop uses '&num in &v' to borrow each element by reference and dereference it with '&num'.

2. Step 2: Calculate sum of elements

   sum starts at 0, then adds 10, 20, and 30, resulting in 60.

3. Final Answer:

   60 -> Option A

4. Quick Check:

   Sum of 10+20+30 = 60 [OK]

Hint: Sum elements by iterating with references [OK]

Common Mistakes:

• Confusing references and values
• Expecting concatenation instead of sum
• Thinking borrowing causes error here

4. Identify the error in this Rust code snippet:

let arr = [1, 2, 3];
for num in arr {
    num += 1;
    println!("{}", num);
}

medium

A. Loop variable 'num' must be a reference

B. Syntax error: missing semicolon after println!

C. Array cannot be iterated directly

D. Cannot modify 'num' because it is an immutable copy

Solution

1. Step 1: Check mutability of loop variable

   In Rust, loop variables are immutable by default; 'num' is a copy of array element.

2. Step 2: Understand why 'num += 1' fails

   Trying to change 'num' causes error because it is not declared mutable.

3. Final Answer:

   Cannot modify 'num' because it is an immutable copy -> Option D

4. Quick Check:

   Loop variables are immutable unless declared mutable [OK]

Hint: Loop vars are immutable unless 'mut' used [OK]

Common Mistakes:

• Thinking semicolon missing causes error
• Believing arrays can't be iterated
• Assuming loop vars are references by default

5. You have a vector of strings: let words = vec!["apple", "banana", "cherry"];. How do you create a new vector containing the lengths of each word using iteration?

hard

A. let lengths = words.map(|w| w.len());

B. let lengths = for w in words { w.len() };

C. let lengths: Vec<usize> = words.iter().map(|w| w.len()).collect();

D. let lengths = words.iter().for_each(|w| w.len());

Solution

1. Step 1: Use iterator and map to transform elements

   words.iter() creates an iterator over references to strings; map applies a function to each element.

2. Step 2: Collect results into a new vector

   collect() gathers the mapped lengths into a Vec<usize>.

3. Final Answer:

   let lengths: Vec<usize> = words.iter().map(|w| w.len()).collect(); -> Option C

4. Quick Check:

   Use iter().map(...).collect() to transform collections [OK]

Hint: Use iter().map(...).collect() to build new collections [OK]

Common Mistakes:

• Trying to use for loop as expression
• Using map directly on vector without iter()
• Using for_each which returns () not a collection