np.einsum() for efficient computation in NumPy - Time & Space Complexity

Time Complexity: np.einsum() for efficient computation

O(n^3)

Understanding Time Complexity

We want to understand how fast np.einsum() runs when doing calculations on arrays.

Specifically, how does the time it takes grow as the size of the arrays grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

A = np.random.rand(1000, 1000)
B = np.random.rand(1000, 1000)

# Compute matrix multiplication using einsum
C = np.einsum('ik,kj->ij', A, B)

This code multiplies two 1000x1000 matrices using np.einsum for efficient computation.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Multiplying and summing elements across rows and columns.
• How many times: For each element in the result matrix, it repeats over the shared dimension (1000 times).

How Execution Grows With Input

As the size of the matrices grows, the number of multiplications and sums grows quickly.

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

Pattern observation: The operations grow by the cube of the input size, so tripling the size makes the work much bigger.

Final Time Complexity

Time Complexity: O(n^3)

This means the time to compute grows roughly with the cube of the matrix size, so bigger matrices take much longer.

Common Mistake

[X] Wrong: "np.einsum() always runs faster than other methods regardless of input size."

[OK] Correct: While np.einsum() is efficient, the time still grows quickly with input size because it does many multiplications and sums. For very large inputs, it still takes a lot of time.

Interview Connect

Understanding how np.einsum() scales helps you explain efficient array operations clearly and confidently in real projects or interviews.

Self-Check

"What if we changed the operation to element-wise multiplication instead of matrix multiplication? How would the time complexity change?"