The following very simple algorithm calculates the determinant of a matrix in a
ID: 3688261 • Letter: T
Question
The following very simple algorithm calculates the determinant of a matrix in a recrusive fashion with no optimization at all. Count how many operations (+, -, * and /) are done for a matrix of size n to get an estimate of the big-O of this algorithm based on FLOPS if you were using this algorithm to solve a system of equations using Cramer's Method. Detail your reasoning and counting carefully. While you may want to consider systems of equations of increasing size your final answer must be for a system of arbitrary size n.
function minors_det(A)
% get size of matrix A
d=0
N=size(A)
if N=2
d=A(1,1)*A(2,2)-A(1,2)*A(2,1)
else
for i=1:N
d=d+(-1)^(1+i)*A(1,i)*minors_det(submatrix(A,i));
end;
end;
return d;
Note that submatrix() function takes a matrix A and removes row 1 and column i to create a new smaller matrix.
A(i,j) refers to the element in the ith rows and jth column of A
Explanation / Answer
Total operations are 5+N^2 because if N=2 it has 3 operations and In remaining cases it is 2+N^2. therefore the total number of operations are 5+N2.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.