Let be a given square matrix. Compute the number of multiplications and additions required to evaluate using:

a) the naive method, (28 times)

b) etc.

__Solution__

Number of multiplications required to calculate one element of product matrix

Number of additions required to calculate one element of product matrix

Let multiplications be x & additions be y.

Total number of operations to calculate one element of product matrix

Size of matrix

Thus, total number of operations required to calculate all elements of the product matrix

__Answer a:__

Using Naive method, there will be 27 matrix multiplications to get .

Thus, total operations required for via naive method

__Answer b:__

If we divide & conquer & store the intermediate results, it can be done via below steps:

Total number of matrix multiplications required via this method to get

*Thus, total operations required for via divide & conquer *