Time complexity of LU decomposition

Question

I am trying to derive the LU decomposition time complexity for an $n \times n$ matrix.

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

$$ \sum_i^n 2(n-i) (n-i+1) $$

How do we get from this sum to a total cost of $\frac{2}{3}n^3$?

Answer 1

An easy transformation ($j = n-i+1$) easily shows that \begin{align} \sum_{i=1}^n 2(n-i) (n-i+1) &= 2 \sum_{j=0}^{n-1}j(j+1)\\ &= 2 \sum_{j=0}^{n-1}(j^2+j)\\ &= 2 \left(\frac{1}{3} n^{3} - \frac{1}{3} n\right) \end{align}

Then, since we are interested only in the asymptotic behaviour, we drop the $\frac{2}{3}n$ part, and what's left is $\frac{2}{3} n^{3}$.

Answer 2

Well, $$ 2\sum_i^n (n-i)(n-i)+(n-i) = 2\sum_i^n (n-i)^2+2\sum_i^n(n-i) $$

Now, let's reindex these sums backwards so it's pretty. $$ 2\sum_i^n (i)^2+2\sum_i^n(i) $$

Now, if you know a little induction (or wolfram alpha) you can prove that $$ \sum_i^n (i)^2 = n^3/3+n^2/2+n/6 $$ and $\sum_i^n i$ is at worst $n^2$. So we have $\frac{2}{3}n^3$

Answer 3

Below is the gist. Hope the loose but cleaner notation can help our memory.

$\sum_i^n 2(n-i) (n-i+1)\approx2\sum n^2\approx2\int x^2dx\approx\frac{2}{3}x^3$

$\approx$ is in the sense of top term coefficient.