Contiguous arrays and stride tricks in NumPy - Time & Space Complexity

Time Complexity: Contiguous arrays and stride tricks

O(n)

Understanding Time Complexity

We want to understand how accessing and manipulating contiguous arrays using stride tricks affects the time it takes to run code.

How does the way data is stored and accessed change the work done as the array grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr = np.arange(1000000)
window_size = 5

# Create a sliding window view using stride tricks
windows = np.lib.stride_tricks.sliding_window_view(arr, window_size)

# Sum each window
result = windows.sum(axis=1)

This code creates overlapping windows of size 5 over a large array and sums each window.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Summing each window of size 5 across the array.
• How many times: The sum operation repeats once for each window, about n - window_size + 1 times.

How Execution Grows With Input

As the array size grows, the number of windows grows roughly the same as the array length, so the total work grows proportionally.

Input Size (n)	Approx. Operations
10	~6 sums of 5 elements each = 30 operations
100	~96 sums of 5 elements each = 480 operations
1000	~996 sums of 5 elements each = 4980 operations

Pattern observation: The total operations increase roughly linearly with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to sum all windows grows in direct proportion to the size of the input array.

Common Mistake

[X] Wrong: "Using stride tricks makes the operation constant time regardless of input size."

[OK] Correct: Stride tricks create views without copying data, but summing each window still requires visiting each element, so time grows with input size.

Interview Connect

Understanding how data layout and views affect performance helps you write efficient code and explain your choices clearly in interviews.

Self-Check

What if we changed the window size to grow with the input size? How would the time complexity change?