Matrix multiplication (*) in MATLAB - Time & Space Complexity

Time Complexity: Matrix multiplication (*)

O(n^3)

Understanding Time Complexity

Matrix multiplication is a common operation in many programs. Understanding how its time grows helps us write faster code.

We want to know how the work needed changes as the matrix size gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

A = rand(n, n);
B = rand(n, n);
C = A * B;

This code multiplies two square matrices of size n by n using MATLAB's built-in operator.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Multiplying and adding elements for each entry in the result matrix.
• How many times: For each of the n rows and n columns, it sums n products, so about n x n x n = n³ times.

How Execution Grows With Input

As the matrix size n grows, the number of operations grows much faster.

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

Pattern observation: When n increases ten times, the work increases about a thousand times.

Final Time Complexity

Time Complexity: O(n^3)

This means the time needed grows roughly with the cube of the matrix size.

Common Mistake

[X] Wrong: "Matrix multiplication takes only n² steps because the result is an n by n matrix."

[OK] Correct: Each element in the result needs n multiplications and additions, so the total work is much more than just filling the matrix.

Interview Connect

Knowing how matrix multiplication scales helps you understand performance in many areas like graphics, data science, and simulations. It shows you how to think about efficiency in real problems.

Self-Check

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