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