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 i^{th} rows and j^{th} column of A
If $t_n$ is the op count for a $n$ by $n$ matrix, then
$t(n) =n\,(t(n-1)+s(n)) $, where $s(n)$ is the time for "submatrix".
Since submatrix has to move $(n-1)^2$ matrix elements, $s(n) = O(n^2) $.
Therefore $t(n) =nt(n-1)+O(n^3) $.
I will let you solve this.
Hint: Do not use this method for large $n$.