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