Contiguous memory layout concept in NumPy - Time & Space Complexity

Time Complexity: Contiguous memory layout concept

O(n)

Understanding Time Complexity

We want to understand how the way data is stored in memory affects the speed of operations in numpy.

Specifically, how does contiguous memory layout impact the time it takes to access or process data?

Scenario Under Consideration

Analyze the time complexity of accessing elements in a numpy array with contiguous memory.

import numpy as np

arr = np.arange(1000000)  # Create a large 1D array
sum_val = 0
for i in range(len(arr)):
    sum_val += arr[i]

This code sums all elements in a large numpy array stored contiguously in memory.

Identify Repeating Operations

Look at what repeats as the input grows.

• Primary operation: Accessing each element in the array once.
• How many times: Exactly once per element, so n times for n elements.

How Execution Grows With Input

As the array size grows, the number of element accesses grows linearly.

Input Size (n)	Approx. Operations
10	10 element accesses
100	100 element accesses
1000	1000 element accesses

Pattern observation: The operations increase directly with input size, one per element.

Final Time Complexity

Time Complexity: O(n)

This means the time to sum elements grows in a straight line as the array gets bigger.

Common Mistake

[X] Wrong: "Accessing elements in a numpy array is always slow because it's Python code."

[OK] Correct: Numpy arrays are stored in contiguous memory, so accessing elements is fast and efficient, much faster than Python lists for large data.

Interview Connect

Understanding how data layout affects speed shows you know why numpy is fast and how to write efficient code.

Self-Check

"What if the numpy array was not stored contiguously? How would that affect the time complexity of accessing elements?"