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.