Array protocol and __array__ in NumPy - Time & Space Complexity

Time Complexity: Array protocol and __array__

O(n)

Understanding Time Complexity

We want to understand how fast operations run when using the array protocol and the __array__ method in numpy.

Specifically, how does the time to convert or interact with arrays grow as the data size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

class MyArray:
    def __init__(self, data):
        self.data = data
    def __array__(self, dtype=None):
        return np.array(self.data, dtype=dtype)

obj = MyArray([1, 2, 3, 4, 5])
arr = np.array(obj)

This code defines a class with a __array__ method that returns a numpy array from its data. Then numpy calls this method to create an array.

Identify Repeating Operations

Look at what repeats when numpy converts the object to an array.

• Primary operation: Copying or reading each element from the original data list to build the numpy array.
• How many times: Once for each element in the data (n times, where n is the data size).

How Execution Grows With Input

As the data size grows, the time to create the numpy array grows roughly in direct proportion.

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

Pattern observation: Doubling the input size roughly doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to convert grows linearly with the number of elements in the data.

Common Mistake

[X] Wrong: "Calling __array__ is instant and does not depend on data size."

[OK] Correct: The method creates a new numpy array by copying data, so it must look at each element, which takes time proportional to the data size.

Interview Connect

Understanding how numpy uses __array__ helps you explain how data conversion works under the hood, a useful skill when discussing performance in data science tasks.

Self-Check

What if the __array__ method returned a view instead of copying data? How would the time complexity change?