\documentclass[a4paper, 12pt, fleqn]{article}
\usepackage{amsmath}

\begin{document}
\noindent
\textbf{First name:} Monika \\
\textbf{Last name:} Wunderlich\\
\textbf{Date:} 16.12.04 \\
\textbf{Homeworknumber:} 2 \\
\textbf{Homework Title:} 2.22\\
\newline
\newline
\textbf{Problem description:} 
\newline
Verify that the dominant term in the operation count (number of multiplications or number of additions) for LU factorization of a matrix of order $n$ by Gaussian elimination is $n^3/3$.\\
\newline
\textbf{Problem solution:} 
\newline
Algorithm for the Gaussian elimination:
\vspace*{1mm}\\
\hspace*{0,5cm} \texttt{for $k = 1: (n-1)$}\\
	\hspace*{1cm} \texttt{for $i =  (k+1) : n$}\\
		\hspace*{1,5cm} $Ag(i,k) =  \frac{Ag(i,k)}{Ag(k,k)}$\\
		\hspace*{1,5cm} \texttt{for $j = (k+1) : n$}\\
			\hspace*{2cm} $Ag(i,j) = Ag(i,j) - Ag(i,k) \cdot Ag(k,j)$\\
		\hspace*{1,5cm} \texttt{end}\\
	\hspace*{1cm} \texttt{end}\\ 
\hspace*{0,5cm} \texttt{end} \\
 
\par 
%\vspace{1mm}

\hspace*{-0,6cm}The number of multiplications $m$ in the algorithm:
\begin{eqnarray}
	m &=& \sum_{k=1}^{n-1} \left(  \sum_{i=k+1}^{n} \left( 1 + \sum_{j=k+1}^{n}1\right) \right) \notag %\\ \-
	=  \sum_{k=1}^{n-1} \left(  \sum_{i=k+1}^{n} \left( 1 + (n-(k+1)+1) \right) \right) \notag \\ 
	&=&  \sum_{k=1}^{n-1} \left(  (n-(k+1)+1)\cdot (n-k+1) \right) \notag \\ 
	\- &=& \sum_{k=1}^{n-1} \left( n^2 +n -(2n +1)k + k^2 \right) \notag \\ 
	\- &=& (n-1)\cdot (n^2+n) -(2n+1)\frac{n(n-1)}{2} + \frac{n(n-1)(2n-1)}{6} \notag \\ \- 
	\- &=& n^3 \left( 1-\frac{2}{2} + \frac{2}{6} \right) + n^2 \left( 1-1+\frac{2-1}{2}-\frac{2+1}{6} \right) +n \left( -1+1+\frac{1}{2} +\frac{1}{6} \right) \notag \\ \-
	&=& \frac{1}{3}n^3 + \frac{2}{3}n. \notag
 \end{eqnarray} 

\par 
\hspace*{-0,6cm}The number of additions $a$ in the algorithm:
\begin{eqnarray}
	a &=& \sum_{k=1}^{n-1} \left(  \sum_{i=k+1}^{n} \left( \sum_{j=k+1}^{n}1\right) \right) \notag \\
	&=&  \sum_{k=1}^{n-1} \left(  \sum_{i=k+1}^{n} \left(n-(k+1)+1 \right) \right) \notag \\
	&=&  \sum_{k=1}^{n-1} \left(  (n-(k+1)+1)\cdot (n-k) \right) \notag \\
	&=& \sum_{k=1}^{n-1} \left( n^2 -2nk + k^2 \right) \notag \\
	&=& (n-1)\cdot n^2 - 2n\frac{n(n-1)}{2} + \frac{n(n-1)(2n-1)}{6} \notag \\
	&=& n^3 \left( 1-\frac{2}{2} + \frac{2}{6} \right) + n^2 \left( -1+\frac{2}{2}-\frac{2+1}{6} \right) +n \frac{1}{6}  \notag \\
	&=& \frac{1}{3}n^3 - \frac{1}{2} n^2 + \frac{1}{6}n. \notag
 \end{eqnarray} 

\vspace{1mm}
\par 
\hspace*{-0,6cm}\textbf{Results:} \\
%\newline
The dominant term in the operation count is both for additions and for multiplications $n^3/3$

\end{document}