This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Matrix Multiplication using Recursion”.
1. If Matrix A is of order X*Y and Matrix B is of order M*N, then what is the order of the Matrix A*B given that Y=M?
a) Y*N
b) X*M
c) X*N
d) Y*M
View Answer
Explanation: The Matrix A*B is of order X*N as it is given that Y=M i.e. number of columns in Matrix A is equal to total number of rows in matrix B. So the Matrix A*B must have X number of rows and N number of columns.
2. How many recursive calls are there in Recursive matrix multiplication through Simple Divide and Conquer Method?
a) 2
b) 6
c) 9
d) 8
View Answer
Explanation: For the multiplication two square matrix recursively using Simple Divide and Conquer Method, there are 8 recursive calls performed for high time complexity.
3. What is the time complexity of matrix multiplied recursively by Divide and Conquer Method?
a) O(n)
b) O(n2)
c) O(n3)
d) O(n!)
View Answer
Explanation: The time complexity of recursive multiplication of two square matrices by the Divide and Conquer method is found to be O(n3) since there are total of 8 recursive calls.
4. What is the time complexity of matrix multiplied recursively by Strassen’s Method?
a) O(nlog7)
b) O(n2)
c) O(n3)
d) O(n!)
View Answer
Explanation: The time complexity of recursive multiplication of two square matrices by Strassen’s Method is found to be O(nlog7) since there are total 7 recursive calls.
5. How many recursive calls are there in Recursive matrix multiplication by Strassen’s Method?
a) 5
b) 7
c) 8
d) 4
View Answer
Explanation: For the multiplication two square matrix recursively using Strassen’s Method, there are 7 recursive calls performed for high time complexity.
6. Matrix A is of order 3*4 and Matrix B is of order 4*5. How many elements will be there in a matrix A*B multiplied recursively.
a) 12
b) 15
c) 16
d) 20
View Answer
Explanation: The resultant matrix will be of order 3*5 when multiplied recursively and therefore the matrix will have 3*5=15 elements.
7. If Matrix X is of order A*B and Matrix Y is of order C*D, and B=C then the order of the Matrix X*Y is A*D?
a) True
b) False
View Answer
Explanation: Given that B=C, so the two matrix can be recursively multiplied. Therefore, the order of the Matrix X*Y is A*D.
8. What is the time complexity of the fastest known matrix multiplication algorithm?
a) O(nlog7)
b) O(n2.37)
c) O(n3)
d) O(n!)
View Answer
Explanation: The Coppersmith-Winograd algorithm multiplies the matrices in O(n2.37) time. Several improvements have been made in the algorithm since 2010.
9. Is Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity?
a) True
b) False
View Answer
Explanation: Since The Coppersmith-Winograd algorithm multiplies the matrices in O(n2.37) time. The time complexity of recursive multiplication of two square matrices by Strassen’s Method is found to be O(n2.80). Therefore, Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Apply for Computer Science Internship
- Check Design and Analysis of Algorithms Books
- Practice Computer Science MCQs
- Practice Data Structure MCQ
- Practice Programming MCQs