Computational Complexity for lower triangular matrices

Question

I am trying to find the complexity $$ l_{ij} = \frac{1}{l_{jj}} \left(a_{ij} - \sum l_{jk} l_{ik} \right). $$ I have considered $a_{ij} - \sum \ldots$ as being one operation, $l_{jk} \times l_{ij}$ as another one and finally the whole divided by $l_{jj}$ as another operation. Finally i got $O(n^2/2)$ but am not sure if its correct or am i supposed to get a term like $n^3$?

Answer 1

It is confusing to have $l_{ij}$ on the left and on the right. Assuming on the left is a different matrix than on the right.

Think about it like this. Computing each term $l_{ij}$ is 2 operations and the sum, which is $\Theta(n)$, so one operation is $2+\Theta(n) = \Theta(n)$.

Now you have $\Theta(n^2)$ of those to compute to fill the entire matrix $L=(l_{ij}$. So you run for $$ \Theta(n^2) \Theta(n) = \Theta(n^3) $$