\problemdata      
        {?} % latex-friendly label for the prob.
        {Asymptotics} % The topic(s) of the problem content.
        {?} % Source (if known)
        {Fall 2001, final} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).

\begin{problem}
For each pair of functions $(f(n), g(n))$ in the table below, indicate
whether the statement at the top of the column is true (e.g., whether
$f(n) = O(g(n))$). Your answer should be ``yes'' or ``no'' in each
box; no explanations needed.

\large{
\[
\begin{array}{|cc|c|c|}
\hline
f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n)) \\ \hline\hline
2^n         & 3^n           &&\\\hline
%
2^{n^2}     & 3^n           &&\\\hline
%
2^{(\log_2 n)^2} & n^2      &&\\\hline
%
n^3 & (\log_2 n)n^{2.9}      &&\\\hline
%
(n!)^2       & n^n          &&\\\hline
\end{array}
\]
}

\solution{
\newcommand\y{\text{yes}}
\newcommand\n{\text{no}}
\begin{equation*}
\begin{array}{|cc|*{3}{c|}}
\hline
f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n))\\\hline\hline
2^n         & 3^n               & \y & \n  \\\hline
%
2^{n^2}     & 3^n               & \n & \y \\\hline
%
2^{(\log_2 n)^2} & n^2          & \n & \y \\\hline
%
n^3 & (log_2 n)n^{2.9}          & \n & \y \\\hline
%
(n!)^2       & n^n              & \n & \y \\\hline
\end{array}
\end{equation*}
}

\end{problem}
