Why lifetimes exist in Rust - Performance Analysis

Time Complexity: Why lifetimes exist

O(1)

Understanding Time Complexity

We want to understand why Rust uses lifetimes and how they affect program execution.

Specifically, we ask: How does Rust ensure safe memory use as programs grow?

Scenario Under Consideration

Analyze the time complexity of the following Rust code snippet involving lifetimes.

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 longest of two string slices, using lifetimes to ensure safety.

Identify Repeating Operations

Look for loops or repeated steps that affect execution time.

• Primary operation: Comparing the lengths (len() is O(1)) of two strings once.
• How many times: Exactly one time per function call.

How Execution Grows With Input

The function fetches lengths with len(), which takes constant time regardless of the length of each string, and compares them.

Input Size (n)	Approx. Operations
10	Constant: 2 len() + 1 compare (~3 ops)
100	Constant: 2 len() + 1 compare (~3 ops)
1000	Constant: 2 len() + 1 compare (~3 ops)

Pattern observation: The time is constant, independent of the string length.

Final Time Complexity

Time Complexity: O(1)

This means the time to run is constant, independent of the size of the input strings.

Common Mistake

[X] Wrong: "Lifetimes slow down the program because they add extra work at runtime."

[OK] Correct: Lifetimes are checked only at compile time, so they do not add any runtime cost or slow down the program.

Interview Connect

Understanding lifetimes shows you can reason about safe memory use and program efficiency, a key skill in Rust programming.

Self-Check

"What if the function returned a new String instead of a string slice? How would the time complexity change?"

Practice

1.

Why does Rust use lifetimes like 'a in its code?

easy

A. To automatically free memory like a garbage collector

B. To make the code run faster by skipping checks

C. To allow multiple mutable references at the same time

D. To ensure references do not outlive the data they point to

Solution

1. Step 1: Understand what lifetimes represent

   Lifetimes in Rust show how long a reference is valid to prevent dangling references.

2. Step 2: Connect lifetimes to safety

   They ensure references do not outlive the data they point to, avoiding bugs.

3. Final Answer:

   To ensure references do not outlive the data they point to -> Option D

4. Quick Check:

   Lifetimes = prevent dangling references [OK]

Hint: Lifetimes prevent references to missing data [OK]

Common Mistakes:

• Thinking lifetimes speed up code
• Confusing lifetimes with garbage collection
• Believing lifetimes allow multiple mutable references

2.

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

fn example(____ s: &'a str) -> &'a str { s }

easy

A. fn example<'a>(s: &'a str) -> &'a str

B. fn example(s: &str<'a>) -> &str<'a>

C. fn example(s: &'a str) -> &str

D. fn example<'a>(s: &str) -> &'a str

Solution

1. Step 1: Recall lifetime syntax in function signatures

   Lifetimes are declared before the function name with 'a and used on references.

2. Step 2: Match correct syntax

   fn example<'a>(s: &'a str) -> &'a str correctly declares 'a and uses it on both input and output references.

3. Final Answer:

   fn example<'a>(s: &'a str) -> &'a str -> Option A

4. Quick Check:

   Lifetime syntax = fn example<'a>(s: &'a str) -> &'a str [OK]

Hint: Declare lifetime before fn name and use on references [OK]

Common Mistakes:

• Putting lifetime after & instead of before type
• Forgetting to declare lifetime before function name
• Using lifetime on non-reference types

3.

What will this Rust code print?

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

fn main() {
    let s1 = String::from("apple");
    let s2 = "banana";
    let result = longest(&s1, s2);
    println!("{}", result);
}

medium

A. apple

B. banana

C. Compilation error due to lifetimes

D. Runtime error due to invalid reference

Solution

1. Step 1: Understand function longest behavior

   It returns the longer string slice between x and y.

2. Step 2: Compare lengths of "apple" and "banana"

   "apple" has 5 letters, "banana" has 6, so it returns "banana".

3. Final Answer:

   banana -> Option B

4. Quick Check:

   Longest string = banana [OK]

Hint: Compare string lengths carefully to find longest [OK]

Common Mistakes:

• Assuming s1 is longer without counting
• Thinking lifetimes cause compile error here
• Confusing references with ownership causing runtime error

4.

Identify the error in this Rust code related to lifetimes:

fn first_word(s: &str) -> &str {
    let bytes = s.as_bytes();
    for (i, &item) in bytes.iter().enumerate() {
        if item == b' ' {
            return &s[0..i];
        }
    }
    &s
}

fn main() {
    let word;
    {
        let s = String::from("hello world");
        word = first_word(&s);
    }
    println!("{}", word);
}

medium

A. Error: cannot borrow s as mutable

B. Error: missing lifetime annotation in function signature

C. Error: returned reference may outlive borrowed data

D. No error, code runs fine

Solution

1. Step 1: Analyze lifetime of variable s

   Variable s is created inside inner block and dropped after it ends.

2. Step 2: Check lifetime of returned reference word

   word holds reference to s, but s is dropped before println!, causing dangling reference.

3. Final Answer:

   Error: returned reference may outlive borrowed data -> Option C

4. Quick Check:

   Dangling reference error = Error: returned reference may outlive borrowed data [OK]

Hint: References must not outlive their data scope [OK]

Common Mistakes:

• Ignoring scope of s and thinking code is safe
• Assuming missing lifetime annotation causes error here
• Confusing mutable borrow errors with lifetime errors

5.

You want to write a function that returns a reference to the longer string slice between two inputs, but one input is owned String and the other is a string slice &str. How should you use lifetimes to make this safe and correct?

hard

A. Convert the owned String to a slice and use a single lifetime for both inputs and output

B. Return the owned String directly without lifetimes

C. Use different lifetimes for each input and output to avoid conflicts

D. Clone both inputs and return an owned String without references

Solution

1. Step 1: Understand input types and lifetimes

   Owned String must be converted to a string slice (&str) to use lifetimes uniformly.

2. Step 2: Use one lifetime parameter for both inputs and output

   This ensures the returned reference is valid as long as both inputs are valid.

3. Final Answer:

   Convert the owned String to a slice and use a single lifetime for both inputs and output -> Option A

4. Quick Check:

   Single lifetime with slices = Convert the owned String to a slice and use a single lifetime for both inputs and output [OK]

Hint: Use &str slices and one lifetime for safe references [OK]

Common Mistakes:

• Returning owned String without references when references expected
• Using multiple lifetimes causing borrow conflicts
• Forgetting to convert String to &str before comparison