This question deals with a function designed to multiply two matrices. It\'s not
ID: 3719579 • Letter: T
Question
This question deals with a function designed to multiply two matrices. It's not necessary that you remember how matrix multiplication is done. The structure of the algorithm should be understandable.
For each of the following groups of lines, select the tightest correct worst-case complexity describing the code in those lines.
O(1)
O(a.numCols)
O(a.numRows)
O(b.numCols)
O(i*j)
O(j*k)
O(j*a.numRows)
O(j*a.numCols)
O(a.numCols*a.numRows)
O(a.numCols*b.numCols)
O(a.numCols^2)
O(a.numCols*a.numRows*b.numCols)
O(a.numCols*a.numRows*b.numRows)
O(a.numCols*a.numRows*b.numCols*b.numRows)
line 10
lines 9-10
line 11
lines 8-11
lines 6-12
lines 5-12
line 4
lines 4-13
A.O(1)
B.O(a.numCols)
C.O(a.numRows)
D.O(b.numCols)
E.O(i*j)
F.O(j*k)
G.O(j*a.numRows)
H.O(j*a.numCols)
I.O(a.numCols*a.numRows)
J.O(a.numCols*b.numCols)
K.O(a.numCols^2)
L.O(a.numCols*a.numRows*b.numCols)
M.O(a.numCols*a.numRows*b.numRows)
N.O(a.numCols*a.numRows*b.numCols*b.numRows)
O. none of the above are correctline 10:
lines 9-10:
line 11:
lines 8-11:
lines 6-12:
lines 5-12:
line 4:
lines 4-12:
Explanation / Answer
We can assume that every elementary operation and condition take O(1) time.
So,
line 10:
Since it contains only one operation and assignment, time complexity would be A. O(1).
line 9-10. It contains a loop which runs a.numCols time. So time complexity would be same. i.e
B. O(a.numCols)
Line 11 is again a single assignment. So, time complexity would be A. O(1).
Line 8-11 would have time complexity O(1) + O(a.numCols) + O(1) = B. O(a.numCols)
Line 6-12 also contain one extra loop. So there are in total two nested loop. Therefore time complexity would be J. O(a.numCols*b.numCols)
Again, line 5-12 has one more loop which runs a.numRows times.
So time complexity would be L. O(a.numCols*a.numRows*b.numCols)
Line 4 is declaring the matrix of size aRows and bCols. So, generally, it takes constant time. However, initializing would take O(a.numRows*b.numCols) which is not an option. So, the answer would be A. O(1) or O.None of the above
Line 4-12 would have same complexity that of three nested loops.
So, the answer is L. O(a.numCols*a.numRows*b.numCols)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.