Please show all work when determining each complexity. thank you in advance. For
ID: 3719407 • Letter: P
Question
Please show all work when determining each complexity. thank you in advance.
For each of the following groups of lines, select the tightest correct worst-case complexity describing the code in those lines. (Choose a Letter for each given line(s), each answer can be used more than once if necessary)
1. line 10
2. lines 9-10
3. line 11
4. lines 8-11
5. lines 6-12
6. line 5-12
7. line 4
8. lines 4-13
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)
none of the above are correct
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 correct
Explanation / Answer
1).Line 10 is
sum += a(i,k) * b(k, j);
It is single addition,single multiplication followed by assignment.all these takes O(1) time.
Overall = O(1) + O(1) + O(1)= O(1)
So,required option a).O(1) is right.
2).line 9-10
for (int k = 0; k < a.numCols; ++k)
sum += a(i,k) * b(k, j);
Line 10 takes O(1) time in single turn.due to line 9 it will execute ( a.numCols -0) times
Therefore,overall time = a.numCols * O(1)= O(a.numCols)
Required option is b).
3).line 11 is
result(i,j) = sum
It is a single assignment operation.it takes O(1) times.
So,required option is a).O(1)
4).line 8-11 are
double sum = 0.0;
for (int k = 0; k < a.numCols; ++k)
sum += a(i,k) * b(k, j);
result(i,j) = sum;
Line 8 is single assignment operation so,it takes O(1) time.
Line 10 and 11 takes O(1) time in single turn.
But due to line 9 they are executed ( a.numCols -0) times.
Therefore,overall time = O(1) + a.numCols*(O(1) + O(1))
=O(a.numCols)
Required option is option b).
5).line 6-12 are
for (int j = 0; j < b.numCols; ++j)
{
double sum = 0.0;
for (int k = 0; k < a.numCols; ++k)
sum += a(i,k) * b(k, j);
result(i,j) = sum;
}
Line 9-11 takes O(a.numCols) time.it is already proved earlier.but due to line 6 line 9-11 is executed ( b.numCols -0) times.line number 8 is executed (b.numCols -0) times.
Overall time = (b.numCols * O(1)) + b.numCols *O(a.numCols)
= O(b.numCols * a.numCols)
Required option is j).
6).line 5-12 are
for (int i = 0; i < a.numRows; ++i)
for (int j = 0; j < b.numCols; ++j)
{
double sum = 0.0;
for (int k = 0; k < a.numCols; ++k)
sum += a(i,k) * b(k, j);
result(i,j) = sum;
}
Line 6-10 takeO(a.numCols * b.numCols) time in single turn .but due to line # 5 it is executed total of (a.numRows - 0) times.
Overall time = a.numRows * O(a.numCols * b.numCols)
= O(a.numRows * a.numCols * b.numCols)
So,required option is L).
7).line 4 is
Matrix result (aRows, bCols);
It is a function call which we can see takes O(1) time
Overall time = O(1)
8).line 4-13
Line 5-12 takes O(a.numCols * b.numRows *a.numRows) times(already proved earlier)
Line 4-13 takes
Overall = O(1) + O(a.numCols * a.numRows * b.numCols) + O(1)
= O(a.numRows * a.numCols * b.numCols)
Required option is option L).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.