# How to calculate the complexity of a given Algorithm

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.

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.

• ..and how do I then bring the loops together to get the final result? And thanks a lot of course Commented Mar 19, 2013 at 10:19
• I've computed for you how much it costs to execute the first of the inner loops. You will have to compute how much it costs to execute the second of the inner loops and then you add up the two costs to get the overall number. Commented Mar 19, 2013 at 11:58