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?