Singular Value Decomposition (svd) in SciPy - Time & Space Complexity

Time Complexity: Singular Value Decomposition (svd)

O(m n min(m, n))

Understanding Time Complexity

We want to understand how the time needed to perform Singular Value Decomposition (SVD) changes as the size of the input matrix grows.

Specifically, how does the work increase when the matrix gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.linalg import svd

# Create a random matrix of size m x n
m, n = 100, 80
A = np.random.rand(m, n)

# Compute the singular value decomposition
U, s, Vh = svd(A)
    

This code creates a matrix and computes its singular value decomposition, which breaks it into three parts.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matrix transformations and iterative calculations inside the svd function.
• How many times: These operations depend on the matrix size, repeating over rows and columns multiple times.

How Execution Grows With Input

As the matrix size grows, the number of calculations grows quickly because the algorithm works on all rows and columns together.

Input Size (n = m = square matrix)	Approx. Operations
10	About 1,000
100	About 1,000,000
1000	About 1,000,000,000

Pattern observation: The work grows roughly with the cube of the matrix size, so doubling the size makes the work about eight times bigger.

Final Time Complexity

Time Complexity: O(m n \min(m, n))

This means the time needed grows roughly with the product of the matrix dimensions and the smaller dimension, which is often close to cubic growth for square matrices.

Common Mistake

[X] Wrong: "SVD runs in linear time because it just breaks the matrix into parts once."

[OK] Correct: The process involves many repeated calculations over all rows and columns, so the time grows much faster than just once through the data.

Interview Connect

Understanding how SVD scales helps you explain performance when working with large datasets or images, showing you know how algorithms behave with bigger inputs.

Self-Check

"What if we only compute a few singular values instead of all? How would the time complexity change?"