GATE CS 2004 Q39 — Asymptotic Worst Case Time and Space Complexity

The time complexity of an algorithm refers to the asymptotic number of basic operations (such as additions and multiplications) it performs as a function of the input size.

For multiplying two $n \times n$ matrices $M_1$ and $M_2$ using the standard matrix multiplication algorithm:

• The number of scalar multiplications required is $n^3$.
• The number of scalar additions required is $n^2(n-1)$.

This count of operations depends solely on the mathematical definition of matrix multiplication and is completely independent of how the matrices are laid out in memory (whether in row-major or column-major order).

Note on Cache Performance:
While the physical execution time (wall-clock time) can be influenced by cache locality—where accessing $M_1$ in row-major and $M_2$ in column-major order minimizes cache misses—the theoretical asymptotic time complexity remains $O(n^3)$ regardless of the storage scheme.

Therefore, the time complexity is independent of the storage scheme.