Common broadcasting patterns in NumPy - Time & Space Complexity

Time Complexity: Common broadcasting patterns

O(n*m)

Understanding Time Complexity

When using NumPy, broadcasting lets us do math on arrays of different shapes without extra loops.

We want to know how the time to run these operations grows as arrays get bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

A = np.ones((1000, 1000))
B = np.arange(1000).reshape(1000, 1)

C = A + B  # Broadcasting B to match A's shape

This code adds a 1000x1000 array to a 1000x1 array by broadcasting the smaller array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Element-wise addition over the full 1000x1000 array.
• How many times: Once for each of the 1,000,000 elements in the result.

How Execution Grows With Input

As the arrays get bigger, the number of additions grows with the total number of elements in the output.

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

Pattern observation: Operations grow roughly with the product of the output array dimensions.

Final Time Complexity

Time Complexity: O(n*m)

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

Common Mistake

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

[OK] Correct: Even though broadcasting avoids copying data, the operation still processes every element in the output array, so time depends on the output size.

Interview Connect

Understanding broadcasting time helps you explain how vectorized code scales and why it's efficient compared to loops.

Self-Check

What if we changed the smaller array to have shape (1, m) instead of (n, 1)? How would the time complexity change?

Practice

1. What does broadcasting in NumPy allow you to do?

easy

A. Perform operations on arrays of different shapes without explicit loops

B. Only add arrays of the exact same shape

C. Convert arrays into lists automatically

D. Sort arrays in ascending order

Solution

1. Step 1: Understand broadcasting concept

   Broadcasting lets NumPy perform element-wise operations on arrays with different shapes by automatically expanding the smaller array.

2. Step 2: Compare options

   Only Perform operations on arrays of different shapes without explicit loops correctly describes this feature. Options A, B, and C describe unrelated behaviors.

3. Final Answer:

   Perform operations on arrays of different shapes without explicit loops -> Option A

4. Quick Check:

   Broadcasting = operations on different shapes [OK]

Hint: Broadcasting means math on different shaped arrays without loops [OK]

Common Mistakes:

• Thinking broadcasting requires arrays to have the same shape
• Confusing broadcasting with sorting or type conversion
• Assuming broadcasting changes array data types

2. Which of the following is the correct way to add a 1D array to each row of a 2D array using broadcasting?

easy

A. result = matrix + vector.T where matrix.shape = (3,4) and vector.shape = (4,)

B. result = matrix + vector where matrix.shape = (3,4) and vector.shape = (3,)

C. result = matrix + vector where matrix.shape = (3,4) and vector.shape = (4,)

D. result = matrix + vector.reshape(3,1) where matrix.shape = (3,4) and vector.shape = (4,)

Solution

1. Step 1: Check shapes for broadcasting

   Adding a 1D array of shape (4,) to each row of a (3,4) matrix works because the vector matches the number of columns.

2. Step 2: Evaluate options

   result = matrix + vector where matrix.shape = (3,4) and vector.shape = (4,) matches this pattern. result = matrix + vector where matrix.shape = (3,4) and vector.shape = (3,) tries to add a (3,) vector to (3,4) matrix which fails. result = matrix + vector.T where matrix.shape = (3,4) and vector.shape = (4,) uses transpose incorrectly. result = matrix + vector.reshape(3,1) where matrix.shape = (3,4) and vector.shape = (4,) reshapes vector wrongly.

3. Final Answer:

   result = matrix + vector where matrix.shape = (3,4) and vector.shape = (4,) -> Option C

4. Quick Check:

   Vector shape matches columns for row-wise addition [OK]

Hint: Add vector matching columns to matrix rows for broadcasting [OK]

Common Mistakes:

• Using vector shape matching rows instead of columns
• Trying to transpose 1D vector which has no effect
• Reshaping vector incorrectly before addition

3. What is the output of the following code?

import numpy as np
A = np.array([[1, 2, 3], [4, 5, 6]])
B = np.array([10, 20, 30])
C = A + B
print(C)

medium

A. [[11 22 33]
[14 25 36]]

B. [[11 22 33]
[14 25 36]
[10 20 30]]

C. [[10 20 30]
[10 20 30]]

D. ValueError due to shape mismatch

Solution

1. Step 1: Understand shapes of A and B

   A has shape (2,3), B has shape (3,). B will broadcast across rows of A.

2. Step 2: Perform element-wise addition

   Each row of A adds B: [1+10, 2+20, 3+30] = [11, 22, 33], [4+10, 5+20, 6+30] = [14, 25, 36].

3. Final Answer:

   [[11 22 33] [14 25 36]] -> Option A

4. Quick Check:

   Broadcast adds vector to each matrix row [OK]

Hint: Add vector to each matrix row when vector shape matches columns [OK]

Common Mistakes:

• Expecting an extra row in output
• Confusing broadcasting with stacking arrays
• Thinking shape mismatch causes error here

4. Identify the error in this code snippet:

import numpy as np
X = np.array([[1, 2], [3, 4], [5, 6]])
y = np.array([10, 20, 30])
result = X + y

medium

A. y should be reshaped to (3,1) before addition

B. No error, code runs fine

C. X and y must have the same number of columns

D. Shapes (3,2) and (3,) cannot broadcast together

Solution

1. Step 1: Check shapes of X and y

   X shape is (3,2), y shape is (3,). Broadcasting rules require trailing dimensions to match or be 1.

2. Step 2: Analyze broadcasting compatibility

   Here, last dims are 2 (X) and 1 (y) after broadcasting rules, so y broadcasts along columns. The addition works without error.

3. Final Answer:

   No error, code runs fine -> Option B

4. Quick Check:

   Broadcasting allows (3,2) + (3,) by treating (3,) as (3,1) [OK]

Hint: Trailing dimensions must match or be 1 for broadcasting [OK]

Common Mistakes:

• Assuming broadcasting works if first dims match
• Not checking trailing dimension compatibility
• Thinking reshaping y to (3,1) fixes addition here

5. Given a 2D array M of shape (4,3) and a 1D array v of shape (4,), how can you add v to each column of M using broadcasting?

hard

A. M + v.T

B. M + v

C. M + v.reshape(1,4)

D. M + v.reshape(4,1)

Solution

1. Step 1: Understand shapes and desired operation

   M is (4,3), v is (4,). To add v to each column, v must be reshaped to (4,1) to broadcast along columns.

2. Step 2: Check each option

   M + v.reshape(4,1) reshapes v to (4,1), allowing broadcasting with M (4,3). M + v tries to add (4,) to (4,3) which broadcasts incorrectly. M + v.reshape(1,4) reshapes v to (1,4), incompatible. M + v.T uses transpose on 1D array which has no effect.

3. Final Answer:

   M + v.reshape(4,1) -> Option D

4. Quick Check:

   Reshape vector to (rows,1) to add to columns [OK]

Hint: Reshape vector to (rows,1) to add to matrix columns [OK]

Common Mistakes:

• Adding vector without reshaping when shapes differ
• Using reshape(1, rows) instead of (rows,1)
• Assuming transpose changes 1D array shape