How to calculate the complexity of a given Algorithm

Question

I have the following algorithm given:

Input: Regular Matrix $A \in \mathbb R^{n,n}$ Output: LU-Decomposition of A = LU

for k = 1, . . . , n do

for j = k, . . . , n do $r_{kj} = a_{kj} − \sum_{i=1}^{k-1} l_{ki}r_{ij}$

end for

for i = k + 1, . . . , n do

$l_{ik} = (a_{ik} − \sum_{j=1}^{k-1} l_{ij}r_{jk})/r_{kk}$

end for

end for

Given every elementary operation (+,-,*,/) has the cost 1, how can it be derived that the complexity of this algorithm is 2/3n^3 - 1/2n^2 - 1/6n? I am really interested in understanding how such a closed formulae for the complexity is derived.

Answer 1

In order to compute $r_{kj}$, you need to do $k-1$ multiplications and $k$ additions, for a total of $2k-1$ operations. You need to do this for $j=k...n$, i.e. $n-k$ times for a total of $(n-k)(2k-1)$ operations to compute all of the $r_{kj}$ for a given $k$. Then you need to do this for all $k$ from 1 to $n$, so the cost of this first loop is $$ \sum_{k=1}^n (n-k)(2k-1) = n\sum_{k=1}^n (2k-1) - \sum_{k=1}^n k(2k-1) \\ = 2n\sum_{k=1}^n k - \sum_{k=1}^n 1 - 2 \sum_{k=1}^n k^2 + \sum_{k=1}^n k \\ = 2n\frac 12 n(n+1) - n - \text{something} + \frac 12 n(n+1). $$ You need to look up the formula for the third sum: I forgot its exact value, but it's proportional to $n^3$.

You can do the same calculation for the second inner loop of your algorithm.