Immutable variables in Rust - Time & Space Complexity

Time Complexity: Immutable variables

O(n)

Understanding Time Complexity

Let's see how using immutable variables affects the speed of a program.

We want to know if not changing values changes how long the program takes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code adds up all numbers in an array without changing the array itself.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the array gets bigger, the program does more additions, one for each number.

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

Pattern observation: The work 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 with the input size.

Common Mistake

[X] Wrong: "Immutable variables make the program slower because you can't change values directly."

[OK] Correct: Immutable variables don't add extra loops or steps; they just prevent changes, so speed depends on how many times you repeat actions, not on mutability.

Interview Connect

Understanding how immutability affects performance helps you write clear and efficient code, a skill valued in many coding challenges and real projects.

Self-Check

"What if we changed the loop to run twice over the array? How would the time complexity change?"