\documentclass{article}
\begin{document}


\begin{center}
{\LARGE CS140: Algorithms }\\
\vspace{.1 in}
{\Large Fall 2001}\\
\vspace{.3 in}
{\large Worksheet - Lecture 1}
\end{center}

\vspace{1 in}

\begin{enumerate}
\item

For every positive integer $n$, Algorithm {\cal A} takes $3n^2$ steps on
some input of size $n$.  State whether or not this statement implies the
following.

\begin{enumerate}
\item
Algorithm {\cal A} is $O(n^3)$.
\item
Algorithm {\cal A} is $\theta (n^2)$.
\item
Algorithm {\cal A} is $\Omega(n^2)$.
\end{enumerate}


\vspace{1 in}
\item
Rank the following functions by increasing rate of growth.
Are any of these functions $\theta$-equivalent?
\begin{displaymath}
\lg_2 n \; , \;\;\; \log_3 n \; , \;\;\; \lg n^2 \;  \;\;\; \lg^2 n
\end{displaymath}
\end{enumerate}

\end{document}
