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.

| cite | improve this answer | |
  • $\begingroup$ ..and how do I then bring the loops together to get the final result? And thanks a lot of course $\endgroup$ – Steven2143 Mar 19 '13 at 10:19
  • 1
    $\begingroup$ 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. $\endgroup$ – Wolfgang Bangerth Mar 19 '13 at 11:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.