Ownership rules in Rust - Time & Space Complexity

Time Complexity: Ownership rules

O(1)

Understanding Time Complexity

Ownership rules in Rust control how data is accessed and managed in memory.

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

Scenario Under Consideration

Analyze the time complexity of the following Rust code snippet.

fn calculate_length(s: String) -> (String, usize) {
    let length = s.len();
    (s, length)
}

fn main() {
    let s1 = String::from("hello");
    let (s2, len) = calculate_length(s1);
    println!("Length: {}", len);
}
    

This code moves ownership of a string to a function, calculates its length, and returns both.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calling len() on the string to get its length.
• How many times: Once per function call, no loops or recursion here.

How Execution Grows With Input

Rust's String::len() retrieves a stored length value in constant time (O(1)). Ownership moves are also O(1) as they involve pointer adjustments without copying data.

Input Size (n)	Approx. Operations
10	O(1)
100	O(1)
1000	O(1)

Pattern observation: The work remains constant regardless of the string length.

Final Time Complexity

Time Complexity: O(1)

This means the time to get the string length remains constant, independent of the string size.

Common Mistake

[X] Wrong: "Ownership transfers make the program slower because data is copied every time."

[OK] Correct: Ownership moves just transfer control without copying data, so they don't add extra time.

Interview Connect

Understanding ownership helps you write safe and efficient Rust code, a skill that shows you know how to manage resources well.

Self-Check

"What if the function borrowed the string instead of taking ownership? How would the time complexity change?"

Practice

1. What happens when ownership of a variable is moved to another variable in Rust?

easy

A. The original variable becomes invalid and cannot be used.

B. Both variables can be used independently without restrictions.

C. The data is copied and both variables own separate copies.

D. The original variable automatically deletes the data.

Solution

1. Step 1: Understand ownership move

   When ownership moves, the original variable loses its right to access the data.

2. Step 2: Effect on original variable

   The original variable becomes invalid and cannot be used to prevent double free errors.

3. Final Answer:

   The original variable becomes invalid and cannot be used. -> Option A

4. Quick Check:

   Ownership move invalidates old owner = A [OK]

Hint: Ownership move disables old variable usage [OK]

Common Mistakes:

• Thinking ownership move copies data
• Assuming both variables remain valid
• Confusing move with borrowing

2. Which of the following is the correct syntax to borrow a variable immutably in Rust?

easy

A. let ref x = value;

B. let x = value;

C. let x = *value;

D. let x = &value;

Solution

1. Step 1: Identify borrowing syntax

   Immutable borrowing uses the & symbol before the variable.

2. Step 2: Match correct syntax

   let x = &value; correctly borrows value immutably.

3. Final Answer:

   let x = &value; -> Option D

4. Quick Check:

   Immutable borrow uses & = B [OK]

Hint: Use & to borrow immutably [OK]

Common Mistakes:

• Using * for borrowing instead of dereferencing
• Missing & symbol for borrowing
• Confusing mutable and immutable borrow syntax

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

let s1 = String::from("hello");
let s2 = s1;
println!("{}", s1);

medium

A. Runtime error

B. hello

C. Compilation error

D. Empty string

Solution

1. Step 1: Analyze ownership move

   Assigning s1 to s2 moves ownership, invalidating s1.

2. Step 2: Using invalidated variable

   Printing s1 after move causes a compile-time error because s1 is no longer valid.

3. Final Answer:

   Compilation error -> Option C

4. Quick Check:

   Using moved variable causes compile error = A [OK]

Hint: Using moved variable causes compile error [OK]

Common Mistakes:

• Expecting s1 to print after move
• Confusing move with copy
• Thinking runtime error occurs instead

4. Identify the error in this Rust code snippet:

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

medium

A. No error, code runs fine.

B. Cannot borrow s as mutable because it is already borrowed as immutable.

C. String::from is not a valid function.

D. Cannot print two variables in one println! macro.

Solution

1. Step 1: Check borrowing rules

   Rust forbids mutable borrow if immutable borrow exists simultaneously.

2. Step 2: Identify conflict

   r1 is an immutable borrow; r2 tries mutable borrow causing error.

3. Final Answer:

   Cannot borrow s as mutable because it is already borrowed as immutable. -> Option B

4. Quick Check:

   Mutable borrow conflicts with existing immutable borrow = D [OK]

Hint: Mutable borrow disallowed if immutable borrow exists [OK]

Common Mistakes:

• Ignoring borrow rules and expecting code to run
• Thinking multiple mutable borrows allowed
• Misunderstanding println! macro usage

5. Given this Rust function:

fn take_ownership(s: String) {
    println!("{}", s);
}

fn main() {
    let s = String::from("hello");
    take_ownership(s);
    println!("{}", s);
}

What is the correct way to fix the error without cloning the string?

hard

A. Change the function parameter to borrow the string: fn take_ownership(s: &String)

B. Remove the println! after the function call.

C. Declare s as mutable in main.

D. Use let s = &String::from("hello"); in main.

Solution

1. Step 1: Understand ownership transfer

   Passing s to take_ownership moves ownership, invalidating s in main.

2. Step 2: Use borrowing to avoid move

   Changing parameter to &String borrows s, so ownership stays with main.

3. Step 3: Adjust function call

   Call take_ownership(&s) to pass reference matching new parameter.

4. Final Answer:

   Change the function parameter to borrow the string: fn take_ownership(s: &String) -> Option A

5. Quick Check:

   Borrow parameter to keep ownership in caller = C [OK]

Hint: Borrow in function parameter to keep ownership [OK]

Common Mistakes:

• Trying to use s after move without borrowing
• Removing code instead of fixing ownership
• Confusing mutability with ownership