Counting number of multiplications and divisions in the Cholesky decomposition To compute the Cholesky decomposition for an $nxn$ symmetric and positive definite matrix A, use the following algorithm: 
$A=LL^T$, $L=[l_{ij}]$
$$l_{ii}=(a_{ii}-\sum_{k=1}^{i-1}l_{ik}^2)^{1/2}$$
$$l_{ij}=\frac{a_{ij}-\sum_{k=1}^{j-1}l_{ik}l_{jk}}{l_{jj}}$$
where $j=1, 2...i-1$ and $i=1, 2...n$
Then I need to find the number of multiplications and divisions required to compute this. I know for each $l_{ij}$ there are $j-1$ multiplications and 1 division, and for each $l_{ii}$ there are $i-1$ multiplications, but I'm not sure how to find the connection between each $l_{ij}$ and the total number of multiplications and divisions. There are $n$ entries of $l_{ii}$ for the $nxn$ matrix, but how many $l_{ij}$ entries are there? 
 A: I think for this you might have your indices mixed up a bit. First, if $A$ is s.p.d, and $L = [l_{ij}]$, then necessarily, both $i$ and $j$ will range to $n$, as $L$ is an $n \times n$  lower triangular matrix. 
For the algorithm itself, though, we do limit the range of $i$ and $j$ since, by definition, we need only compute the lower triangular portion of the matrix. As the algo for the Cholesky factor is a nested loop, I'm assuming that you have $i$ being the index for the outside loop, and $j$ being the inside. In this case, your definition of $l_{ii}$ is correct, but your definition of $l_{ij}$ is not. For instance, when $i = 1$, we cannot have $j$ looping until $i - 1$. I would begin by rewriting your terms as such
For $i = 1:n$
$$ \quad l_{ii} = \left(a_{ii} - \sum\limits_{k=1}^{i-1} l^2_{jk} \right)^{1/2}$$
You'll notice that for $i = 1$, $l_{11} = a_{11}$ and there will be no multiplication. For each $i = m$, there will be $m - 1$ multiplications. Since we have $i = 1:n$, we can say that the terms $l_{ii}$ have a total of $\sum_{m=1}^{n} m-1 = \frac{n(n-1)}{2}$ total multiplications and no divisions. 
We now look at the second term, which is correctly defined as 
For $j = i + 1:n$
$$l_{ji} = \frac{\left(a_{ji} - \sum_{k=1}^{i-1} l_{jk} l_{ik} \right)}{l_{ii}}$$
Let's begin with counting divisions. Here, now, we have for each $j$, we will have $1$ division. We have to be careful in our calculation, though, as this is a nested loop. The first time our algorithm loops through $j$, we will have $n - 1$ iterations. The second time, (when $i = 2$), we will have $n - 2$ iterations. In total, we will have $\sum\limits_{k=1}^{n-1} n - k = (n-1)n - \frac{n(n-1)}{2}$ total divisions. You'll note here that we sum only to $n-1$ because for $i = n$, we will not be looping through $j$. 
Finally, we need to look at the multiplications. I won't discuss through in detail, but with a pencil and paper, it's easy to sketch out how many we will have. For example, if we assume $n = 4$, we can work through this whole algorithm, treating the cases $i = 1,2,3$, and the subsequent nested multiplications for each $j$ term. Working through this, you can confirm that the number of multiplications that we will have is
$$\sum_{i = 1}^n \sum_{k=i}^{n-i} k$$
This sum is kind of tricky, and I'm not sure if I have a good value for it yet based on $n$. I'll go ahead and post this answer, and if I figure it out (or if anybody in the comments gets it), I'll come back and edit. So for total multiplications and divisions for the Cholesky algorithm, we have
\begin{align}
\frac{n(n-1)}{2} + (n-1)n + \frac{n(n-1)}{2} + \ ?? = 2n(n-1) + \ ??
\end{align}
Good luck on that last sum! The pattern is clear once you write it out, but I haven't quite nailed down a closed form answer for it.
