1
$\begingroup$

I have the an algorithm for computing a matrix determinant:

$$\ det(A) = \sum_{i=1}^n (-1)^{i-1} \cdot A_{i1} \cdot det(A_{-i,-1})$$

Where $\ A_{-i,-1} $ is the matrix $\ A $ without the row $\ 1 $ and column $\ i $

Drawing the recurrence tree, I see each level $\ k $ has $\ \frac{(n-1)!}{(n-k)!} $ nodes. So I think the upper bound for this algorithm to be $\ O(n!) $ because the height of the tree is $\ n $ and the row sum of each level is the same as number of nodes. How can I set lower bound using recurrence tree? I've found this answer where the lower bound of such arithmetic operation in a matrix is set to be $\ \Omega(n^3) $ though , can not understand why?

$\endgroup$
3
  • $\begingroup$ Your method can be improved upon significantly. The lower bound is not on a particular algorithm, but rather on a class of algorithms. In fact, the determinant can be computed in $O(n^\omega)$, where $\omega $ is the matrix multiplication exponent, which is smaller than 3. $\endgroup$ Nov 9, 2020 at 15:44
  • $\begingroup$ Sorry I should have added that I was given a particular algorithm that just do exactly as the formula above. Does it change anything? Also, could you elaborate why the determinant can be computed in $\ O(n^{\omega}) $ ? $\endgroup$
    – bm1125
    Nov 9, 2020 at 16:19
  • $\begingroup$ I understand your question. I was trying to explain the other answer. As for the fast algorithm, you can find it in textbooks such as CLRS, and probably also on Wikipedia. $\endgroup$ Nov 9, 2020 at 16:26

1 Answer 1

1
$\begingroup$

The complexity of your algorithm on $n \times n$ matrices satisfies the recurrence $$ T(n)=nT(n-1) + O(n^3), $$ with a base case of $T(1) = O(1)$. In particular, $T(n) \geq n! T(1)$.

In the other direction, let $S(n) = T(n)/n!$. Then $$ S(n) = S(n-1) + O(n^3/n!), $$ with a base case of $S(1) = O(1)$. Since $\sum_{n=0}^\infty n^3/n!$ converges, we get $S(n) = O(1)$, and so $T(n) = O(n!)$. (The same argument also proves the lower bound.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.