1D and 2D broadcasting in NumPy - Time & Space Complexity

Time Complexity: 1D and 2D broadcasting

O(n*m)

Understanding Time Complexity

We want to understand how the time needed to run broadcasting operations grows as the size of arrays increases.

How does numpy handle operations between arrays of different shapes efficiently?

Scenario Under Consideration

Analyze the time complexity of the following numpy broadcasting code.

import numpy as np

arr_2d = np.ones((1000, 1000))
arr_1d = np.arange(1000)

result = arr_2d + arr_1d

This code adds a 1D array to each row of a 2D array using broadcasting.

Identify Repeating Operations

Look at what repeats when numpy adds these arrays.

• Primary operation: Adding each element of the 1D array to each element in every row of the 2D array.
• How many times: For each of the 1000 rows, 1000 additions happen, so 1,000 x 1,000 = 1,000,000 additions.

How Execution Grows With Input

As the size of the arrays grows, the number of additions grows quickly.

Input Size (n)	Approx. Operations
10	10 x 10 = 100 additions
100	100 x 100 = 10,000 additions
1000	1000 x 1000 = 1,000,000 additions

Pattern observation: The operations grow roughly with the square of the input size.

Final Time Complexity

Time Complexity: O(n*m)

This means the time grows proportionally to the total number of elements involved in the operation.

Common Mistake

[X] Wrong: "Broadcasting makes the operation run in constant time regardless of array size."

[OK] Correct: Broadcasting avoids explicit loops in code but still performs element-wise operations internally, so time grows with the total number of elements.

Interview Connect

Understanding broadcasting time helps you explain how numpy handles big data efficiently and shows you can reason about performance in real tasks.

Self-Check

"What if we broadcast a 1D array to a 3D array? How would the time complexity change?"