Write an algorithm in pseudocode to perform the multiplicati

Write an algorithm in pseudocode to perform the multiplication of a n cross n matrix A with a n cross 1 vector b. What is the main operation of this algorithm? How many times is the main operation executed? What is the efficiency class of this algorithm?

Solution

a. Here is the algorithm for you:

MatrixMultiplication(M1(1..n:1..n), M2(1..n: 1..1))
//Input: An nxn matrix, and a nx1 matrix.
//Output: A 1xn matrix.
//Given the matrices, this algorithm returns the product of these two matrices.

for i = 1 : n
b[i] = 0
for j = 1 : n
b[i] = b[i] + M1[i, j] * M2[j, 1]
return b

b. The main operation of this algorithm is the multiplication. b[i] = b[i] + M1[i, j] * M2[j, 1].

c. How many times is the main operation executed?

The main operation is executed for n² times.

d. The efficiency of this algorithm is: O(n²).