Singular value decomposition (svd) in MATLAB - Time & Space Complexity

Time Complexity: Singular value decomposition (svd)

O(n^3)

Understanding Time Complexity

We want to understand how the time needed to perform singular value decomposition (SVD) changes as the size of the matrix grows.

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

Scenario Under Consideration

Analyze the time complexity of the following MATLAB code snippet.

A = rand(n, n);  % Create an n-by-n random matrix
[U, S, V] = svd(A);
    

This code computes the singular value decomposition of a square matrix A of size n-by-n.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The algorithm repeatedly performs matrix multiplications and transformations on the n-by-n matrix.
• How many times: These operations happen multiple times, roughly proportional to the size of the matrix cubed.

How Execution Grows With Input

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

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

Pattern observation: When n increases ten times, the work increases about a thousand times, showing a cubic growth pattern.

Final Time Complexity

Time Complexity: O(n^3)

This means the time needed grows roughly with the cube of the matrix size, so doubling the size makes the work about eight times bigger.

Common Mistake

[X] Wrong: "SVD runs in linear time because it just processes each element once."

[OK] Correct: SVD involves complex matrix operations that combine rows and columns many times, so it takes much more work than just touching each element once.

Interview Connect

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

Self-Check

"What if the matrix A was not square but rectangular with size m-by-n? How would the time complexity change?"