Why linear algebra matters in NumPy - Performance Analysis

Time Complexity: Why linear algebra matters

O(n³)

Understanding Time Complexity

We want to see how the time to do linear algebra tasks grows as the data gets bigger.

How does the work needed change when we multiply or add big arrays?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

n = 10  # Example size
A = np.random.rand(n, n)
B = np.random.rand(n, n)

C = np.dot(A, B)  # Matrix multiplication

This code multiplies two square matrices of size n by n using numpy.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Multiplying each element of a row in A by each element of a column in B and summing.
• How many times: For each of the n rows and n columns, this happens n times.

How Execution Grows With Input

When n grows, the number of multiplications and additions grows quickly.

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

Pattern observation: Operations grow much faster than n itself, roughly n times n times n.

Final Time Complexity

Time Complexity: O(n³)

This means if the matrix size doubles, the work needed grows about eight times.

Common Mistake

[X] Wrong: "Matrix multiplication takes time proportional to n squared because there are n by n elements."

[OK] Correct: Each element requires summing over n multiplications, so the total work is more than just n squared.

Interview Connect

Understanding how matrix operations scale helps you explain performance in data tasks and shows you know what happens behind the scenes.

Self-Check

"What if we multiply a matrix of size n by a matrix of size n by m? How would the time complexity change?"