Time complexity of LU decomposition 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$?

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