Array slices in Rust - Time & Space Complexity

Time Complexity: Array slices

O(n)

Understanding Time Complexity

When working with array slices in Rust, it's important to know how the time to access or process them changes as the slice size grows.

We want to understand how the number of operations changes when we work with slices of different lengths.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn sum_slice(slice: &[i32]) -> i32 {
    let mut total = 0;
    for &item in slice {
        total += item;
    }
    total
}

fn main() {
    let arr = [1, 2, 3, 4, 5];
    let result = sum_slice(&arr[1..4]);
    println!("Sum: {}", result);
}
    

This code sums the values in a slice of an array, iterating over the selected part only.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each element in the slice.
• How many times: Exactly once for each element in the slice.

How Execution Grows With Input

As the slice gets bigger, the number of additions grows directly with the number of elements.

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

Pattern observation: The work grows in a straight line with the slice size; doubling the slice doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to sum the slice grows directly with the number of elements in the slice.

Common Mistake

[X] Wrong: "Accessing a slice is always constant time regardless of size."

[OK] Correct: While accessing a single element by index is constant time, processing the whole slice (like summing all elements) takes time proportional to the slice length.

Interview Connect

Understanding how operations scale with slice size helps you reason about performance in real Rust programs, a skill valued in many coding challenges and interviews.

Self-Check

"What if we changed the slice to a nested slice and summed all inner slices? How would the time complexity change?"

Practice

1. What is an array slice in Rust?

easy

A. A new array created by copying elements

B. A macro to print arrays

C. A function that modifies an array

D. A reference to a part of an array without copying data

Solution

1. Step 1: Understand what a slice is

   A slice is a reference to a contiguous part of an array, not a new array.

2. Step 2: Compare options

   Only A reference to a part of an array without copying data correctly describes a slice as a reference without copying.

3. Final Answer:

   A reference to a part of an array without copying data -> Option D

4. Quick Check:

   Slice = reference to part of array [OK]

Hint: Remember: slices borrow, they don't copy [OK]

Common Mistakes:

• Thinking slices create new arrays
• Confusing slices with functions
• Assuming slices own data

2. Which of the following is the correct syntax to create a slice from an array arr in Rust?

easy

A. let slice = &arr[1..4];

B. let slice = arr.slice(1, 4);

C. let slice = arr[1:4];

D. let slice = &arr(1..4);

Solution

1. Step 1: Recall Rust slice syntax

   Rust uses &array[start..end] to create a slice referencing elements from start up to but not including end.

2. Step 2: Check each option

   let slice = &arr[1..4]; uses correct Rust syntax. Options A, B, and C use invalid syntax.

3. Final Answer:

   let slice = &arr[1..4]; -> Option A

4. Quick Check:

   Slice syntax = &arr[start..end] [OK]

Hint: Use &array[start..end] for slices [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Using colons instead of two dots
• Calling slice as a method

3. What is the output of this Rust code?

let arr = [10, 20, 30, 40, 50];
let slice = &arr[1..4];
println!("{:?}", slice);

medium

A. [30, 40, 50]

B. [10, 20, 30]

C. [20, 30, 40]

D. [1, 4]

Solution

1. Step 1: Understand the slice range

   The slice &arr[1..4] includes elements at indices 1, 2, and 3 (20, 30, 40).

2. Step 2: Check the printed output

   Printing the slice shows the elements in the slice as an array-like list.

3. Final Answer:

   [20, 30, 40] -> Option C

4. Quick Check:

   Slice arr[1..4] = [20, 30, 40] [OK]

Hint: Remember slice excludes the end index element [OK]

Common Mistakes:

• Including the element at index 4
• Starting slice at index 0
• Printing the slice as indices

4. Identify the error in this Rust code snippet:

let arr = [1, 2, 3, 4, 5];
let slice = &arr[2..6];
println!("{:?}", slice);

medium

A. The slice range goes out of bounds

B. The slice syntax is incorrect

C. The array is not mutable

D. The println! macro is used incorrectly

Solution

1. Step 1: Check the slice range

   The array has length 5, valid indices are 0 to 4. The slice uses 2..6, which tries to access index 5 (out of bounds).

2. Step 2: Identify the error type

   Rust will panic at runtime due to out-of-bounds slicing.

3. Final Answer:

   The slice range goes out of bounds -> Option A

4. Quick Check:

   Slice range must be within array length [OK]

Hint: Slice end index must be ≤ array length [OK]

Common Mistakes:

• Using an end index beyond array length
• Confusing syntax errors with runtime errors
• Assuming arrays auto-expand

5. Given a function that takes a slice of integers and returns the sum of its elements, which of the following implementations is correct?

fn sum_slice(slice: &[i32]) -> i32 {
    // fill in
}

hard

A. slice.to_vec().sum()

B. slice.iter().sum()

C. slice[0] + slice[1]

D. slice.sum()

Solution

1. Step 1: Understand slice methods

   A slice has an iterator via .iter(), and iterators have a .sum() method to add elements.

2. Step 2: Evaluate each option

   slice.iter().sum() correctly uses slice.iter().sum(). slice.to_vec().sum() is valid because Vec<i32> has sum() method. slice[0] + slice[1] only sums two elements, not all. slice.sum() is invalid because slices don't have sum() directly.

3. Final Answer:

   slice.iter().sum() -> Option B

4. Quick Check:

   Use iter().sum() to sum slice elements [OK]

Hint: Use slice.iter().sum() to sum elements [OK]

Common Mistakes:

• Trying to call sum() directly on slice
• Summing only first two elements
• Calling sum() on Vec<i32>