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 choice between row-major and column-major affects memory access patterns and cache locality, which can influence the actual runtime performance of the algorithm. For example, accessing elements sequentially in memory (as opposed to non-sequential) is generally faster because of better cache utilization.

• However, the time complexity (which is about the number of operations and not about the details of memory access or cache) remains the same and is independent of storage scheme.

Answer 5

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.

Answer 6

The correct answer is D) independent of the storage scheme.

---

Why Asymptotic Complexity is Independent of Storage

From a purely theoretical, asymptotic complexity perspective, the way a matrix is stored in memory does not change the total number of fundamental operations (multiplications and additions) required to compute the result.

The standard algorithm for multiplying two matrices always performs:

• multiplications

• additions

Regardless of whether the matrices are stored in row-major or column-major order, this exact number of arithmetic operations must be performed.

Practical Performance vs. Theoretical Complexity

• Performance: In the real world, matching the storage layout to the access pattern (A row-major, B column-major) drastically improves performance by reducing cache misses. This is a crucial concept in systems programming and performance optimization.

 

• Theoretical Complexity: GATE questions on this topic are typically asking about the fundamental asymptotic complexity, which only counts the number of operations as a function of . In this context, memory access time is considered constant for each operation, so caching effects are ignored.

Therefore, since the number of operations is always the same, the asymptotic time complexity is independent of the storage scheme.