Let A and B be n×n matrices, and let v be a column vector of length n. Which of(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Time complexity of matrix multiplications?

**Physics Forums | Science Articles, Homework Help, Discussion**