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?"

Practice

1. What does broadcasting in NumPy allow you to do with arrays of different shapes?

easy

A. Only add arrays if they have the exact same shape

B. Sort arrays in ascending order

C. Convert arrays into lists automatically

D. Perform element-wise operations without manually reshaping arrays

Solution

1. Step 1: Understand broadcasting concept

   Broadcasting lets NumPy perform math on arrays with different shapes by stretching smaller arrays.

2. Step 2: Identify what broadcasting enables

   This means you can do element-wise operations without manually reshaping arrays to the same shape.

3. Final Answer:

   Perform element-wise operations without manually reshaping arrays -> Option D

4. Quick Check:

   Broadcasting = element-wise operations on different shapes [OK]

Hint: Broadcasting stretches smaller arrays to match bigger ones [OK]

Common Mistakes:

• Thinking arrays must have the same shape to operate
• Confusing broadcasting with sorting or reshaping
• Assuming broadcasting copies data

2. Which of the following is the correct way to add a 1D array b = np.array([1, 2, 3]) to each row of a 2D array a with shape (4, 3)?

easy

A. a + b

B. a + b.T

C. a + b.reshape(3, 1)

D. a + b.reshape(1, 4)

Solution

1. Step 1: Check shapes of arrays

   Array a has shape (4, 3), and b has shape (3,). Adding a + b broadcasts b across rows.

2. Step 2: Understand broadcasting rules

   Since b matches the number of columns, it adds to each row correctly without reshaping.

3. Final Answer:

   a + b -> Option A

4. Quick Check:

   1D array added across rows = a + b [OK]

Hint: Add 1D array directly if its length matches columns [OK]

Common Mistakes:

• Trying to transpose 1D array which has no effect
• Reshaping to wrong dimensions causing errors
• Confusing rows and columns in shapes

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])
result = a + b
print(result)

medium

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

B. [[11 12 13]
[14 15 16]]

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

D. Error due to shape mismatch

Solution

1. Step 1: Analyze shapes and operation

   a shape is (2,3), b shape is (3,). Adding broadcasts b across rows.

2. Step 2: Calculate element-wise addition

   Row 1: [1+10, 2+20, 3+30] = [11, 22, 33]
   Row 2: [4+10, 5+20, 6+30] = [14, 25, 36]

3. Final Answer:

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

4. Quick Check:

   Broadcast add across rows = [[11 22 33], [14 25 36]] [OK]

Hint: Add 1D array to 2D rows matches columns [OK]

Common Mistakes:

• Expecting error due to different shapes
• Adding element-wise without broadcasting
• Confusing rows and columns in addition

4. Identify the error in this code snippet:

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

medium

A. Using wrong operator for addition

B. Syntax error in array creation

C. Shapes of a and b are incompatible for broadcasting

D. No error, code runs fine

Solution

1. Step 1: Check shapes of arrays

   a shape is (3, 2), b shape is (3,). They differ in second dimension.

2. Step 2: Understand broadcasting rules

   Broadcasting requires trailing dimensions to match or be 1. Here, 2 != 3, so addition fails.

3. Final Answer:

   Shapes of a and b are incompatible for broadcasting -> Option C

4. Quick Check:

   Shape mismatch causes broadcasting error [OK]

Hint: Check trailing dimensions match or are 1 for broadcasting [OK]

Common Mistakes:

• Assuming any shapes can broadcast
• Ignoring dimension order in arrays
• Thinking 1D arrays always broadcast to 2D

5. You have a 2D array data of shape (5, 4) representing 5 samples with 4 features each. You want to subtract the mean of each feature (given as a 1D array mean_vals of length 4) from the corresponding feature column in data. Which code correctly applies broadcasting to do this?

hard

A. data - mean_vals.reshape(4, 1)

B. data - mean_vals

C. data - mean_vals.reshape(1, 5)

D. data - mean_vals.T

Solution

1. Step 1: Understand shapes and operation

   data shape is (5, 4), mean_vals shape is (4,). Subtracting mean_vals from data broadcasts mean_vals across rows.

2. Step 2: Confirm correct broadcasting

   Since mean_vals length matches columns, data - mean_vals subtracts feature-wise means correctly.

3. Final Answer:

   data - mean_vals -> Option B

4. Quick Check:

   Subtract 1D array from 2D rows = data - mean_vals [OK]

Hint: Subtract 1D array matching columns directly [OK]

Common Mistakes:

• Reshaping mean_vals incorrectly causing errors
• Transposing 1D array which has no effect
• Trying to subtract mean_vals across wrong axis