Strides and how data is accessed in NumPy - Time & Space Complexity

Time Complexity: Strides and how data is accessed

O(n^2)

Understanding Time Complexity

When working with numpy arrays, how data is accessed matters for speed.

We want to see how the way numpy reads data affects the time it takes.

Scenario Under Consideration

Analyze the time complexity of the following numpy code snippet.

import numpy as np

arr = np.arange(10000).reshape(100, 100)
sub_arr = arr[:, ::2]
result = np.sum(sub_arr)

This code creates a 100x100 array, takes every second column, then sums all values.

Identify Repeating Operations

Look for repeated steps that take most time.

• Primary operation: Summing all elements in the sliced array.
• How many times: Once for each element in the sliced array (100 rows x 50 columns = 5000 elements).

How Execution Grows With Input

As the array size grows, the sum operation takes longer because it reads more elements.

Input Size (n x n)	Approx. Operations (sum elements)
10 x 10	50 (half columns)
100 x 100	5,000
1000 x 1000	500,000

Pattern observation: Operations grow roughly with the number of elements accessed, which depends on the slice size.

Final Time Complexity

Time Complexity: O(n^2)

This means the time grows roughly with the total number of elements accessed in the sliced array.

Common Mistake

[X] Wrong: "Slicing with steps like ::2 makes the operation twice as fast always."

[OK] Correct: Even with slicing, numpy still reads each accessed element, so time depends on how many elements are included, not just the step size.

Interview Connect

Understanding how numpy accesses data helps you write faster code and explain performance clearly in interviews.

Self-Check

What if we changed the slice to arr[::2, ::2]? How would the time complexity change?

Practice

1. What do strides in a NumPy array represent?

easy

A. The number of bytes to jump to move to the next element in each dimension

B. The total number of elements in the array

C. The shape of the array

D. The data type of the array elements

Solution

1. Step 1: Understand the definition of strides

   Strides indicate how many bytes NumPy moves in memory to access the next element along each dimension.

2. Step 2: Differentiate from other array attributes

   Shape is the size per dimension, dtype is the data type, and total elements is the count, none describe memory jumps.

3. Final Answer:

   The number of bytes to jump to move to the next element in each dimension -> Option A

4. Quick Check:

   Strides = bytes jump per dimension [OK]

Hint: Strides = byte steps to next element per dimension [OK]

Common Mistakes:

• Confusing strides with shape
• Thinking strides represent element count
• Mixing strides with data type size

2. Which of the following is the correct way to check the strides of a NumPy array arr?

easy

A. arr.strides()

B. arr.strides

C. arr.get_strides()

D. strides(arr)

Solution

1. Step 1: Recall how strides are accessed in NumPy

   Strides is an attribute, not a method, so it is accessed without parentheses.

2. Step 2: Evaluate each option

   arr.strides() and C use parentheses incorrectly; strides(arr) is not a valid function; arr.strides correctly accesses the attribute.

3. Final Answer:

   arr.strides -> Option B

4. Quick Check:

   Strides is an attribute, no parentheses [OK]

Hint: Use attribute, not method: arr.strides [OK]

Common Mistakes:

• Using parentheses like a method
• Trying non-existent functions
• Confusing strides with shape attribute

3. Given the code:

import numpy as np
arr = np.array([[1, 2, 3], [4, 5, 6]])
slice_arr = arr[:, 1:3]

What will slice_arr.strides most likely be if arr.strides is (24, 8)?

medium

A. (24, 16)

B. (24, 8) but reversed

C. (24, 8)

D. (24, 8) but with first stride changed to 8

Solution

1. Step 1: Understand original strides meaning

   Original strides (24, 8) mean 24 bytes to move to next row, 8 bytes to next column.

2. Step 2: Analyze slicing effect on strides

   Slicing [:, 1:3] uses step=1 for columns (equivalent to 1:3:1), so both row stride (24) and column stride (8) remain unchanged.

3. Final Answer:

   (24, 8) -> Option C

4. Quick Check:

   Step=1 slicing keeps strides unchanged [OK]

Hint: Step=1 slicing keeps strides unchanged [OK]

Common Mistakes:

• Thinking non-zero start changes strides
• Believing column slicing doubles stride
• Confusing with step>1 strided slicing

4. Consider this code snippet:

import numpy as np
arr = np.arange(12).reshape(3,4)
sub_arr = arr[::2, ::-1]
print(sub_arr.strides)

It raises an error. What is the likely cause?

medium

A. Negative step in slicing causes invalid strides

B. Using step size 2 in slicing is not allowed

C. Slicing with negative step reverses strides but is valid

D. No error; code runs fine

Solution

1. Step 1: Understand slicing with steps

   The code uses [::2, ::-1]: step=2 for rows (valid), step=-1 for columns (valid, reverses dimension).

2. Step 2: Check if code runs

   NumPy supports all integer steps including negative; strides adjust (row *=2, col *=-1), no error occurs.

3. Final Answer:

   No error; code runs fine -> Option D

4. Quick Check:

   Negative step reverses strides, no error [OK]

Hint: Negative slice steps reverse strides, no error [OK]

Common Mistakes:

• Assuming negative steps cause errors
• Thinking step size 2 is invalid
• Confusing stride reversal with error

5. You have a large 2D NumPy array data with shape (1000, 1000) and strides (8000, 8). You want to create a view that selects every 10th row and every 5th column without copying data. What will be the strides of this view?

hard

A. (80000, 40)

B. (8000, 8)

C. (8000, 40)

D. (80000, 8)

Solution

1. Step 1: Understand original strides

   Original strides (8000, 8) mean 8000 bytes to move one row, 8 bytes to move one column.

2. Step 2: Calculate new strides after slicing

   Selecting every 10th row multiplies row stride by 10 -> 8000*10=80000; every 5th column multiplies column stride by 5 -> 8*5=40.

3. Final Answer:

   (80000, 40) -> Option A

4. Quick Check:

   Stride scales by step size in slicing [OK]

Hint: Multiply strides by slice step size [OK]

Common Mistakes:

• Forgetting to multiply strides by step size
• Mixing row and column strides
• Assuming strides stay unchanged after slicing