Slice lifetime basics in Rust - Time & Space Complexity

Time Complexity: Slice lifetime basics

O(n)

Understanding Time Complexity

When working with slices in Rust, it is important to understand how the program's speed changes as the slice size grows.

We want to know how the time to process a slice changes when the slice gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn sum_slice(slice: &[i32]) -> i32 {
    let mut total = 0;
    for &item in slice {
        total += item;
    }
    total
}
    

This function adds up all the numbers in a slice and returns the total.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the slice gets bigger, the function does more additions, one for each item.

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 in the slice.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line as the slice gets bigger.

Common Mistake

[X] Wrong: "The function runs in the same time no matter the slice size."

[OK] Correct: Because the function must look at every item, more items mean more work and more time.

Interview Connect

Understanding how loops over slices affect time helps you explain your code clearly and shows you know how programs grow with data size.

Self-Check

"What if we changed the function to only sum the first half of the slice? How would the time complexity change?"

Practice

1. What does a slice lifetime in Rust indicate?
fn example<'a>(slice: &'a [i32]) {}

easy

A. How long the slice reference is valid in the program

B. The size of the slice in memory

C. The number of elements in the slice

D. The type of elements inside the slice

Solution

1. Step 1: Understand what a lifetime means in Rust

   Lifetimes tell Rust how long a reference is valid to prevent using invalid data.

2. Step 2: Apply this to a slice reference

   The lifetime on a slice reference means how long the slice can be safely used.

3. Final Answer:

   How long the slice reference is valid in the program -> Option A

4. Quick Check:

   Slice lifetime = reference validity [OK]

Hint: Lifetimes track reference validity duration [OK]

Common Mistakes:

• Confusing lifetime with size or length
• Thinking lifetime is about element type
• Ignoring lifetime annotations on references

2. Which of the following is the correct syntax to declare a function that takes a slice with a lifetime parameter?

fn process_slice(____) {}

easy

A. &'a [i32]

B. &'a [i32];

C. &[i32]

D. &[i32]'a

Solution

1. Step 1: Recall lifetime syntax for references

   Lifetimes are written as &'a before the type to indicate the lifetime of the reference.

2. Step 2: Check each option

   &'a [i32] correctly places &'a before the slice type [i32]. &[i32] misses lifetime, &'a [i32]; has an extra semicolon, &[i32]'a places lifetime incorrectly.

3. Final Answer:

   &'a [i32] -> Option A

4. Quick Check:

   Lifetime syntax = &'a [type] [OK]

Hint: Lifetimes go right after & before type [OK]

Common Mistakes:

• Putting lifetime after the type
• Adding extra semicolons inside parameters
• Omitting lifetime when needed

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

fn get_first<'a>(slice: &'a [i32]) -> &'a i32 {
    &slice[0]
}

fn main() {
    let numbers = vec![10, 20, 30];
    let first = get_first(&numbers);
    println!("{}", first);
}

medium

A. 20

B. 10

C. Compilation error due to lifetime mismatch

D. Runtime panic

Solution

1. Step 1: Understand the function behavior

   The function returns a reference to the first element of the slice, which is 10.

2. Step 2: Check lifetime correctness and usage

   The lifetime 'a ensures the returned reference is valid as long as the input slice is valid. The vector lives long enough, so no error.

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Returned first element = 10 [OK]

Hint: Returned slice element matches first index [OK]

Common Mistakes:

• Thinking lifetime causes compile error here
• Confusing element values
• Expecting runtime panic without reason

4. Identify the error in this Rust code snippet:

fn invalid<'a>() -> &'a [i32] {
    let data = vec![1, 2, 3];
    &data[..]
}

medium

A. Missing lifetime annotation on data

B. Syntax error in slice syntax

C. The function returns a reference to data that will be dropped

D. No error, code is correct

Solution

1. Step 1: Analyze the function return and data lifetime

   The function returns a slice reference with lifetime 'a, but data is created inside the function and dropped when it ends.

2. Step 2: Understand why this causes an error

   Returning a reference to local data is invalid because the data won't live long enough, causing a dangling reference.

3. Final Answer:

   The function returns a reference to data that will be dropped -> Option C

4. Quick Check:

   Returning local reference = error [OK]

Hint: Never return reference to local variable [OK]

Common Mistakes:

• Assuming lifetime annotation fixes local data drop
• Ignoring ownership rules
• Thinking slice syntax is wrong

5. Given this function that returns a slice from two input slices, which lifetime annotation is correct to ensure safety?

fn longest_slice<'a>(x: &'a [i32], y: &'a [i32]) -> &____ [i32] {
    if x.len() > y.len() { x } else { y }
}

hard

A. 'a + 'b

B. 'b

C. 'static

D. 'a

Solution

1. Step 1: Understand the function's return lifetime

   The function returns a slice that could come from either input slice, both sharing lifetime 'a.

2. Step 2: Use shared lifetime for safety

   The correct lifetime for the return is 'a, matching the lifetime of both input slices.

3. Final Answer:

   'a -> Option D

4. Quick Check:

   Return lifetime = 'a of inputs [OK]

Hint: Return lifetime must cover both inputs [OK]

Common Mistakes:

• Choosing only one input lifetime
• Using 'static without reason
• Ignoring lifetime intersection rules