Mutable variables in Rust - Time & Space Complexity

Time Complexity: Mutable variables

O(n)

Understanding Time Complexity

Let's see how using mutable variables affects how long a program takes to run.

We want to know how the program's steps grow when we change the input size.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn sum_numbers(n: u32) -> u32 {
    let mut total = 0;
    for i in 1..=n {
        total += i;
    }
    total
}

This code adds numbers from 1 up to n using a mutable variable to keep the running total.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each number to the total inside the loop.
• How many times: Exactly n times, once for each number from 1 to n.

How Execution Grows With Input

Each time n gets bigger, the loop runs more times, so the work grows steadily.

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

Pattern observation: The number of steps grows directly with n; doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the size of the input.

Common Mistake

[X] Wrong: "Using a mutable variable makes the program faster or slower in a way that changes the time complexity."

[OK] Correct: The mutable variable just holds the running total; it doesn't add extra loops or steps. The main factor is how many times the loop runs.

Interview Connect

Understanding how loops and variables affect time helps you explain your code clearly and shows you know what makes programs faster or slower.

Self-Check

"What if we replaced the loop with recursion that sums numbers? How would the time complexity change?"