What is the time complexity of multiplying two matrices of unequal dimension?

Question

I've looked over the big-O complexity of multiplying two n × n matrices, which takes time O(n³). But how do you get big-O complexity for multiplying two rectangular matrices which are of dimensions m × n and n × r? I've been told the answer is O(mnr), but I'm not sure where this comes from. Can anyone explain this?

Thanks!

Answer 1

I assume that you're talking about the complexity of multiplying two square matrices of dimensions n × n working out to O(n³) and are asking the complexity of multiplying an m × n matrix and an n × r matrix. There are specialized algorithms that can solve this problem faster than the naive approach, but for the purposes of this question I'll just talk about the standard "multiply each row by each column for each entry" algorithm.

First, let's see where the O(n³) term comes from in multiplying two n × n matrices. Note that for each value of the resulting matrix, the entry at position (i, j) is given by the inner product of the ith row of the left matrix and the jth column of the right matrix. There are n elements in each row and column, so computing each element takes time Θ(n). Doing this Θ(n²) times (once for each element of the resulting matrix) takes time Θ(n³).

Now think about this in the context of the product of an m × n matrix and an n × r matrix. Entry (i, j) in the matrix is given by the inner product of the ith row of the left matrix (which has n entries) and the jth column of the right matrix (which has n entries), so computing it takes time Θ(n). You do this once per element of the resulting matrix. Since the resulting matrix has dimension m × r, there are Θ(mr) elements to consider. Therefore, the total work done is Θ(mnr).

Hope this helps!