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

Practice

1. What does a variable lifetime in Rust describe?

easy

A. How long a reference remains valid in the program

B. The size of a variable in memory

C. The number of times a variable is used

D. The type of a variable

Solution

1. Step 1: Define lifetime and evaluate options

   In Rust, lifetime refers to how long a reference is valid and safe to use. Only 'How long a reference remains valid in the program' correctly describes it; B is size, C is usage count, D is type.

2. Final Answer:

   How long a reference remains valid in the program -> Option A

3. Quick Check:

   Lifetime = reference validity duration [OK]

Hint: Lifetime means reference validity duration [OK]

Common Mistakes:

• Confusing lifetime with variable size
• Thinking lifetime counts usage times
• Mixing lifetime with variable type

2. Which of the following is the correct syntax to declare a function with a lifetime parameter 'a for a reference argument in Rust?

easy

A. fn example(x: &i32) -> &i32 { x }

B. fn example(x: &i32<'a>) -> &i32<'a> { x }

C. fn example<'a>(x: &'a i32) -> &'a i32 { x }

D. fn example<'a>(x: &i32) -> &'a i32 { x }

Solution

1. Step 1: Verify lifetime annotation syntax and check options

   Rust requires lifetime parameters declared with 'a before the function and used in references as &'a i32. A correctly declares and uses 'a for input/output. B misplaces after type, C lacks annotations, D misses on input.

2. Final Answer:

   fn example<'a>(x: &'a i32) -> &'a i32 { x } -> Option C

3. Quick Check:

   Lifetime syntax = fn name<'a>(x: &'a Type) -> &'a Type [OK]

Hint: Declare lifetime before function, use on references [OK]

Common Mistakes:

• Placing lifetime after type instead of before
• Omitting lifetime on input or output references
• Using lifetime without declaring it

3. What will be the output of this Rust code snippet?

fn main() {
    let mut r;
    {
        let x = 5;
        r = &x;
    }
    println!("{}", r);
}

medium

A. 5

B. Compilation error due to lifetime mismatch

C. 0

D. Runtime panic

Solution

1. Step 1: Analyze scopes and reference lifetime

   x goes out of scope at end of inner block, but r references it and lives longer, violating Rust's lifetime rules, resulting in compilation error.

2. Final Answer:

   Compilation error due to lifetime mismatch -> Option B

3. Quick Check:

   Reference lifetime must not outlive data [OK]

Hint: References can't outlive the data they point to [OK]

Common Mistakes:

• Assuming code prints 5 without error
• Expecting runtime panic instead of compile error
• Ignoring inner block scope

4. Identify the error in this Rust function related to lifetimes:

fn longest(x: &str, y: &str) -> &str {
    if x.len() > y.len() { x } else { y }
}

medium

A. Missing lifetime annotations on parameters and return type

B. Using &str instead of String

C. Function should return usize instead of &str

D. No error, code is correct

Solution

1. Step 1: Examine function signature and Rust lifetime rules

   The function returns a reference to one of the inputs without lifetime annotations, preventing Rust from verifying safety. Annotations like <'a> are required on params and return.

2. Final Answer:

   Missing lifetime annotations on parameters and return type -> Option A

3. Quick Check:

   Return references need lifetime annotations [OK]

Hint: Add lifetime annotations when returning references [OK]

Common Mistakes:

• Thinking &str vs String causes error
• Believing function should return length
• Assuming no error without lifetimes

5. Given this struct and function, which lifetime annotation is correct to ensure the reference inside Holder is valid?

struct Holder<'a> {
    value: &'a str,
}

fn create_holder(s: &str) -> Holder {
    Holder { value: s }
}

hard

A. fn create_holder(s: &'a str) -> Holder<'a> { Holder { value: s } }

B. fn create_holder(s: &str) -> Holder { Holder { value: s } }

C. fn create_holder<'a>(s: &str) -> Holder<'a> { Holder { value: s } }

D. fn create_holder<'a>(s: &'a str) -> Holder<'a> { Holder { value: s } }

Solution

1. Step 1: Match function signature to struct lifetime parameter

   Holder<'a> ties value's lifetime to 'a. Function must declare 'a, use on s: &'a str, return Holder<'a>. D correct; A lacks fn 'a decl, B/C mismatch lifetimes.

2. Final Answer:

   fn create_holder<'a>(s: &'a str) -> Holder<'a> { Holder { value: s } } -> Option D

3. Quick Check:

   Function lifetimes must match struct lifetimes [OK]

Hint: Match function and struct lifetimes exactly [OK]

Common Mistakes:

• Omitting lifetime on function signature
• Using lifetime only on return or input, not both
• Assuming struct lifetime is optional