Ownership and functions in Rust - Time & Space Complexity

Time Complexity: Ownership and functions

O(n)

Understanding Time Complexity

When we use ownership in Rust functions, it affects how many steps the program takes to run.

We want to see how the program's work changes as the input size grows when ownership moves between functions.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

fn main() {
    let data = String::from("hello");
    takes_ownership(data);
}
    

This code moves ownership of a string to a function, which then prints it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calling the function once with ownership moved.
• How many times: Exactly one time in this example.

How Execution Grows With Input

As the size of the string grows, the time to print grows roughly in proportion to the string length.

Input Size (n)	Approx. Operations
10	About 10 steps to handle the string data
100	About 100 steps
1000	About 1000 steps

Pattern observation: The work grows directly with the size of the input string.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line as the input string gets bigger.

Common Mistake

[X] Wrong: "Moving ownership is free and does not depend on input size."

[OK] Correct: Moving ownership of a large string is actually a constant time operation because Rust moves the pointer, length, and capacity without copying the data. However, printing the string takes time proportional to its length.

Interview Connect

Understanding how ownership affects time helps you explain Rust code clearly and shows you know how data moves in programs.

Self-Check

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

Practice

1. What happens when a function in Rust takes ownership of a variable passed to it?

easy

A. The variable is shared between the function and the caller simultaneously.

B. The variable is copied and both original and function have ownership.

C. The function borrows the variable temporarily without taking ownership.

D. The original variable can no longer be used after the function call.

Solution

1. Step 1: Understand ownership transfer in Rust functions

   When a function takes ownership, it means the variable's ownership moves to the function.

2. Step 2: Effect on original variable after function call

   Since ownership moved, the original variable cannot be used anymore after the call.

3. Final Answer:

   The original variable can no longer be used after the function call. -> Option D

4. Quick Check:

   Ownership transfer = original variable unusable [OK]

Hint: Ownership moves to function, original variable becomes invalid [OK]

Common Mistakes:

• Thinking ownership is shared, not moved
• Assuming variable is copied automatically
• Confusing borrowing with ownership transfer

2. Which of the following function signatures correctly borrows a string slice without taking ownership?

easy

A. fn print_name(name: String) { println!("{}", name); }

B. fn print_name(name: &String) { println!("{}", name); }

C. fn print_name(name: &str) { println!("{}", name); }

D. fn print_name(name: String) -> String { name }

Solution

1. Step 1: Identify borrowing syntax for string slices

   Borrowing a string slice uses &str type, which is a reference to a string slice.

2. Step 2: Check each signature for borrowing without ownership

   fn print_name(name: &str) { println!("{}", name); } uses &str, which borrows without taking ownership. fn print_name(name: &String) { println!("{}", name); } borrows a String reference but &str is more idiomatic for slices.

3. Final Answer:

   fn print_name(name: &str) { println!("{}", name); } -> Option C

4. Quick Check:

   Borrow string slice = &str parameter [OK]

Hint: Use &str to borrow string slices without ownership [OK]

Common Mistakes:

• Using String parameter takes ownership
• Confusing &String with &str
• Returning ownership when not needed

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

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

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

medium

A. Inside function: hello
Compile error: use of moved value 's'

B. Inside function: hello
Outside function: hello

C. Inside function: hello
Outside function: <empty>

D. Runtime error: variable s not found

Solution

1. Step 1: Analyze ownership transfer in function call

   The function take_ownership takes ownership of s, so s is moved into the function.

2. Step 2: Check usage of s after function call

   After the call, s is no longer valid in main, so using it causes a compile error.

3. Final Answer:

   Inside function: hello Compile error: use of moved value 's' -> Option A

4. Quick Check:

   Ownership moved, use after move = compile error [OK]

Hint: Using moved variable after function call causes compile error [OK]

Common Mistakes:

• Assuming variable is copied automatically
• Expecting output after ownership moved
• Ignoring Rust's ownership rules

4. Identify the error in this Rust code and how to fix it:

fn calculate_length(s: String) -> usize {
    s.len()
}

fn main() {
    let s1 = String::from("hello");
    let len = calculate_length(s1);
    println!("The length of '{}' is {}.", s1, len);
}

medium

A. Error: s1 is moved into calculate_length; fix by passing &s1 instead.

B. Error: calculate_length returns wrong type; fix by returning &usize.

C. Error: println! macro syntax incorrect; fix by removing quotes.

D. No error; code runs and prints length correctly.

Solution

1. Step 1: Identify ownership issue in function call

   calculate_length takes ownership of s1, so s1 is moved and invalid after call.

2. Step 2: Fix by borrowing s1 instead of moving

   Change function parameter to &String and pass &s1 to avoid moving ownership.

3. Final Answer:

   Error: s1 is moved into calculate_length; fix by passing &s1 instead. -> Option A

4. Quick Check:

   Pass reference to avoid moving ownership [OK]

Hint: Pass references to keep ownership when calling functions [OK]

Common Mistakes:

• Trying to return reference to local variable
• Ignoring ownership move on function parameters
• Misunderstanding borrowing syntax

5. You want to write a function that takes ownership of a vector, doubles each element, and returns ownership back. Which function signature and body correctly implement this in Rust?

hard

A. fn double_vec(v: &Vec<i32>) -> Vec<i32> { v.iter().map(|x| x * 2).collect() }

B. fn double_vec(v: Vec<i32>) -> Vec<i32> { v.iter().map(|x| x * 2).collect() }

C. fn double_vec(v: Vec<i32>) { for x in &v { println!("{}", x * 2); } }

D. fn double_vec(v: &mut Vec<i32>) { for x in v { *x *= 2; } }

Solution

1. Step 1: Understand ownership and return requirements

   The function must take ownership of the vector and return ownership back after doubling elements.

2. Step 2: Analyze each option for ownership and functionality

   fn double_vec(v: Vec<i32>) -> Vec<i32> { v.iter().map(|x| x * 2).collect() } takes ownership (Vec<i32>), creates a new doubled vector, and returns it, satisfying requirements.

3. Final Answer:

   fn double_vec(v: Vec<i32>) -> Vec<i32> { v.iter().map(|x| x * 2).collect() } -> Option B

4. Quick Check:

   Take ownership, return new doubled vector [OK]

Hint: Take Vec ownership and return new Vec after processing [OK]

Common Mistakes:

• Borrowing vector but not returning ownership
• Not returning anything from function
• Modifying borrowed vector without ownership