# Complexity/Operation count for the forward and backward substitution in the LU decomposition?

If I have a linear system of equations $Ax=b$ where $A \in \mathbb{R} ^{n\times n}, x \in \mathbb{R} ^{n}, b \in \mathbb{R} ^{n}$ this system can be solved for $x$ via an LU decomposition: $$A = LU$$ where $U \in \mathbb{R} ^{n\times n}$ is upper triangular and $L \in \mathbb{R} ^{n\times n}$ is lower triangular.

I understand a forward substitution is then required where one first solves:

$$Ly=b$$ for $y$.

And then we solve: $$Ux=y$$ for $x$.

I am currently trying to determine the operation count or the FLOPS for each of the forward substitution and backward substitution. I have seen that the correct value is approximately given by $\mathcal{O}(n^{2})$ flops but I am unsure how one can arrive at this value.

I can see that for the backward substitution, for example, the system is represented as:

$$\begin{bmatrix} u_{11} & u_{12} & \cdots & u_{1n} \\ 0 & u_{22} &\cdots &u_{2n} \\ \cdots& \cdots & \ddots &\vdots \\ 0 & 0 & \cdots & u_{nn} \end{bmatrix} \begin{bmatrix} x_{1}\\ x_{2}\\ \vdots \\ x_{n} \end{bmatrix} = \begin{bmatrix} y_{1}\\ y_{2}\\ \vdots \\ y_{n} \end{bmatrix}$$

From which:

$$x_{i} = \frac{1}{u_{ii}} \left ( y_{i} - \sum_{j=i+1}^{n}u_{ij}x_{j} \right ); i = n, ..., 1$$

From an equation like this, how can one identify the approximate operation count?

If your matrix is $$n\times n$$ you have the following operations
1. $$n$$ divisions,
2. $$\frac{n^2-n}{2}$$ sums,
3. $$\frac{n^2-n}{2}$$ multiplications.
The number of divisions is clear because you have $$n$$ rows. The number of sums and multiplications are $$\sum_{i=1}^{n-1}n^2=\frac{n^2-n}{2}$$. It comes from $$\sum_{j=1+1}^{n}u_{ij}x_j$$.
The total number of operations is $$2n^2-n=\mathcal{O}(n^2)$$