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