COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
O(n)
|
|
|
O(log n)
|
|
|
O(n3)
|
|
|
O(n2)
|
Detailed explanation-1: -By that definition, matrix addition is an O(N^2) since you must visit each of the NxN elements exactly once. By that same definition, matrix multiplication (using square NxN matrices) is O(N^3) because you need to visit N elements in each of the source matrices to compute each of the NxN elements in the product matrix.
Detailed explanation-2: -The standard way of multiplying an m-by-n matrix by an n-by-p matrix has complexity O(mnp).
Detailed explanation-3: -Explanation : Time complexity will be O(n2), because if we add all the elements one by one to other matrics we have to traverse the whole matrix at least 1 time and traversion takes O(n2) times.
Detailed explanation-4: -Space complexity = Auxiliary space + Input space. If you build a two-dimensional array of size n*n, this will need O(n2) space. Space complexity is dependent on several factors. These include the programming language, the compiler, as well as the machine that runs the algorithm.
Detailed explanation-5: -As of October 2022, the best announced bound on the asymptotic complexity of a matrix multiplication algorithm is O(n2.37188) time, given by Duan, Wu and Zhou announced in a preprint. This improves on the bound of O(n2.3728596) time, given by Josh Alman and Virginia Vassilevska Williams.