Question

1. Write an algorithm to calculate the Matrix multiplication (or write with pseudo code)

2. Write an algorithm to calculate the recursive Matrix multiplication (or write with pseudo code)

3. Find the time complexity of your pseudo code and analyze the differences

Answer 1

Algorithm for matrix multiplication:

Step 1: Start

Step 2: Declare variable i,j and k.

Step 3: Define the size of the matrix in a variable say N.

Step 4: A [][] and B[][] are the matrices and C[][] is the result matrix.

Step 5: Variable i is for knowing the position in the first matrix and variable j is for knowing the position in second matrix.

Step 6: The variable k traverses through both the matrix and multiplication happens.

Step 7:Three For loops are used to iterate through the rows and columns.

Step 8: The for loop fails if its exceeds the size of the matrix.

Step 9: Multiplication happens in a standard way i.e The first row of the ith matrix and first column of jth matrix is multiplied and added altogether.

Step 10: In your main function declare the input values and run the code.

Step 11: Stop

2.Algorithm for recursive matrix multiplication

Step 1: Start

Step 2: Recursive multiplication is the process of dividing the input matrix into sub matrices and then getting the result.

Step 3: Only if the number of columns in a second matrix are equal to the number of rows in the first matrix recursive multiplication happens.

Step 4:Similar to matrix multiplication follow the step 2.

Step 5: Declare a maximum size say 100 as we will be dividing it into sub matrices.

Step 6: Using if statement check the column position using i variable and then check the column position in second matrix by j variable.

Step 7: The above if statements get true then check the position of k variable and if its not exceeded size of matrix then mutliply both and get the result matrix.

Step 8: C[][] will hold the result matrix.

3.In a 2*2 matrix 8 multiplications happen so the time compexity will be 8T(N/2)+O(N^2). Solving the equation you get a time complexity value of O(N^3). Using Strassens method this can be reduced by using divide and conquer method. i.e dividing the input matrix into sub matrices and recursive calls made are reduced to 7 from 8.The time complexity after using this will be O(N^2.87). Usually this procedure is not used and naive multiplying is done.