Think of the straightforward way to obtain the determinant of an n x n matrix A.

Question

Think of the straightforward way to obtain the determinant of an n x n matrix A. Write the pseudo- code for the algorithm (Don't write full code). You can also consider showing an example to illustrate the algorithm. Write the recurrence relation for the time required. What do you think will be the solution to the recurrence? Try to solve it the best you can. Provide the answer in asymptotic notation. Hint: Here is an example showing how determinants are computed for a small 3x3 matrix. Det 3 0 30 4(1) 4 10 8 1011 (1) 8 4 10 8 4 10

Explanation / Answer

function determinant(A) //Recursive function to find the determinant of a square matrix

If size(A,1) != size(A,2)

Print “matrix is not a square matrix”

else if max(size(A))==2

D = (A(1,1)*A(2,2))(A(1,2)*A(2,1))

else

for j=1:size(A,1)

                      temp=A;

        temp(1,:)=[ ];

        temp(:,j)=[ ];

if j==1

D=(A(1,j)*((1)ˆ(j+1))* determinant (temp));

                      else

D=D+(A(1,j)*((1)ˆ(j+1))* determinant (temp));

                     end

                end

   end

end

The above recurrence relation can be written as

T(n)=T(n1)+nc.

Also T(n1)=T(n2)+(n1)c

Therefore,

      T(n)=T(n2)+(n1)c+nc.

      Again,T(n2)=T(n3)+(n2)c

T(n)=T(n3)+(n2)c+(n1)c+nc.

At the end we use T(2)=T(1)+2c=1+2c

Thus

T(n)=1+(2+3++n)c.

We know that

1+2++n=n(n+1)/2,

which implies 2+3++n=(n2+n2)/2

T(n)=1+( n2+n2)c/2

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.