Introduction

The time complexity of matrix multiplication depends on which algorithm you mean and on the matrix shapes involved. For the standard textbook algorithm multiplying an m x n matrix by an n x p matrix, the time complexity is O(mnp).

When people quote O(n^3), they are talking about the special case where all matrices are square and have the same dimension n. That is the starting point, not the only answer.

Standard Matrix Multiplication

Suppose matrix A has shape m x n and matrix B has shape n x p. Their product C has shape m x p, and each entry is a dot product of length n.

A direct implementation looks like this:

1def matmul(a, b):
2    m = len(a)
3    n = len(a[0])
4    p = len(b[0])
5
6    result = [[0 for _ in range(p)] for _ in range(m)]
7
8    for i in range(m):
9        for j in range(p):
10            for k in range(n):
11                result[i][j] += a[i][k] * b[k][j]
12
13    return result

The three nested loops explain the complexity directly:

• 'm choices for the row'
• 'p choices for the column'
• 'n multiplications and additions per output entry'

So the running time is O(mnp).

Why Square Matrices Become O(n^3)

If m = n = p, then the formula becomes:

O(n * n * n) = O(n^3)

That is why introductory algorithms courses often summarize matrix multiplication as cubic time.

For example, multiplying two 1000 x 1000 matrices with the naive algorithm scales on the order of a billion scalar multiply-add style operations.

Faster Algorithms Exist

Researchers found algorithms that beat the cubic bound for large square matrices. The most famous practical theoretical milestone is Strassen's algorithm, which reduces the exponent to about 2.807.

The idea is to split matrices into blocks and reduce the number of recursive multiplications.

Strassen complexity: O(n^log2(7)) ≈ O(n^2.807)

There are also even faster asymptotic algorithms with smaller exponents, but they are usually not what engineers mean in day-to-day software work because the constant factors and implementation complexity are high.

Why the Naive Complexity Still Matters

Even though faster asymptotic algorithms exist, the standard O(mnp) cost is still the most useful answer in many contexts because:

• it matches simple implementations
• many libraries switch algorithms internally based on size
• practical performance depends heavily on cache layout, blocking, and hardware acceleration

So a library may run much faster than a naive triple loop while still fundamentally being discussed against the classical cubic baseline.

Theoretical Complexity Versus Real Performance

Time complexity is not the same as wall-clock speed. A theoretically faster algorithm can lose in practice on small or medium matrices because of overhead.

That is why optimized BLAS libraries, GPU kernels, and blocked algorithms matter so much in practice. They improve performance dramatically even when you still conceptually start from matrix multiplication's classical structure.

Do Not Confuse This with Matrix Chain Multiplication

There is a different problem called matrix chain multiplication that asks for the best parenthesization of many matrix products. That problem is about minimizing the total number of scalar operations across a whole chain.

It is not the same as asking for the time complexity of multiplying one matrix by another.

Common Pitfalls

• Saying matrix multiplication is always O(n^3) without mentioning the rectangular O(mnp) form.
• Assuming asymptotically faster algorithms are always faster in practical code.
• Confusing the complexity of one multiplication with the separate matrix chain ordering problem.
• Ignoring hardware and memory effects when comparing real implementations.
• Forgetting that output size itself is m x p, so even writing the result has a cost tied to matrix dimensions.

Summary

• Standard multiplication of an m x n matrix by an n x p matrix takes O(mnp) time.
• For square n x n matrices, that becomes O(n^3).
• Faster algorithms such as Strassen reduce the exponent for large square matrices.
• Practical runtime depends on implementation details, not only asymptotic notation.
• Use O(mnp) when discussing general shapes and O(n^3) for the common square-matrix shorthand.