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

• I get it up to the $2 \sum_{j=0}^{n-1} (j^2 + j)$ .. but then I don't see how did you get the next step. I must be missing something. Jun 18, 2015 at 22:19
• You can use the classical formulas for the sums of the first $n$ squares and the first $n$ integers : $$\sum_0^n{k^2} =\frac{1}{6} {\left(2 n + 1\right)} {\left(n + 1\right)} n$$ and $$\sum_0^n{k} =\frac{n(n+1)}{2}$$ and adapt them to $n-1$ Jun 18, 2015 at 22:29
• I am a little confused. Why don't any of the answers here also consider the part where we have to also find the upper triangular matrix?
– user681443
Feb 28, 2020 at 1:58

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$

• I don't see how you get that $\sum_i^n (i)^2 = n^2/3 + n^2/2+n/6$ Jun 18, 2015 at 22:22
• Here math.stackexchange.com/questions/48080/… is the MSE discussion about it. There are many proofs. One proof is by induction using the formula for $\sum_i^n i$ as a starter. There are some number theoretic proofs. It's a good fact to know. Jun 18, 2015 at 22:27