11,946 views
42 votes
42 votes

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

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

  2. best if both are in row-major order

  3. best if both are in column-major order

  4. independent of the storage scheme

4 Answers

Best answer
62 votes
62 votes

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.

edited by
23 votes
23 votes

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.

edited by
4 votes
4 votes

ans a)

Matrix multiplication takes the rows of M2 and columns of M2 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.

 

3 votes
3 votes
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:

Related questions

15 votes
15 votes
7 answers
1
Kathleen asked Sep 18, 2014
11,658 views
The problem $\text{3-SAT}$ and $\text{2-SAT}$ are both in $\text{P}$both $\text{NP}$ complete$\text{NP}$-complete and in $\text{P}$ respectivelyundecidable and $\text{NP}...
77 votes
77 votes
5 answers
2
Kathleen asked Sep 18, 2014
33,224 views
The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of$n$$n^2$$n \log n$$n \log^2n$
31 votes
31 votes
6 answers
3
Kathleen asked Sep 18, 2014
19,267 views
The time complexity of the following C function is (assume $n 0$)int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); }$O(n)$$...