Array basics in Rust - Time & Space Complexity

Time Complexity: Array basics

O(n)

Understanding Time Complexity

When working with arrays, it is important to know how the time to do tasks changes as the array gets bigger.

We want to find out how the number of steps grows when we do simple operations on arrays.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn sum_array(arr: &[i32]) -> i32 {
    let mut total = 0;
    for &num in arr.iter() {
        total += num;
    }
    total
}
    

This code adds up all the numbers in an array and returns the total sum.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each number to the total inside a loop.
• How many times: Once for every item in the array.

How Execution Grows With Input

As the array gets bigger, the number of additions grows at the same rate.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

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

Final Time Complexity

Time Complexity: O(n)

This means if the array doubles in size, the time to add all numbers roughly doubles too.

Common Mistake

[X] Wrong: "Adding all numbers in an array takes the same time no matter how big the array is."

[OK] Correct: The loop must visit each item, so more items mean more steps and more time.

Interview Connect

Understanding how simple loops over arrays grow with input size is a key skill that helps you reason about more complex code.

Self-Check

"What if we only summed the first half of the array? How would the time complexity change?"

Practice

1. What is true about arrays in Rust?

easy

A. Their size can change after creation.

B. They store multiple values of the same type in a fixed-size list.

C. They can store values of different types together.

D. They do not allow access by index.

Solution

1. Step 1: Understand array type restrictions

   Arrays in Rust hold values all of the same type, ensuring type safety.

2. Step 2: Understand array size behavior

   Arrays have a fixed size that cannot be changed after creation.

3. Final Answer:

   They store multiple values of the same type in a fixed-size list. -> Option B

4. Quick Check:

   Array = fixed size + same type [OK]

Hint: Remember: Rust arrays are fixed size and single type [OK]

Common Mistakes:

• Thinking arrays can hold mixed types
• Assuming arrays can grow or shrink
• Believing arrays don't use indexes

2. Which of the following is the correct way to declare an array of 3 integers in Rust?

easy

A. let arr = [1, 2, 3];

B. let arr = (1, 2, 3);

C. let arr = {1, 2, 3};

D. let arr = <1, 2, 3>;

Solution

1. Step 1: Identify Rust array syntax

   Arrays use square brackets [] with comma-separated values.

2. Step 2: Check other options

   Parentheses () create tuples, curly braces {} are blocks, angle brackets <> are not valid here.

3. Final Answer:

   let arr = [1, 2, 3]; -> Option A

4. Quick Check:

   Array syntax uses [] [OK]

Hint: Arrays use square brackets [] with commas [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Confusing arrays with tuples
• Using invalid symbols like {} or <>

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

let arr = [10, 20, 30, 40];
println!("{}", arr[2]);

medium

A. Index out of bounds error

B. 20

C. 40

D. 30

Solution

1. Step 1: Understand array indexing

   Rust arrays start indexing at 0, so arr[2] is the third element.

2. Step 2: Identify the element at index 2

   The elements are [10, 20, 30, 40], so arr[2] is 30.

3. Final Answer:

   30 -> Option D

4. Quick Check:

   Index 2 = 30 [OK]

Hint: Count from zero to find the correct index [OK]

Common Mistakes:

• Starting count at 1 instead of 0
• Confusing element positions
• Expecting runtime error for valid index

4. Find the error in this Rust code snippet:

let arr = [1, 2, 3];
println!("{}", arr[3]);

medium

A. No error, prints 3

B. Type mismatch error

C. Index out of bounds error at runtime

D. Syntax error due to missing semicolon

Solution

1. Step 1: Check array length and index used

   The array has 3 elements with indexes 0, 1, 2. Index 3 is invalid.

2. Step 2: Understand Rust runtime behavior

   Accessing arr[3] causes a runtime panic due to index out of bounds.

3. Final Answer:

   Index out of bounds error at runtime -> Option C

4. Quick Check:

   Invalid index causes runtime panic [OK]

Hint: Check if index is less than array length [OK]

Common Mistakes:

• Assuming index 3 is valid for 3-element array
• Confusing syntax error with runtime error
• Ignoring Rust's panic on invalid index

5. You want to create an array of 5 zeros in Rust. Which code correctly does this?

hard

A. let arr = [0; 5];

B. let arr = [0, 5];

C. let arr = [5; 0];

D. let arr = [0] * 5;

Solution

1. Step 1: Understand Rust array repetition syntax

   The syntax [value; count] creates an array repeating value count times.

2. Step 2: Check each option

   let arr = [0; 5]; uses [0; 5], which creates 5 zeros. Others are invalid or create wrong arrays.

3. Final Answer:

   let arr = [0; 5]; -> Option A

4. Quick Check:

   Use [value; count] to repeat values [OK]

Hint: Use [value; count] to make repeated arrays [OK]

Common Mistakes:

• Using commas instead of semicolon for repetition
• Confusing multiplication syntax with arrays
• Reversing value and count in repetition