Lower bound for matrix determinant algorithm 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?
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.)