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

The complexity remains the same independent of storage scheme.

The main difference between row-major and column-major order is memory access patterns - for example if you iterate by column then row-major order would be jumping around memory, which is bad for CPUs because they cannot read-ahead/cache memory.

This is because transferring data from RAM to the CPU on modern processors is relatively very slow, compared with the speed of the processors. Thus most of the time would be spent on waiting for the memory to arrive.

To solve this problem, memory accesses are answered in in bunches, with a lot of extra data coming to the CPU's caches. This makes it important to use "good" memory access patterns, so that the machine can try and predict what you will use next, and therefore cache it, and thus eliminate the transfer-wait-times as much as possible. But if you jump around memory instead of going in order, the machine will potentially have to wait for each access.

The wait time is bounded by a constant however, so the complexity remains the same. And of course, doing it in the correct order does not decrease the complexity.

https://cs.stackexchange.com/questions/17865/does-the-performance-of-matrix-multiplication-depend-on-the-storage-of-the-array

---

program execution time is nothing but time complexity . Am i wrong?

---

Time complexity is not the exact program execution time, it is an estimated time which is independent of many things- machine, processor's speed, etc.

Like that, we assume that access to any element takes constant time(O(1)) but internally it will be different for different machines.

---

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.