Question

Time complexity of solving linear equations by lu decompostion and cholesky method

Answer 1

Eliminating the first column will require n additions and n multiplications for n−1 rows. Therefore, the number of operations for the first column is 2n(n−1). For the second column, we have n−1 additions and n−1 multiplications, and we do this for (n−2) rows giving us 2(n−1)(n−2). Therefore, the total number of operations required for the full decomposition can be written as

∑in2(n−i)(n−i+1)