Reference usage patterns in Rust - Time & Space Complexity

Time Complexity: Reference usage patterns

O(n)

Understanding Time Complexity

We want to see how using references in Rust affects how long a program takes to run.

Specifically, we ask: does borrowing data change how many steps the program needs?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn sum_values(values: &Vec) -> 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 sums all numbers in a list by borrowing the list instead of taking ownership.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the list gets bigger, the program does more additions, one per 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.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the list size.

Common Mistake

[X] Wrong: "Using references makes the program run faster by doing fewer steps."

[OK] Correct: Borrowing data avoids copying but does not reduce the number of times the program processes each item.

Interview Connect

Understanding how references affect time helps you explain efficient data handling clearly and confidently.

Self-Check

"What if we changed the vector to a linked list? How would the time complexity change?"

Practice

1. What does the & symbol represent in Rust when used before a variable?

easy

A. A pointer that can be null

B. A mutable reference to the variable, allowing modification

C. A reference to the variable, allowing read-only access without ownership

D. A way to clone the variable's value

Solution

1. Step 1: Understand the meaning of & in Rust

   In Rust, & creates a reference to a value, which means you can read the value without taking ownership.

2. Step 2: Differentiate from mutable references and pointers

   &mut is used for mutable references, and Rust references are never null pointers, so & is not a pointer that can be null.

3. Final Answer:

   A reference to the variable, allowing read-only access without ownership -> Option C

4. Quick Check:

   & means read-only reference [OK]

Hint: Remember: & means read-only reference, &mut means change allowed [OK]

Common Mistakes:

• Confusing & with &mut for mutability
• Thinking & creates a copy of the value
• Assuming & can be null pointer

2. Which of the following is the correct syntax to create a mutable reference to a variable num in Rust?

easy

A. let ref = #

B. let ref = &mut num;

C. let ref = *num;

D. let ref = mut #

Solution

1. Step 1: Recall syntax for mutable references

   In Rust, to create a mutable reference, you use &mut before the variable name.

2. Step 2: Check each option

   let ref = # uses & which is an immutable reference. let ref = *num; uses dereference operator * incorrectly here. let ref = mut # has incorrect syntax order.

3. Final Answer:

   let ref = &mut num; -> Option B

4. Quick Check:

   Mutable reference syntax = &mut [OK]

Hint: Use &mut before variable for mutable reference [OK]

Common Mistakes:

• Using & instead of &mut for mutable references
• Placing mut after & incorrectly
• Using * instead of & for references

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

fn main() {
    let x = 10;
    let y = &x;
    println!("{}", y);
}

medium

A. 10

B. &10

C. Compilation error

D. Memory address of x

Solution

1. Step 1: Understand the reference y = &x

   Variable y is a reference to x, so it points to the value 10.

2. Step 2: Printing a reference with println!("{}", y)

   Rust automatically dereferences y when printing, so it prints the value 10, not the address or &10.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Printing reference prints value [OK]

Hint: Printing &var shows value, not address [OK]

Common Mistakes:

• Expecting &10 to print literally
• Thinking it prints memory address
• Assuming compilation error due to reference

4. Identify the error in this Rust code snippet:

fn main() {
    let mut num = 5;
    let r = #
    *r = 10;
    println!("{}", num);
}

medium

A. Cannot assign to *r because r is an immutable reference

B. num should not be mutable

C. Missing semicolon after *r = 10

D. Cannot print num after referencing

Solution

1. Step 1: Check reference mutability

   Variable r is an immutable reference to num because it is declared as &num, not &mut num.

2. Step 2: Understand assignment through reference

   You cannot assign a new value through an immutable reference. The line *r = 10; causes a compilation error.

3. Final Answer:

   Cannot assign to *r because r is an immutable reference -> Option A

4. Quick Check:

   Immutable reference cannot be used to modify value [OK]

Hint: Use &mut for references if you want to change data [OK]

Common Mistakes:

• Forgetting to use &mut for mutable references
• Thinking mut on variable alone allows mutation through immutable ref
• Ignoring compiler error messages

5. Given a function that takes a mutable reference to a vector and appends a value, which of the following correctly calls the function to add 42 to vec?

fn add_value(v: &mut Vec<i32>) {
    v.push(42);
}

fn main() {
    let mut vec = vec![1, 2, 3];
    // Which call is correct here?
}

hard

A. add_value(&vec);

B. add_value(mut &vec);

C. add_value(vec);

D. add_value(&mut vec);

Solution

1. Step 1: Understand function parameter type

   The function add_value expects a mutable reference &mut Vec<i32>.

2. Step 2: Check how to pass mutable reference

   To pass a mutable reference, the variable must be mutable and passed as &mut vec. Passing &vec is immutable reference, and passing vec moves ownership.

3. Final Answer:

   add_value(&mut vec); -> Option D

4. Quick Check:

   Mutable reference call uses &mut [OK]

Hint: Pass &mut variable to functions needing mutable reference [OK]

Common Mistakes:

• Passing immutable reference when mutable is needed
• Passing ownership instead of reference
• Incorrect syntax like mut &var