Broadcasting compatibility check in NumPy - Time & Space Complexity

Time Complexity: Broadcasting compatibility check

O(n)

Understanding Time Complexity

We want to understand how the time needed to check if two arrays can be broadcast together changes as their sizes grow.

How does the checking process scale when arrays get bigger or have more dimensions?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

def can_broadcast(shape1, shape2):
    for s1, s2 in zip(shape1[::-1], shape2[::-1]):
        if s1 != s2 and s1 != 1 and s2 != 1:
            return False
    return True

# Example usage
can_broadcast((4, 3, 2), (3, 1))

This code checks if two shapes can be broadcast together by comparing their dimensions from the end.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the dimensions of the two shapes from last to first.
• How many times: The loop runs as many times as the length of the shorter shape.

How Execution Grows With Input

As the number of dimensions in the smaller shape grows, the number of checks grows linearly.

Input Size (n)	Approx. Operations
2	2 checks
10	10 checks
100	100 checks

Pattern observation: The number of operations grows directly with the number of dimensions in the smaller shape.

Final Time Complexity

Time Complexity: O(n)

This means the time to check broadcasting grows in a straight line with the number of dimensions in the smaller array.

Common Mistake

[X] Wrong: "The time to check broadcasting depends on the total number of elements in the arrays."

[OK] Correct: The check only compares the shapes' dimensions, not the full data, so it depends on the number of dimensions, not elements.

Interview Connect

Understanding how broadcasting checks scale helps you reason about array operations efficiently, a useful skill when working with data and numerical computations.

Self-Check

"What if we changed the check to compare all dimensions of the larger shape instead of the smaller one? How would the time complexity change?"

Practice

1. Which of the following pairs of shapes are compatible for broadcasting in NumPy?

easy

A. (1, 2, 3) and (2, 3, 1)

B. (2, 3) and (3, 2)

C. (4, 5) and (4, 5, 1)

D. (3, 1) and (1, 4)

Solution

1. Step 1: Understand broadcasting rules

   Broadcasting compares shapes from right to left. Dimensions must be equal or one must be 1.

2. Step 2: Check each pair

   For (3,1) and (1,4), rightmost dims 1 and 4 are compatible (1 can broadcast to 4), left dims 3 and 1 compatible (1 can broadcast to 3). So compatible.

3. Final Answer:

   (3, 1) and (1, 4) are compatible -> Option D

4. Quick Check:

   Broadcast dims right to left, 1 can expand [OK]

Hint: Check shapes from right; 1 or equal dims broadcast [OK]

Common Mistakes:

• Assuming all different shapes are compatible
• Not comparing dimensions from right to left
• Ignoring that 1 can broadcast to any size

2. Which of the following is the correct way to check broadcasting compatibility of shapes (2, 3) and (3,) using NumPy?

easy

A. numpy.broadcast_shapes((2, 3), (3,))

B. numpy.broadcast((2, 3), (3,))

C. numpy.broadcast_shapes([2, 3], 3)

D. numpy.broadcast((2, 3), (3))

Solution

1. Step 1: Identify the correct function

   NumPy provides numpy.broadcast_shapes to check shape compatibility, which takes tuples as shape arguments.

2. Step 2: Check argument types

   numpy.broadcast_shapes((2, 3), (3,)) uses numpy.broadcast_shapes with tuples, which is correct. numpy.broadcast_shapes([2, 3], 3) uses a scalar for the second argument, which is invalid for this function.

3. Final Answer:

   numpy.broadcast_shapes((2, 3), (3,)) -> Option A

4. Quick Check:

   Use numpy.broadcast_shapes with tuples [OK]

Hint: Use numpy.broadcast_shapes with tuples for shape check [OK]

Common Mistakes:

• Using numpy.broadcast instead of numpy.broadcast_shapes
• Passing scalars instead of sequences
• Missing parentheses or wrong argument types

3. What will be the output of the following code?

import numpy as np
shape = np.broadcast_shapes((4, 1, 3), (1, 5, 3))
print(shape)

medium

A. (4, 1, 3)

B. (4, 5, 3)

C. (1, 5, 3)

D. ValueError: shapes not compatible

Solution

1. Step 1: Compare shapes dimension-wise from right

   Rightmost dims: 3 and 3 match. Next dims: 1 and 5, 1 broadcasts to 5. Leftmost dims: 4 and 1, 1 broadcasts to 4.

2. Step 2: Determine broadcasted shape

   Broadcasted shape is (4, 5, 3) combining max of each dimension.

3. Final Answer:

   (4, 5, 3) -> Option B

4. Quick Check:

   Broadcast dims max or 1 expands [OK]

Hint: Broadcast dims take max or 1 expands to max [OK]

Common Mistakes:

• Confusing which dimension broadcasts to which
• Expecting error when shapes are compatible
• Mixing up order of dimensions

4. The following code throws an error. What is the cause?

import numpy as np
np.broadcast_shapes((3, 2), (2, 3))

medium

A. Shapes are not compatible for broadcasting

B. Function broadcast_shapes does not exist

C. Tuples must be of same length

D. Missing import statement

Solution

1. Step 1: Check broadcasting rules for shapes (3, 2) and (2, 3)

   Compare from right: 2 vs 3 are different and neither is 1, so incompatible.

2. Step 2: Confirm error cause

   Since shapes cannot broadcast, numpy.broadcast_shapes raises ValueError.

3. Final Answer:

   Shapes are not compatible for broadcasting -> Option A

4. Quick Check:

   Broadcast dims must be equal or 1 [OK]

Hint: Check dims right to left; mismatch without 1 causes error [OK]

Common Mistakes:

• Thinking function is missing or typo
• Assuming tuples must be same length
• Ignoring broadcasting dimension rules

5. You have arrays with shapes (7, 1, 5) and (1, 3, 1). You want to add them using broadcasting. What will be the resulting shape?

hard

A. (1, 3, 5)

B. (7, 1, 1)

C. (7, 3, 5)

D. Cannot broadcast these shapes

Solution

1. Step 1: Compare shapes from right to left

   Right dims: 5 and 1, 1 broadcasts to 5. Middle dims: 1 and 3, 1 broadcasts to 3. Left dims: 7 and 1, 1 broadcasts to 7.

2. Step 2: Combine broadcasted dimensions

   Resulting shape is (7, 3, 5) taking max of each dimension.

3. Final Answer:

   (7, 3, 5) -> Option C

4. Quick Check:

   Broadcast dims max or 1 expands [OK]

Hint: Broadcast dims max or 1 expands to max [OK]

Common Mistakes:

• Mixing up dimension order
• Assuming shapes must be identical
• Forgetting 1 can broadcast to any size