Immutable references in Rust - Time & Space Complexity

Time Complexity: Immutable references

O(n)

Understanding Time Complexity

Let's see how using immutable references affects the time it takes for a Rust program to run.

We want to know how the program's work grows when it reads data without changing it.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn sum_elements(numbers: &Vec<i32>) -> i32 {
    let mut sum = 0;
    for &num in numbers.iter() {
        sum += num;
    }
    sum
}

This code calculates the sum of all numbers in a list using an immutable reference.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the list gets bigger, the program does more work by adding more numbers.

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 an immutable reference makes the loop faster or slower."

[OK] Correct: Immutable references only control data safety, not how many times the loop runs. The time depends on the list size, not the reference type.

Interview Connect

Understanding how loops work with references shows you can reason about program speed and safety together, a skill useful in many coding tasks.

Self-Check

"What if we changed the immutable reference to a mutable one and modified elements inside the loop? How would the time complexity change?"

Practice

1. What does an immutable reference in Rust allow you to do?

easy

A. Prevent any access to the data

B. Read data without changing it

C. Create multiple mutable references

D. Change data while reading it

Solution

1. Step 1: Understand the purpose of immutable references

   Immutable references allow you to look at data without changing it.

2. Step 2: Compare options with this understanding

   Only Read data without changing it correctly states that immutable references let you read data without changing it.

3. Final Answer:

   Read data without changing it -> Option B

4. Quick Check:

   Immutable reference = read-only access [OK]

Hint: Immutable references only allow reading data [OK]

Common Mistakes:

• Thinking immutable references allow data modification
• Confusing mutable and immutable references
• Believing immutable references block all access

2. Which of the following is the correct syntax to create an immutable reference to a variable x in Rust?

easy

A. let ref = x&;

B. let ref = *x;

C. let ref = &mut x;

D. let ref = &x;

Solution

1. Step 1: Recall syntax for immutable references

   In Rust, an immutable reference is created using the ampersand before the variable: &x.

2. Step 2: Check each option

   let ref = &x; uses &x correctly. let ref = *x; uses dereference operator incorrectly. let ref = &mut x; creates a mutable reference, not immutable. let ref = x&; is invalid syntax.

3. Final Answer:

   let ref = &x; -> Option D

4. Quick Check:

   Immutable reference syntax = &variable [OK]

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

Common Mistakes:

• Using *x instead of &x
• Confusing mutable (&mut) with immutable (&)
• Writing invalid syntax like x&

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

let x = 10;
let r1 = &x;
let r2 = &x;
println!("{} and {}", r1, r2);

medium

A. Compilation error due to multiple references

B. Runtime error

C. 10 and 10

D. 10 and 0

Solution

1. Step 1: Understand multiple immutable references

   Rust allows multiple immutable references to the same data at the same time without error.

2. Step 2: Check the print statement

   Both r1 and r2 point to x which is 10, so printing them shows "10 and 10".

3. Final Answer:

   10 and 10 -> Option C

4. Quick Check:

   Multiple immutable refs print same value [OK]

Hint: Multiple immutable references can coexist safely [OK]

Common Mistakes:

• Thinking multiple immutable references cause errors
• Expecting runtime errors from references
• Confusing mutable and immutable references rules

4. Identify the error in this Rust code snippet:

let mut x = 5;
let r1 = &x;
let r2 = &mut x;
println!("{} and {}", r1, r2);

medium

A. Cannot have mutable and immutable references at the same time

B. Missing semicolon after let r1

C. Cannot print references directly

D. Variable x should not be mutable

Solution

1. Step 1: Check reference rules in Rust

   Rust forbids having a mutable reference while immutable references exist to the same variable.

2. Step 2: Analyze the code

   Here, r1 is an immutable reference and r2 is a mutable reference to x at the same time, causing a compile error.

3. Final Answer:

   Cannot have mutable and immutable references at the same time -> Option A

4. Quick Check:

   Mutable + immutable refs together = error [OK]

Hint: Mutable and immutable refs can't coexist simultaneously [OK]

Common Mistakes:

• Ignoring Rust's borrowing rules
• Thinking printing references causes error
• Assuming mutability of variable is the problem

5. Given this Rust function:

fn print_value(val: &i32) {
    println!("Value is {}", val);
}

fn main() {
    let mut num = 20;
    let r1 = #
    print_value(r1);
    let r2 = &mut num;
    *r2 += 5;
    print_value(&num);
}

What is the output when this program runs?

hard

A. Value is 20\nValue is 25

B. Compilation error due to mutable and immutable references

C. Value is 25\nValue is 25

D. Runtime error

Solution

1. Step 1: Analyze references in main function

   First, an immutable reference r1 to num is created and passed to print_value. Then a mutable reference r2 is created after r1 is no longer used.

2. Step 2: Check Rust borrowing rules

   Rust allows mutable references after immutable references are no longer used. Here, r1 is used only in print_value, so r2 creation is valid.

3. Step 3: Determine output

   First print_value prints 20, then after incrementing via r2, second print_value prints 25.

4. Final Answer:

   Value is 20 Value is 25 -> Option A

5. Quick Check:

   Immutable ref used before mutable ref creation [OK]

Hint: Mutable ref can be created after immutable ref is no longer used [OK]

Common Mistakes:

• Assuming code runs into compile error
• Ignoring Rust's borrowing rules about scopes
• Thinking mutable ref can coexist with immutable ref simultaneously