Register

GATE CSE 2004 | Question: 39

21,092 views
60 60 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

7 Answers

0 0 votes

Answer:independent of the storage scheme

Here they mention that they use the array container,which take O(1) time complexity to get and set the element, so it doesn't influence the matrix multiplication  whether if we arrange in row or colum major as we can acess it instantly where ever they are .

The time complexity change, if we change the algorithm we follow or if we used another container like linked list which take O(n) for lookup.

Page:
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2004 | Ques...Next → · GATE CSE 2004 | Ques...
← Previous in category · GATE CSE 2004 | Ques...Next in category → · GATE CSE 2004 | Ques...
Position:
Show:

Related questions

16 16 votes
7 answers 7 answers
15.2k
15.2k views
Kathleen asked Sep 18, 2014
15,245 views
GATE CSE 2004 | Question: 30, ISRO2017-10
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}...
128 128 votes
8 answers 8 answers
53.0k
53.0k views
Kathleen asked Sep 18, 2014
52,955 views
GATE CSE 2004 | Question: 29
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$
41 41 votes
7 answers 7 answers
29.0k
29.0k views
Kathleen asked Sep 18, 2014
29,043 views
GATE CSE 2004 | Question: 83, ISRO2015-40
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)$$...
89 89 votes
13 answers 13 answers
34.3k
34.3k views
Kathleen asked Sep 18, 2014
34,315 views
GATE CSE 2004 | Question: 82
Let $A[1,\ldots,n]$ be an array storing a bit ($1$ or $0$) at each location, and $f(m)$ is a function whose time complexity is $\Theta(m)$. Consider the following program...