# Time complexity of matrix multiplications?

1. Mar 19, 2012

### de1337ed

Let A and B be n×n matrices, and let v be a column vector of length n. Which of
the following two expressions is faster to compute?
1. ( A⋅ B )⋅ v or 2. A⋅ (B⋅ v)
As a function of n, give the number of multiplications and additions required for each part.

My attempt:

So, I said that (2) is faster to compute because B x v will have n additions and n multiplications, so that would be f(n) = n2. And B x v would be another column vector.
And A x (B x v) would also be g(n) = n2 for the same reason (because B x v is a column vector). So I thought the total complexity for be T(n) = n4

For (1), I thought that (A x B) would be f(n) = n3 because there are n additions, n multiplications, and this occurs n times. Multiplying the new n x n matrix with the column vector, we would get g(n) = n2 because of n multiplications and n additions. So in total, it would be T(n) = n5.

I feel like this isn't correct, but maybe I'm on the right track?
Thank you.

2. Mar 20, 2012

### Staff: Mentor

It is not clear what the question is asking. Maybe it is this:

As a function of n, give (i) the number of multiplications, and
(ii) the number of additions, required for each part.

When you compute a new element by multiplying a row of n elements by a column of n elements, the number of multiplications involved is n, but the number of additions involved is n-1. (I'm not sure whether n-1 is close enough to call it n, or not.)
Why multiply the two? If you had to combine them, I think you'd add them, and this can't be simplified further: number of multiplications = n3 + n2.