Lifetime annotations in Rust - Time & Space Complexity

Time Complexity: Lifetime annotations

O(1)

Understanding Time Complexity

When we use lifetime annotations in Rust, we want to understand how they affect the speed of our program.

We ask: does adding lifetime annotations change how long the program takes to run as the input grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

fn main() {
    let string1 = String::from("hello");
    let string2 = "world";
    let result = longest(string1.as_str(), string2);
    println!("Longest string is: {}", result);
}
    

This code finds the longer of two string slices using lifetime annotations to ensure safety.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing the length of two strings once.
• How many times: Exactly one time per function call.

How Execution Grows With Input

The function checks the length of each string once, so the time depends on how long it takes to get the length.

Input Size (n)	Approx. Operations
10	2 length checks + 1 comparison
100	2 length checks + 1 comparison
1000	2 length checks + 1 comparison

Pattern observation: The number of operations stays the same regardless of input size.

Final Time Complexity

Time Complexity: O(1)

This means the time to run the function does not grow with the size of the input strings.

Common Mistake

[X] Wrong: "Lifetime annotations make the program slower because they add extra work at runtime."

[OK] Correct: Lifetime annotations are checked only at compile time and do not affect runtime speed.

Interview Connect

Understanding that lifetime annotations do not add runtime cost shows you know Rust's safety features separate from performance.

Self-Check

"What if the function compared every character of the strings instead of just their lengths? How would the time complexity change?"