Computer Science 477/677 Fall 1998
Short Quiz, September 22, 1998


 0.5in



No books, notes, or scratch paper.  Use pen or pencil, any color.
Use the rest of this page and the backs of the pages for scratch paper.
If you need more scratch paper, it will be provided.


The entire test is 80 points.

\item
True or False. [5 points each]  
		\begin{enumerate}
			\item
Quicksort on an array of $n$ items takes $O(n \log n)$ time.
{\blank}
			\item
Computers are so fast nowadays that it doesn't matter whether programs
are efficient.
{\blank}
			\item
$\log n = O(\sqrt{n})$
{\blank}
			\item
If $f(n) = O(g(n))$, then $\log(f(n)) = O(\log(g(n)))$.
{\blank}
			\item
$\lg^\ast$ grows so slowly that $\lg^\ast(n)$ never exceeds $100$.
{\blank}
			\item
If $\log(f(n)) = O(\log(g(n)))$.
then $f(n) = O(g(n))$.
{\blank}
		\end{enumerate}

        \item
Give a mathematically correct definition of the statement, ``$f(n) = O(n^2)$''
[10 points]
 2in
        \item
Give a mathematically correct definition of the statement,
``$g(n) = \Theta(n^3)$''
[10 points]
 2in

        \item
Solve the following recurrences.  [10 points each]
		\begin{enumerate}
			\item
Give $G(n)$ in  $\Theta$ notation:

$G(n) = G(n-1) + n^2$
 2in
			\item
Give $F(n)$ in $O$ notation:

$F(n) = O(F(\frac{n}{2}))+O(n^2)$
 2in
			\item
Give $H(n)$ in $O$ notation:

$H(n) = H(\log n) + 1$

		\end{enumerate}
 \end{enumerate}