Question

The following algorithm multiplies two square matrices using a straightforward implementation of the definition of matrix multiplication.

(If you are unfamiliar with matrices, think of them as 2-dimensional arrays, and don’t worry, you don’t need to know how to do matrix multiplication to solve this problem)

1 2 3 4 5 6 7 8 9

10

ALGORITHM MatrixMultiplication(A[1..n, 1..n], B[1..n, 1..n])
// Multiply two square matrices of order n using the definition-based algorithm //Input: twon×nmatricesAandB
// Output: matrix C = AB
fori←1tondo

for j ← 1 to n do C[i, j] ← 0

for k ← 1 to n do

C[i, j] ← C[i, j] + (A[i, k] * B[k, j]) return C

The basic operations are the addition and multiplication of matrix elements at line 9. Determine the number of basic operations performed for two input matrices of size n × n. Write your answer in simplest form, if possible.

please try to explain how you did thi, thank you!

Answer 1

fori←1 to n do

for j ← 1 to n do

C[i, j] ← 0

for k ← 1 to n do

C[i, j] ← C[i, j] + (A[i, k] * B[k, j]) // basic operation

return C

If the matrix is of order n x n, the number of basic operations take place is n³. For example, if the matrix is of the order 2 x 2, the number of basic operations performed will be 2³ =8 . If it is a 3 x 3 matrix then it will be 3³ =27 and so on.

Example

Consider the 2 x 2 matrix A = 1 2 and B = 5 6

  3 4 1   2

The result will also be a 2 x 2 matrix ( 4 elements)

Row 1

Initially c[i,j=0

so in the first summation it will be 0 + 1 *5 =5 count 1

second summation will be 5+2*1 =7 count 2

First element in the resultant matrix will be 7

Row 1

Again c[i,j=0

For the second element the first summation will be 0+1*6=6 count 3

second summation will be 6+2*2 =10 count 4

So second element in first row will be 10

Row 2

Initially c[i,j=0

so in the first summation it will be 0 + 3 *5 =15 count 5

second summation will be 15+1*4 =19 count 6

So first element in the second row will be 19

Row 2

For the second element in row 2,  the first summation will be 0+3*6=18 count 7

second summation will be 18+4*2 =26 count 8

So second element in second row will be 26

All together the count of basic operations is 8 which is 2³