Adding elements to vectors in Rust - Time & Space Complexity

Time Complexity: Adding elements to vectors

O(n)

Understanding Time Complexity

When we add elements to a vector in Rust, it is important to know how the time it takes changes as the vector grows.

We want to understand how the cost of adding elements grows when the vector gets bigger.

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

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

How Execution Grows With Input

Each element is added one after another. Most adds are quick, but sometimes the vector needs to grow its storage, which takes more time.

Input Size (n)	Approx. Operations
10	About 10 simple adds, with a few extra steps for resizing
100	About 100 adds, with a few resizing steps spread out
1000	About 1000 adds, resizing happens a few times but not every add

Pattern observation: Most adds are quick, but occasionally the vector grows bigger, which costs more time. Overall, the time grows roughly in a straight line with n.

Final Time Complexity

Time Complexity: O(n)

This means adding n elements takes time roughly proportional to n, growing steadily as more elements are added.

Common Mistake

[X] Wrong: "Each push always takes the same small amount of time."

[OK] Correct: Sometimes the vector needs to resize its storage, which takes extra time. But these resizing steps happen rarely enough that the average time per push stays low.

Interview Connect

Understanding how adding elements to a vector scales helps you reason about performance in many programs. It shows you how data structures behave as they grow, a useful skill for writing efficient code.

Self-Check

"What if we used a linked list instead of a vector? How would the time complexity of adding elements change?"

Practice

1. What does the push method do when used on a Rust vector?

easy

A. Removes the last element from the vector

B. Adds a new element to the end of the vector

C. Creates a new vector with one element

D. Sorts the elements in the vector

Solution

1. Step 1: Understand the purpose of push

   The push method is used to add elements to a vector in Rust.

2. Step 2: Identify what push does specifically

   It adds a new element to the end of the vector, increasing its size by one.

3. Final Answer:

   Adds a new element to the end of the vector -> Option B

4. Quick Check:

   push adds element [OK]

Hint: Remember: push always adds at the end [OK]

Common Mistakes:

• Confusing push with pop (which removes elements)
• Thinking push creates a new vector
• Assuming push sorts the vector

2. Which of the following is the correct way to declare a mutable vector and add the number 10 to it in Rust?

easy

A. let v = Vec::new(); v.add(10);

B. let v = Vec::new(); v.push(10);

C. let mut v = Vec::new(); v.add(10);

D. let mut v = Vec::new(); v.push(10);

Solution

1. Step 1: Check vector mutability

   To add elements, the vector must be mutable, so let mut v is required.

2. Step 2: Use correct method to add element

   The method to add an element is push, not add.

3. Final Answer:

   let mut v = Vec::new(); v.push(10); -> Option D

4. Quick Check:

   Mutable vector + push method [OK]

Hint: Mutable vector + push method adds elements [OK]

Common Mistakes:

• Forgetting to make the vector mutable
• Using a non-existent method like add
• Trying to push on an immutable vector

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

let mut v = vec![1, 2];
v.push(3);
println!("{:?}", v);

medium

A. [1, 2]

B. Compilation error

C. [1, 2, 3]

D. [3, 1, 2]

Solution

1. Step 1: Understand initial vector content

   The vector starts with elements [1, 2].

2. Step 2: Apply the push method

   The push(3) adds 3 at the end, so vector becomes [1, 2, 3].

3. Final Answer:

   [1, 2, 3] -> Option C

4. Quick Check:

   push adds element at end [OK]

Hint: push adds element at the end of vector [OK]

Common Mistakes:

• Expecting push to add at the start
• Thinking push replaces elements
• Assuming code causes error

4. Identify the error in this Rust code snippet:

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

medium

A. Vector is not mutable, so push cannot be called

B. push method does not exist for vectors

C. Vec::new() cannot create an empty vector

D. Missing semicolon after Vec::new()

Solution

1. Step 1: Check vector mutability

   The vector is declared as immutable with let v, so it cannot be changed.

2. Step 2: Understand push method requirements

   The push method requires the vector to be mutable to add elements.

3. Final Answer:

   Vector is not mutable, so push cannot be called -> Option A

4. Quick Check:

   push needs mutable vector [OK]

Hint: Make vector mutable to use push [OK]

Common Mistakes:

• Assuming push works on immutable vectors
• Thinking Vec::new() is invalid
• Ignoring mut keyword necessity

5. You want to add multiple elements [4, 5, 6] to an existing mutable vector v. Which code correctly adds all these elements efficiently?

hard

A. v.extend([4, 5, 6]);

B. v.push(4, 5, 6);

C. v.add([4, 5, 6]);

D. v.push([4, 5, 6]);

Solution

1. Step 1: Understand adding multiple elements

   Using push adds one element at a time, so multiple calls are needed for multiple elements.

2. Step 2: Use the efficient method for multiple elements

   The extend method adds all elements from an iterable at once, which is more efficient.

3. Final Answer:

   v.extend([4, 5, 6]); -> Option A

4. Quick Check:

   Use extend for multiple elements [OK]

Hint: Use extend to add many elements at once [OK]

Common Mistakes:

• Using push with a whole array (causes error)
• Using non-existent add method
• Calling push multiple times instead of extend