np.linalg.solve() for linear systems in NumPy - Time & Space Complexity

Time Complexity: np.linalg.solve() for linear systems

O(n^3)

Understanding Time Complexity

We want to understand how the time needed to solve linear equations grows as the size of the system increases.

How does the work change when we have more variables and equations?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

# Create a random 3x3 matrix A and vector b
A = np.random.rand(3, 3)
b = np.random.rand(3)

# Solve the system Ax = b
x = np.linalg.solve(A, b)

This code solves a system of 3 linear equations with 3 unknowns using numpy's solver.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matrix factorization and substitution steps inside the solver.
• How many times: These operations involve nested loops over the matrix size, repeated roughly n times for an n x n matrix.

How Execution Grows With Input

As the number of variables (n) grows, the work to solve the system grows quickly because the solver does many calculations involving all rows and columns.

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: The work grows roughly by the cube of n, so doubling n makes the work about eight times bigger.

Final Time Complexity

Time Complexity: O(n^3)

This means if you double the number of variables, the time to solve the system grows about eight times.

Common Mistake

[X] Wrong: "Solving linear systems with np.linalg.solve() takes time proportional to n, so doubling variables doubles time."

[OK] Correct: The solver does many nested calculations involving all variables, so time grows much faster than just doubling.

Interview Connect

Knowing how solving linear systems scales helps you understand performance in data science tasks like regression or simulations.

Self-Check

"What if we used a sparse matrix solver instead of np.linalg.solve()? How would the time complexity change?"