\documentclass[12pt,a4paper]{article}
\usepackage{ngerman}
\usepackage{amsmath}
\renewcommand{\labelenumi}{(\emph{\alph{enumi}})}
\renewcommand{\labelenumii}{\arabic{enumii}.}

\begin{document}
\noindent\textbf{First name:} Christoph\\
\textbf{Last Name:} Oberauer\\
\textbf{Email:} coberau@cosy.sbg.ac.at\\
\textbf{Date:} 07.12.2002\\
\textbf{Homework number:} 3\\
\textbf{Homework Title:} Exercise 3.24


\paragraph{Problem description:\\}
Verify that the dominant term in the operation count (number of multiplcations or number of additions) for solving an $m \times n$ linear least squares problem using the normal equations and Cholesky factorization in $mn^2/6+n^3/6$.


\paragraph{Problem solution:\\}
Calculate number of operations for
\begin{enumerate}
\item
Normal equations
\item
Cholesky factorization
\end{enumerate}


\paragraph{Results:}
\begin{enumerate}
\item
$A^TA$: The resulting matrix is symmetric has $n \times n$ elements. Therefore actually $\frac{n(n+1)}{2}$ elements have to be calculated. For each element $m$ multiplications and $m-1$ additions have to be made.\\
$A^Tb$: The resulting vector has $n$ elements, each requiring $m$ multiplications and $m-1$ additions.\\
If additions are left out, because the computing-costs are much less than for multiplications and assuming a large $n$, the dominant term for normal equations is
$$\frac{n^2m}{2}$$
\item
Cholesky factorization needs $\sum_{j=1}^{n}{\sum_{k=1}^{j-1}{(n-j+1)}}$ multiplications and the same number of additions plus $n$ calculations of a square root and $\sum_{j=1}^{n}{n-j}$ divisions.
$$\sum_{j=1}^{n}{\sum_{k=1}^{j-1}{(n-j+1)}}=$$
$$\sum_{j=1}^{n}{(j-1)n-(j-1)j+(j-1)}=$$
$$\sum_{j=1}^{n}{jn-n-j^2+j+j-1}=$$
$$n\frac{n(n+1)}{2}-n^2-\frac{n(n+1)(2n+1)}{6}+2\frac{n(n+1)}{2}-n=$$
$$\frac{3(n+2)n(n+1)}{6}-\frac{(2n+1)n(n+1)}{6}-n^2-n=$$
$$\frac{(n+5)n(n+1)}{6}-n^2-n=$$
$$\frac{n^3+5n^2+n^2+5n-6n^2-6n}{6}=$$
$$\frac{n^3-n}{6}$$
Thus the dominant term for cholesky factorization is (again leaving out additions, as well as $n$ square roots on $O(n^2)$ divisions)
$$\frac{n^3}{6}$$
\end{enumerate}
The overall dominant term in the operation count evaluates to 
$$\frac{n^2m}{2}+\frac{n^3}{6}$$


\paragraph{Discussion and Comments:}
\end{document}