Fdtxjr

If I have a linear system of equations $Ax=b$ where $A in mathbbR ^ntimes n, x in mathbbR ^n, b in mathbbR ^n $ this system can be solved for $x$ via an LU decomposition: $$A = LU$$ where $U in mathbbR ^ntimes n$ is upper triangular and $L in mathbbR ^ntimes 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 $mathcalO(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:

$$beginbmatrix
u_11 & u_12 & cdots & u_1n \
0 & u_22 &cdots &u_2n \
cdots& cdots & ddots &vdots \
0 & 0 & cdots & u_nn
endbmatrix beginbmatrix
x_1\
x_2\
vdots \
x_n
endbmatrix = beginbmatrix
y_1\
y_2\
vdots \
y_n
endbmatrix$$

From which:

$$x_i = frac1u_ii left ( y_i - sum_j=i+1^nu_ijx_j right ); i = n, ..., 1$$

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

If your matrix is $ntimes n$ you have the following operations

1. 
   $n$ divisions,


2. 
   $fracn^2-n2$ sums,


3. 
   $fracn^2-n2$ multiplications.

The number of divisions is clear because you have $n$ rows. The number of sums and multiplications are
$sum_i=1^n-1n^2=fracn^2-n2$. It comes from $sum_j=1+1^nu_ijx_j$.

The total number of operations is $2n^2-n=mathcalO(n^2)$

I hope it solves your doubts