Mutable references in Rust - Time & Space Complexity

Time Complexity: Mutable references

O(n)

Understanding Time Complexity

When using mutable references in Rust, it's important to see how the program's steps grow as input gets bigger.

We want to know how the time to run changes when we change the size of the data we modify through mutable references.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn increment_all(nums: &mut [i32]) {
    for num in nums {
        *num += 1;
    }
}

fn main() {
    let mut values = vec![1, 2, 3, 4, 5];
    increment_all(&mut values);
}
    

This code increases each number in a list by one using a mutable reference to change the original data.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each element in the list to increment it.
• How many times: Once for each element in the list.

How Execution Grows With Input

As the list gets bigger, the program spends more time because it changes each number one by one.

Input Size (n)	Approx. Operations
10	10 increments
100	100 increments
1000	1000 increments

Pattern observation: The time grows directly with the number of items; doubling items doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the number of elements you change.

Common Mistake

[X] Wrong: "Using mutable references makes the code run faster because it changes data directly."

[OK] Correct: Mutable references let you change data safely, but the time depends on how many items you process, not just on using references.

Interview Connect

Understanding how mutable references affect time helps you explain how your code handles data changes efficiently and safely.

Self-Check

"What if we changed the loop to only increment every other element? How would the time complexity change?"

Practice

1. What does a mutable reference &mut allow you to do in Rust?

easy

A. Prevent any changes to the value it points to

B. Create multiple immutable references at the same time

C. Move ownership of the value to another variable

D. Change the value it points to without taking ownership

Solution

1. Step 1: Understand what &mut means

   The &mut symbol creates a mutable reference, which means you can change the value it points to without taking ownership.

2. Step 2: Compare with other options

   Options B and D describe immutable references or no changes allowed, and C talks about ownership transfer, which is different from mutable references.

3. Final Answer:

   Change the value it points to without taking ownership -> Option D

4. Quick Check:

   Mutable reference = change value without ownership [OK]

Hint: Mutable references let you change data without moving ownership [OK]

Common Mistakes:

• Confusing mutable references with ownership transfer
• Thinking multiple mutable references are allowed simultaneously
• Believing mutable references prevent changes

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: Identify the syntax for mutable references

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

2. Step 2: Check each option

   A creates an immutable reference, B dereferences the value, and D has incorrect syntax order.

3. Final Answer:

   let ref = &mut num; -> Option B

4. Quick Check:

   Mutable reference syntax = &mut variable [OK]

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

Common Mistakes:

• Forgetting the 'mut' keyword after &
• Placing 'mut' before & incorrectly
• Using * instead of &mut for references

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

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

medium

A. 6

B. Runtime panic

C. Compilation error

D. 5

Solution

1. Step 1: Understand the mutable reference usage

   The variable x is mutable. A mutable reference r is created to x. The value pointed by r is incremented by 1 using *r += 1;.

2. Step 2: Determine the final value of x

   Since r points to x, incrementing *r changes x from 5 to 6. The print statement outputs 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Mutable reference modifies original value = 6 [OK]

Hint: Dereference mutable ref with * to change original value [OK]

Common Mistakes:

• Expecting original value unchanged
• Confusing reference with copy
• Thinking code causes compile error

4. What is wrong with this Rust code?

fn main() {
    let mut val = 10;
    let r1 = &mut val;
    let r2 = &mut val;
    *r1 += 1;
    *r2 += 1;
    println!("{}", val);
}

medium

A. Dereferencing mutable references is not allowed

B. Cannot mutate a variable declared as mutable

C. Cannot have two mutable references to the same variable at the same time

D. Missing semicolon after println!

Solution

1. Step 1: Identify the mutable references

   The code creates two mutable references r1 and r2 to the same variable val at the same time.

2. Step 2: Recall Rust's borrowing rules

   Rust allows only one mutable reference at a time to prevent data races. Having two mutable references simultaneously causes a compile-time error.

3. Final Answer:

   Cannot have two mutable references to the same variable at the same time -> Option C

4. Quick Check:

   Only one mutable reference allowed at once [OK]

Hint: Only one mutable reference allowed at a time [OK]

Common Mistakes:

• Trying to create multiple mutable references simultaneously
• Thinking mutable references can be copied freely
• Ignoring Rust's borrowing rules

5. Given the following code, what is the correct way to safely modify the value inside data using mutable references without causing a compile error?

fn main() {
    let mut data = 100;
    let r1 = &data;
    let r2 = &mut data;
    *r2 += 50;
    println!("{}", data);
}

hard

A. Remove the immutable reference r1 before creating r2

B. Change r2 to an immutable reference &data

C. Use two mutable references r1 and r2 simultaneously

D. Make data immutable by removing mut

Solution

1. Step 1: Understand Rust's borrowing rules

   Rust does not allow mutable and immutable references to the same variable at the same time. Here, r1 is immutable and r2 is mutable, causing a conflict.

2. Step 2: Fix the code by removing the immutable reference

   Removing r1 allows only the mutable reference r2 to exist, so modifying data through r2 is safe and allowed.

3. Final Answer:

   Remove the immutable reference r1 before creating r2 -> Option A

4. Quick Check:

   Mutable and immutable refs cannot coexist [OK]

Hint: Remove immutable refs before mutable refs to avoid errors [OK]

Common Mistakes:

• Trying to use mutable and immutable references simultaneously
• Changing mutable ref to immutable without reason
• Making variable immutable but still trying to mutate