Calculation of the complexity of the determinant of a recursive algorithm

Question

I wrote an algorithm for calculating the determinant of the nxn matrix based on the Laplace extension:

I got the repetition ratio below: T(n) = n(n² + T(n-1))

On Wikipedia, I read that this should give the result T(n) = O(n!) , But I don’t know how to prove it (albeit intuitively).

Answer 1

The formula is correct, but your repetition ratio is not. You do not need n² , since you do not need to save or generate submatrices.

M ij is the determinant of the submatrix (n-1) x (n-1) . Therefore, you need to calculate the determinants of n for n different matrices. Thus, the correct repetition ratio is T(n) = n⋅T(n-1) + 2n-1 . It simplifies

 T(n) = n ⋅ T(n-1) + 2n-1 = n ⋅ (n-1) ⋅ T(n-2) + n ⋅ (n-1) = n ⋅ ( (n-1) ⋅ ( (n-2) ⋅ (...) + n-3 ) + n-2 ) + n-1 = 2n-1 + n ⋅ (2(n-1)-1) + n ⋅ (n-1) ⋅ (2(n-2)-1) + ... + n! < 2 ⋅ n + 2 ⋅ n ⋅ (n-1) + 2 ⋅ n ⋅ (n-1) ⋅ (n-2) + ... + 2 ⋅ n! + n! = 2 ⋅ (n + n ⋅ (n-1) + ... + n!/2) + 3 ⋅ n! < 2 ⋅ (n!/(n-1)! + n!/(n-2)! + ... + n!/2!) + 3 ⋅ n! 

Because of 2⋅n!/k! ≤ n!/(k-1)! 2⋅n!/k! ≤ n!/(k-1)! for all k ≥ 2 we get

  n!/(n-1)! + n!/(n-2)! + n!/(n-3)! + ... + n!/2! ≤ n!/(n-2)! + n!/(n-2)! + n!/(n-3)! + ... + n!/2! ≤ n!/(n-3)! + n!/(n-3)! + ... + n!/2! ≤ n!/(n-4)! + ... + n!/2! ≤ ... ≤ n!/2! + n!/2! ≤ n! 

So,

 T(n) = n ⋅ T(n-1) + 2n-1 < 2 ⋅ (n!/(n-1)! + n!/(n-2)! + ... + n!/2!) + 3 ⋅ n! ≤ 2 ⋅ n! + 3 ⋅ n! = 5 ⋅ n! = O(n!) 

So your algorithm works in O(n!)