GATE CSE 2004 | Question: 39

Question

Two matrices $M_1$ and $M_2$ are to be stored in arrays $A$ and $B$ respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute $M_1 \times M_2$ will be

• A. best if $A$ is in row-major, and $B$ is in column-major order

• B. best if both are in row-major order

• C. best if both are in column-major order

• D. independent of the storage scheme

Answer 1

D is correct

Here time complexity is asked, for each access of array element it will be constant,

So the time complexity will not depend upon storage. If at all program execution time is asked option a is true.

Comments

just asking, what is the time complexity of the fastest matrix multiplication algorithm, i googled and it showed o(n^2.3), is there any other faster algorithm?

---

i had doing coding on Solvay Strassen multiplication that takes arround O(n^2.8) something but one more algorithm is suggested to multiply the matrices is "Coppersmith-Winograd algorithm" that takes around O(n^2.38) best known algorithm as off now.

https://stackoverflow.com/questions/8546756/matrix-multiplication-algorithm-time-complexity

---

Why the algo won't care about the size here.... because if the size will be so much large access time for particular elements will vary

Answer 2

Running time of an algorithm is always independent of the storage scheme. While computing the running time of an algorithm we assume that to access any element time taken is same. So Answer is D.

But if the question asked best time complexity in which of the following implementation (not algorithm) then Option a is correct.

Comments

@reena while measuring the time complexity of an algorithm we do the asymptotic analysis, where we do not bother about the hardware on which the program is running.

But obviously hardware effect the overall time is taken to execute a program.

---

program execution time effects when we're accessing row-major order & array is stored in column-major order.( one simple point is huge no. of cache miss which will cause many miss penalty).

---

Hemant Parihar Sir, you switched the explanations.

Time Complexity is independent of hardware and storage schemes. It only depends on the code.

 

Running time, however, would depend upon several other factors like hardware, pipelining, miss penalties etc.

Answer 3

ans a)

Matrix multiplication takes the rows of M₂ and columns of M₂ in order. So, if the array A is stored in row-major and array B is stored in column-major, when the first element is accessed, the neighbouring elements (which will be immediately needed) will also be brought to cache. So, this storage scheme is best for matrix multiplication in terms of execution time.

 

Comments

The question asks about "Time Complexity". In any cases O(n³) would be the TC. Had it been asked about "execution time in terms of memory access time" then option a. would be appropriate. 

Please clarify my doubt.

---

did you mean to say rows of M1?

and i think you have given answer for the question asking the about the program execution and the time complexity

---

 An O(n³) algorithm will still be an O(n³)algorithm (assuming you are using the straightforward matrix-multiply). However, by taking into account the memory hierarchy of the system, you can significantly speed up that O(n³) algorithm.

Answer 4

The question asks about time complexity, not time taken by the program and for time complexity, it doesn't matter how we store array elements or which data structure we use, we always need to access same number of elements of M1 and M2 to multiply the matrices. It is always constant or O(1) time to do element access, thus the constants may differ for different schemes, but not the time complexity.