<\body> Here's the long way around for reference: To establish what we're talking about, here's some Matlab/Octave code to perform the LU decomposition via Gaussian eliminiation: <\with|par-par-sep|0> Now all we need to do is count up the number of arithmetic operations: <\itemize> The innermost loop executes multiplications and subtractions for the inner product, as well as one division.\ <\equation*> \=> The innermost loop is executed from (We call for simplicity.) to , so <\equation*> \=[2(n-i)+1]. The outer loop simply executes the inner loop times, without any additional operations, so. <\equation*> \=[2(n-i)+1]. Possibly the least annoying way to show our result is induction: The base case () is easy: <\equation*> [2(n-i)+1]=0 and <\equation*> --=0. Then, suppose we know that <\equation*> \(n)=n-n-n, let's show the same thing for (n+1)>: <\eqnarray*> ||(n+1)>>|||[2(n+1-i)+1]>>|||(n)+[2(n+1-i)+1]-[2(n-i)+1]>>|||(n)+[2(n+1-i)+1]+[2(n+1-i)+1]-[2(n-i)+1]>>|||(n)+[2(n+1-n-1)+1]+[2(n+1-i)+1]+[2(n+1-i)+1]-[2(n-i)+1]>>|||(n)+1+1+[2(n+1-i)+1-2(n-i)-1]>>|||(n)+1+1+[2(n+1-i)-2(n-i)]>>|||(n)+1+1+2>>|||(n)+1+1+2(n-s-1)>>|||(n)+1+-1+2n-2s>>|||(n)+1-(n-1)+2n(n-1)-2s>>|||(n)+1-(n-1)+2n(n-1)-2>>|||(n)+2-n+n(n-1)>>|||n-n-n+2-n+n(n-1)>>>> \; Evaluating this operations count yields <\eqnarray*> ||[2(n-i)+1]>>|||[2n-2i+1]>>|||(2n+1)(n-s-1)-2i>>|||(2n+1)(n-s-1)-2i>>>> For reference, the code yields the following output: <\with|par-par-sep|0> <\initial> <\collection>