Vector vs array comparison in Rust - Performance Comparison

Time Complexity: Vector vs array comparison

O(n)

Understanding Time Complexity

When comparing a vector and an array in Rust, it's important to understand how the time it takes to compare them grows as their size increases.

We want to know how the number of steps changes when we compare these two collections element by element.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn compare_vector_array(vec: &Vec, arr: &[i32]) -> bool {
    if vec.len() != arr.len() {
        return false;
    }
    for i in 0..vec.len() {
        if vec[i] != arr[i] {
            return false;
        }
    }
    true
}
    

This code checks if a vector and an array have the same length and then compares each element one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop comparing elements at each index.
• How many times: Up to the length of the vector or array (n times).

How Execution Grows With Input

As the size of the vector and array grows, the number of comparisons grows roughly the same.

Input Size (n)	Approx. Operations
10	Up to 10 element comparisons
100	Up to 100 element comparisons
1000	Up to 1000 element comparisons

Pattern observation: The number of steps grows directly with the number of elements; doubling the size roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to compare grows linearly with the number of elements in the vector and array.

Common Mistake

[X] Wrong: "Comparing a vector and an array is always constant time because they are fixed size."

[OK] Correct: Even if the sizes are fixed, the program must check each element to be sure they are equal, so the time depends on the number of elements.

Interview Connect

Understanding how element-wise comparison scales helps you reason about performance in real programs, especially when working with collections of data.

Self-Check

"What if we compared only the first element instead of all elements? How would the time complexity change?"

Practice

1. Which of the following statements correctly describes the main difference between a Rust array and a Rust vector?

easy

A. Arrays have a fixed size known at compile time, while vectors can grow or shrink at runtime.

B. Vectors have a fixed size known at compile time, while arrays can grow or shrink at runtime.

C. Both arrays and vectors have fixed sizes and cannot change after creation.

D. Arrays are only used for strings, while vectors are used for numbers.

Solution

1. Step 1: Understand array size behavior

   Arrays in Rust have a fixed size that must be known when the program is compiled.

2. Step 2: Understand vector size behavior

   Vectors are dynamic and can grow or shrink during program execution.

3. Final Answer:

   Arrays have a fixed size known at compile time, while vectors can grow or shrink at runtime. -> Option A

4. Quick Check:

   Array fixed size, Vector dynamic size = C [OK]

Hint: Remember: arrays fixed size, vectors flexible size [OK]

Common Mistakes:

• Confusing which type is fixed or dynamic
• Thinking vectors are fixed size
• Assuming arrays can grow dynamically

2. Which of the following is the correct syntax to declare a vector of integers in Rust?

easy

A. let v = (1, 2, 3);

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

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

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

Solution

1. Step 1: Identify vector creation syntax

   In Rust, vectors are created using the macro vec![...] with square brackets and exclamation mark.

2. Step 2: Compare options

   let v = vec![1, 2, 3]; uses vec![1, 2, 3], which is correct. let v = [1, 2, 3]; is an array, C and D are invalid syntax for vectors.

3. Final Answer:

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

4. Quick Check:

   Vector syntax uses vec! macro = A [OK]

Hint: Vectors use vec! macro with square brackets [OK]

Common Mistakes:

• Using array syntax instead of vec! macro
• Missing exclamation mark in vec! macro
• Using parentheses instead of brackets

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

let arr = [10, 20, 30];
let vec = vec![10, 20, 30];
println!("{} {}", arr.len(), vec.len());

medium

A. 3 0

B. 3 3

C. 0 3

D. Compilation error

Solution

1. Step 1: Check array length

   The array arr has 3 elements, so arr.len() returns 3.

2. Step 2: Check vector length

   The vector vec also has 3 elements, so vec.len() returns 3.

3. Final Answer:

   3 3 -> Option B

4. Quick Check:

   Both lengths are 3 = B [OK]

Hint: Both array and vector have length 3 here [OK]

Common Mistakes:

• Assuming vector length is zero initially
• Confusing array and vector length methods
• Expecting compilation error due to different types

4. Identify the error in this Rust code snippet:

let arr = [1, 2, 3];
arr.push(4);

medium

A. Arrays do not have a push method; only vectors do.

B. The array is missing a semicolon after declaration.

C. The push method requires a mutable reference to the array.

D. The code is correct and will compile.

Solution

1. Step 1: Check array methods

   Arrays in Rust have fixed size and do not support the push method.

2. Step 2: Understand push method usage

   The push method is only available for vectors, which are growable.

3. Final Answer:

   Arrays do not have a push method; only vectors do. -> Option A

4. Quick Check:

   push() only works on vectors = D [OK]

Hint: Only vectors support push(), arrays do not [OK]

Common Mistakes:

• Trying to push to arrays
• Thinking arrays can be resized
• Ignoring method availability on types

5. You want to store a list of user scores that can change size during the program. Which Rust type should you choose and why?

hard

A. Use a tuple because it can hold multiple types of scores.

B. Use an array because it is faster and fixed size is better for scores.

C. Use a vector because it can grow or shrink as scores are added or removed.

D. Use a string because scores are numbers stored as text.

Solution

1. Step 1: Analyze data size requirement

   The list of user scores can change size, so a fixed size container is not suitable.

2. Step 2: Choose appropriate Rust type

   Vectors are growable and flexible, making them ideal for dynamic lists like scores.

3. Final Answer:

   Use a vector because it can grow or shrink as scores are added or removed. -> Option C

4. Quick Check:

   Dynamic list needs vector = A [OK]

Hint: Dynamic size needs vector, fixed size needs array [OK]

Common Mistakes:

• Choosing array for dynamic data
• Confusing tuples with lists
• Using string for numeric data