Time complexity of LU decomposition

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}$.

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.

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$