\documentclass{article} 
\usepackage[utf8]{inputenc} 
\usepackage{amssymb} 
\title{Homework 06} 
\author{Adrian German} 
\date{January 12, 2002} 
\begin{document} 
\maketitle 
\tableofcontents
 
\section{Introduction} 

We first looked at the Selection Sort algorithm as described on pp. 636-643.
 
\section{The Order of Growth of Selection Sort}
 
Let $n$ be the size of the array. The total number of visits is 
$$T(n) = n + 2 + (n - 1) + 2 + ... + 2 + 2 = \frac{1}{2} n^2 + \frac{5}{2} n - 3$$ 

\noindent So selection sort is an $O(n^2)$ algorithm. 

\section{Big-Oh Notation} 

Suppose there is a function $T(n)$ that represents the running time of an algorithm 
as a function of its input size. Suppose then that there is another function $f(n)$ 
that we want to compare $T(n)$ to. Then we say that $$T(n) = O(f(n))$$ if there exist 
$n_0 \in \mathbb{N}$ and $C \in \mathbb{R}$ such that $$\frac{T(n)}{f(n)} \le C$$ for 
all $n \ge n_0$.

\end{document}