- #1

de1337ed

- 11

- 0

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) = n

^{2}. And B x v would be another column vector.

And A x (B x v) would also be g(n) = n

^{2}for the same reason (because B x v is a column vector). So I thought the total complexity for be T(n) = n

^{4}

For (1), I thought that (A x B) would be f(n) = n

^{3}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) = n

^{2}because of n multiplications and n additions. So in total, it would be T(n) = n

^{5}.

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

A little help please?

Thank you.