Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each…
2004
Two matrices M1 and M2 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 M1 × M2 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
Attempted by 263 students.
Show answer & explanation
Correct answer: D
Answer: Θ(n^3) — independent of the storage scheme.
Explanation: The standard (naive) algorithm for multiplying two n×n matrices uses three nested loops and performs on the order of n^3 scalar multiplications (and a similar number of additions). This operation count does not depend on whether the matrices are stored in row-major or column-major order.
Operation count: For n×n matrices the triple loop yields Θ(n^3) arithmetic operations.
Memory layout effect: Row-major vs column-major only affects whether particular memory accesses in the inner loop are contiguous, which influences cache behavior and constant factors (performance), but it does not change the asymptotic number of arithmetic operations.
Conclusion: Time complexity is Θ(n^3). Storage scheme may change runtime constants (practical speed) but not the asymptotic complexity.
A video solution is available for this question — log in and enroll to watch it.