Borrowing rules in Rust - Time & Space Complexity

Time Complexity: Borrowing rules

O(n)

Understanding Time Complexity

We want to understand how borrowing rules affect the speed of Rust programs.

Specifically, how does the program's work grow when borrowing is involved?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn sum_elements(numbers: &Vec) -> i32 {
    let mut total = 0;
    for num in numbers {
        total += *num;
    }
    total
}

fn main() {
    let data = vec![1, 2, 3, 4, 5];
    let result = sum_elements(&data);
    println!("Sum: {}", result);
}
    

This code sums all numbers in a list by borrowing the list without 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 element in the list.

How Execution Grows With Input

As the list gets bigger, the program does more work by visiting each number once.

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 sum grows in a straight line with the list size.

Common Mistake

[X] Wrong: "Borrowing makes the code run faster because it avoids copying."

[OK] Correct: Borrowing helps with memory safety and avoids copying, but the time to visit each element still depends on the list size.

Interview Connect

Understanding how borrowing affects program speed helps you write safe and efficient Rust code, a skill valued in many coding challenges.

Self-Check

"What if we changed the function to take ownership of the vector instead of borrowing? How would the time complexity change?"

Practice

1. What does borrowing in Rust allow you to do?

easy

A. Copy data to a new variable

B. Use data without taking ownership

C. Delete data immediately

D. Create multiple owners of data

Solution

1. Step 1: Understand borrowing concept

   Borrowing means using data without taking ownership, so the original owner keeps control.

2. Step 2: Compare options

   Copying or deleting data changes ownership or data state, which borrowing does not do.

3. Final Answer:

   Use data without taking ownership -> Option B

4. Quick Check:

   Borrowing = Use without ownership [OK]

Hint: Borrowing means using data without owning it [OK]

Common Mistakes:

• Confusing borrowing with copying
• Thinking borrowing deletes data
• Assuming borrowing creates multiple owners

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

easy

A. let y = &x;

B. let y = *x;

C. let y = &mut x;

D. let y = x;

Solution

1. Step 1: Identify immutable borrow syntax

   Immutable borrow uses &x to create a reference without allowing changes.

2. Step 2: Check other options

   &mut x is mutable borrow, *x dereferences, and x moves ownership.

3. Final Answer:

   let y = &x; -> Option A

4. Quick Check:

   Immutable borrow = &x [OK]

Hint: Immutable borrow uses & before variable [OK]

Common Mistakes:

• Using &mut for immutable borrow
• Dereferencing instead of borrowing
• Assigning ownership instead of reference

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

let mut s = String::from("hello");
let r1 = &s;
let r2 = &s;
println!("{} and {}", r1, r2);
let r3 = &mut s;
println!("{}", r3);

medium

A. hello and hello\nerror at runtime

B. hello and hello\nhello

C. Compile error due to mutable borrow while immutable borrows exist

D. hello\nhello and hello

Solution

1. Step 1: Analyze immutable borrows

   Two immutable borrows r1 and r2 are allowed simultaneously.

2. Step 2: Check mutable borrow after immutable borrows

   Trying to create mutable borrow r3 while immutable borrows exist causes compile error.

3. Final Answer:

   Compile error due to mutable borrow while immutable borrows exist -> Option C

4. Quick Check:

   Mutable borrow disallowed with active immutable borrows [OK]

Hint: No mutable borrow allowed if immutable borrows exist [OK]

Common Mistakes:

• Assuming mutable borrow works after immutable borrows
• Expecting runtime error instead of compile error
• Confusing output with allowed borrows

4. Identify the error in this Rust code snippet:

let mut data = vec![1, 2, 3];
let r1 = &mut data;
let r2 = &data;
r1.push(4);
println!("{:?}", r2);

medium

A. No error, code runs fine

B. Cannot push to vector inside mutable borrow

C. Cannot print vector with {:?}

D. Cannot borrow data as immutable while mutable borrow exists

Solution

1. Step 1: Check borrows

   Variable r1 is a mutable borrow, r2 is an immutable borrow of the same data.

2. Step 2: Understand borrowing rules

   Rust forbids immutable borrow while mutable borrow is active, causing a compile error.

3. Final Answer:

   Cannot borrow data as immutable while mutable borrow exists -> Option D

4. Quick Check:

   Immutable borrow disallowed during mutable borrow [OK]

Hint: No immutable borrow allowed during mutable borrow [OK]

Common Mistakes:

• Thinking push is invalid inside mutable borrow
• Ignoring borrow conflict between r1 and r2
• Assuming printing with {:?} causes error

5. You want to write a function that takes a mutable reference to a vector and appends a number, but also returns the length of the vector after appending. Which function signature and usage follow Rust's borrowing rules correctly?

hard

A. fn add_and_len(v: &mut Vec<i32>, n: i32) -> usize { v.push(n); v.len() }
let mut nums = vec![1,2];
let length = add_and_len(&mut nums, 3);

B. fn add_and_len(v: &Vec<i32>, n: i32) -> usize { v.push(n); v.len() }
let mut nums = vec![1,2];
let length = add_and_len(&nums, 3);

C. fn add_and_len(v: Vec<i32>, n: i32) -> usize { v.push(n); v.len() }
let nums = vec![1,2];
let length = add_and_len(nums, 3);

D. fn add_and_len(v: &mut Vec<i32>, n: i32) -> usize { v.len(); v.push(n) }
let mut nums = vec![1,2];
let length = add_and_len(&mut nums, 3);

Solution

1. Step 1: Check function signature for mutable borrow

   Function needs &mut Vec<i32> to modify vector by pushing a number.

2. Step 2: Verify function body and usage

   fn add_and_len(v: &mut Vec<i32>, n: i32) -> usize { v.push(n); v.len() } let mut nums = vec![1,2]; let length = add_and_len(&mut nums, 3); pushes number then returns length correctly; usage passes mutable reference.

3. Step 3: Analyze other options

   fn add_and_len(v: &Vec<i32>, n: i32) -> usize { v.push(n); v.len() } let mut nums = vec![1,2]; let length = add_and_len(&nums, 3); uses immutable borrow but tries to push (not allowed). fn add_and_len(v: Vec<i32>, n: i32) -> usize { v.push(n); v.len() } let nums = vec![1,2]; let length = add_and_len(nums, 3); takes ownership, not borrow. fn add_and_len(v: &mut Vec<i32>, n: i32) -> usize { v.len(); v.push(n) } let mut nums = vec![1,2]; let length = add_and_len(&mut nums, 3); returns length before push, so length is old value.

4. Final Answer:

   fn add_and_len(v: &mut Vec<i32>, n: i32) -> usize { v.push(n); v.len() } let mut nums = vec![1,2]; let length = add_and_len(&mut nums, 3); -> Option A

5. Quick Check:

   Mutable borrow needed to modify vector [OK]

Hint: Use &mut to modify data inside function [OK]

Common Mistakes:

• Using immutable borrow when modifying data
• Taking ownership instead of borrowing
• Returning length before modification