Variable lifetime basics in Rust - Time & Space Complexity

Time Complexity: Variable lifetime basics

O(n)

Understanding Time Complexity

When we write Rust code, variables only exist for a certain time called their lifetime.

We want to understand how the time a program runs changes as variables live and get used.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn sum_values(values: &[i32]) -> i32 {
    let mut total = 0;
    for &value in values {
        total += value;
    }
    total
}

fn main() {
    let numbers = vec![1, 2, 3, 4, 5];
    let result = sum_values(&numbers);
    println!("Sum: {}", result);
}
    

This code adds up numbers in a list, using a variable that lives during the loop.

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 each number in the input list.

How Execution Grows With Input

As the list gets bigger, the loop runs more times, adding each number once.

Input Size (n)	Approx. Operations
10	About 10 additions
100	About 100 additions
1000	About 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 run grows in a straight line as the input list gets bigger.

Common Mistake

[X] Wrong: "The variable lifetime makes the program slower because it lasts longer."

[OK] Correct: The variable lifetime just means how long the variable exists in memory, not how many times the code runs. The speed depends on how many times the loop runs, not how long variables live.

Interview Connect

Understanding how variable lifetime relates to loops helps you explain how your code runs efficiently and safely in Rust.

Self-Check

"What if we changed the loop to call a function inside that also loops over the input? How would the time complexity change?"