Broadcasting for outer products in NumPy - Time & Space Complexity

Time Complexity: Broadcasting for outer products

O(n^2)

Understanding Time Complexity

We want to understand how the time needed to compute outer products using broadcasting changes as the input size grows.

How does the number of operations increase when vectors get longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

n = 10  # Example size
x = np.arange(n)          # Vector of length n
y = np.arange(n)          # Vector of length n

outer_product = x[:, None] * y  # Compute outer product using broadcasting

This code creates two vectors and computes their outer product by broadcasting one vector to a column and multiplying by the other.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Multiplying each element of vector x by each element of vector y.
• How many times: For vectors of length n, this multiplication happens n x n times.

How Execution Grows With Input

As the vectors get longer, the number of multiplications grows quickly because every element in x multiplies with every element in y.

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

Pattern observation: The operations grow by the square of the input size. Doubling n makes the work about four times bigger.

Final Time Complexity

Time Complexity: O(n2)

This means the time to compute the outer product grows roughly with the square of the vector length.

Common Mistake

[X] Wrong: "Broadcasting makes the operation run in linear time because it avoids loops."

[OK] Correct: Broadcasting helps write code without explicit loops, but the actual number of multiplications still grows with n squared because every pair of elements is multiplied.

Interview Connect

Understanding how broadcasting affects time helps you explain performance clearly and shows you know how array operations scale in real tasks.

Self-Check

"What if we computed the outer product of two vectors where one vector is much smaller than the other? How would the time complexity change?"