Vector creation in Rust - Time & Space Complexity

Time Complexity: Vector creation

O(n)

Understanding Time Complexity

When we create a vector in Rust, it is important to know how the time it takes grows as the vector gets bigger.

We want to understand how the work changes when we add more items to the vector.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

let mut v = Vec::new();
for i in 0..n {
    v.push(i);
}
    

This code creates an empty vector and adds numbers from 0 up to n-1 one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding an element to the vector with push.
• How many times: Exactly n times, once for each number from 0 to n-1.

How Execution Grows With Input

Each new item is added one after another, so the total work grows as we add more items.

Input Size (n)	Approx. Operations
10	About 10 push operations
100	About 100 push operations
1000	About 1000 push operations

Pattern observation: The work grows directly with the number of items added.

Final Time Complexity

Time Complexity: O(n)

This means the time to create the vector grows in a straight line as we add more items.

Common Mistake

[X] Wrong: "Adding each item takes a lot longer because the vector must copy all items every time."

[OK] Correct: Rust vectors allocate extra space ahead of time, so most push operations are quick and do not copy all items every time.

Interview Connect

Understanding how vector creation time grows helps you explain how data structures work behind the scenes, a useful skill in many programming tasks.

Self-Check

What if we used Vec::with_capacity(n) before the loop? How would the time complexity change?

Practice

1. Which of the following correctly creates an empty vector of integers in Rust?

easy

A. let v: Vec<i32> = Vec::new();

B. let v = vec!();

C. let v = Vector::new();

D. let v = vec![0];

Solution

1. Step 1: Understand how to create an empty vector

   In Rust, an empty vector is created using Vec::new() with the type specified if needed.

2. Step 2: Check each option

   let v: Vec<i32> = Vec::new(); uses Vec::new() with type i32, which is correct. let v = vec!(); uses vec!() which is invalid syntax. let v = Vector::new(); uses Vector::new() which is not a Rust type. let v = vec![0]; creates a vector with one element 0, not empty.

3. Final Answer:

   let v: Vec<i32> = Vec::new(); -> Option A

4. Quick Check:

   Empty vector = Vec::new() [OK]

Hint: Empty vector uses Vec::new() with type [OK]

Common Mistakes:

• Using vec!() with empty parentheses
• Using Vector instead of Vec
• Creating vector with one element instead of empty

2. Which syntax correctly creates a vector with the values 1, 2, and 3 in Rust?

easy

A. let v = vec{1, 2, 3};

B. let v = Vec[1, 2, 3];

C. let v = vec(1, 2, 3);

D. let v = vec![1, 2, 3];

Solution

1. Step 1: Recall vector creation with values

   Rust uses the macro vec![...] with square brackets and exclamation mark to create vectors with initial values.

2. Step 2: Evaluate each option

   let v = vec![1, 2, 3]; uses correct syntax vec![1, 2, 3]. let v = Vec[1, 2, 3]; uses square brackets without exclamation mark, invalid. let v = vec(1, 2, 3); uses parentheses, invalid. let v = vec{1, 2, 3}; uses curly braces, invalid.

3. Final Answer:

   let v = vec![1, 2, 3]; -> Option D

4. Quick Check:

   Vector with values = vec![...] [OK]

Hint: Use vec! macro with square brackets for values [OK]

Common Mistakes:

• Missing exclamation mark after vec
• Using parentheses or curly braces instead of brackets
• Using Vec[...] which is invalid syntax

3. What is the output of this Rust code?

let mut v = Vec::new();
v.push(10);
v.push(20);
println!("{:?}", v);

medium

A. [10, 20]

B. [20, 10]

C. 10 20

D. Error: cannot push to vector

Solution

1. Step 1: Understand vector push operations

   The vector starts empty. push(10) adds 10 at the end, then push(20) adds 20 after 10.

2. Step 2: Check the printed output

   The println!("{:?}", v) prints the vector in debug format showing all elements in order: [10, 20].

3. Final Answer:

   [10, 20] -> Option A

4. Quick Check:

   Push adds elements in order [OK]

Hint: push adds elements at the end, print shows all [OK]

Common Mistakes:

• Assuming push adds at the front
• Printing vector without debug format
• Confusing order of elements

4. Identify the error in this Rust code snippet:

let v = Vec::new();
v.push(5);

medium

A. push method does not exist for vectors

B. Vec::new() does not create a vector

C. Cannot push to an immutable vector

D. Missing semicolon after Vec::new()

Solution

1. Step 1: Check vector mutability

   The vector v is declared without mut, so it is immutable by default.

2. Step 2: Understand push method requirements

   The push method requires the vector to be mutable to add elements. Trying to push to an immutable vector causes a compile error.

3. Final Answer:

   Cannot push to an immutable vector -> Option C

4. Quick Check:

   push needs mutable vector [OK]

Hint: Add mut to vector to allow push [OK]

Common Mistakes:

• Forgetting mut keyword
• Thinking Vec::new() returns non-vector
• Assuming push works on immutable vectors

5. You want to create a vector of strings from an array of &str slices and then add a new string. Which code correctly does this?

hard

A. let v = vec!["a", "b", "c"]; v.push("d");

B. let mut v: Vec<String> = ["a", "b", "c"].iter().map(|&s| s.to_string()).collect(); v.push("d".to_string());

C. let mut v = Vec::new(); v.push(["a", "b", "c"]); v.push("d");

D. let mut v = vec![String::from("a"), String::from("b"), String::from("c")]; v.push('d');

Solution

1. Step 1: Convert &str slices to String vector

   The array of &str slices needs to be converted to a vector of String using iter(), map() with to_string(), then collect().

2. Step 2: Add a new String element

   After creating a mutable vector, use push with "d".to_string() to add a new string.

3. Step 3: Check other options

   let v = vec!["a", "b", "c"]; v.push("d"); tries to push to an immutable vector of &str slices, invalid. let mut v = Vec::new(); v.push(["a", "b", "c"]); v.push("d"); tries to push an array inside vector, invalid. let mut v = vec![String::from("a"), String::from("b"), String::from("c")]; v.push('d'); pushes a char instead of String, invalid.

4. Final Answer:

   let mut v: Vec<String> = ["a", "b", "c"].iter().map(|&s| s.to_string()).collect(); v.push("d".to_string()); -> Option B

5. Quick Check:

   Convert slices to String vector, then push String [OK]

Hint: Map &str to String, collect to Vec<String>, then push [OK]

Common Mistakes:

• Trying to push to immutable vector
• Pushing wrong types (char instead of String)
• Not converting &str slices to String