\documentclass[12pt]{article}

\usepackage[T1]{fontenc} 
\usepackage{fullpage,amsmath,amsfonts}

\begin{document}

\title{Algorithms and Data Structures}
\author{Summer Semester 2022}
\date{For discussion on Tuesday, May 10, 2022}
\maketitle

\begin{enumerate}
\item Reconsider the two algorithms for computing prefix averages
which we discussed on May 3 (see GTG, Section 3.3.3), one that
computes the prefix average in $O(n^2)$ time, the other which finishes
in $O(n)$ time.

Modify your Python code such that, in one plot, you show
\begin{enumerate}
\item the recorded timings of the $O(n^2)$ algorithm,
\item the recorded timings of the $O(n)$ algorithm,
\item a reference line $f(n) = \text{const} \cdot n^2$,
\item a reference line $f(n) = \text{const} \cdot n$.
\end{enumerate}

\emph{Hints:}

\begin{itemize}
\item If you did not manage to complete a working version of both
algorithms during the tutorial session on Tuesday, you can find a
working version on the class web site, named
\verb+2022-05-03_prefix_averages.py+.  This file also contains an
alternative implementation of the $O(n^2)$ algorithm---you should be
able to easily see which is which.

\item To plot several data sets into one plot, just issue separate
calls to \texttt{loglog} without calling \texttt{figure()} again.

\item It is good practice to draw a legend.  Example:
\begin{verbatim}
  legend(('first data set', 'second data set', ...))
\end{verbatim}

\end{itemize}

\item See the attached excerpt from GTG, p.~143.  For each of the five
algorithms, state the expected running time in big-Oh notation.


\end{enumerate}
\end{document}
