Broadcasting rules in NumPy - Time & Space Complexity

Time Complexity: Broadcasting rules

O(n x m)

Understanding Time Complexity

We want to understand how the time needed to run numpy operations changes when using broadcasting.

Specifically, how does numpy handle operations on arrays of different shapes efficiently?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr1 = np.ones((1000, 1))
arr2 = np.ones((1, 500))
result = arr1 + arr2

This code adds two arrays with different shapes using broadcasting to create a (1000, 500) result.

Identify Repeating Operations

Look at what repeats when numpy adds these arrays.

• Primary operation: Adding each element in the resulting 2D array.
• How many times: Once for every element in the output array (1000 rows x 500 columns = 500,000 times).

How Execution Grows With Input

As the size of the arrays grows, the number of additions grows with the total number of elements in the broadcasted shape.

Input Size (n)	Approx. Operations
10 (10x10)	100
100 (100x100)	10,000
1000 (1000x1000)	1,000,000

Pattern observation: The operations grow roughly with the total number of elements in the broadcasted array, which is the product of its dimensions.

Final Time Complexity

Time Complexity: O(n x m)

This means the time grows proportional to the total number of elements in the broadcasted output array.

Common Mistake

[X] Wrong: "Broadcasting makes the operation run only as fast as the smaller array size."

[OK] Correct: Even though numpy uses broadcasting to avoid copying data, the operation still processes every element in the final output array, so time depends on the full broadcasted size.

Interview Connect

Understanding broadcasting time helps you explain how numpy handles large data efficiently and why some operations take longer depending on array shapes.

Self-Check

"What if we changed the smaller array to have the same shape as the larger one? How would the time complexity change?"