\problemdata      
        {?} % latex-friendly label for the prob.
        {Asymptotics} % The topic(s) of the problem content.
        {?} % Source (if known)
        {Fall 2001, PS7} % 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))$).  Assume $k\geq 1$, $\epsilon > 0$, and $c > 1$ are
constants. Your answer should be in the form of a table with ``yes'' or
``no'' in each box.
\begin{equation*}
\begin{array}{|cc|*{3}{c|}}
\hline
f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n)) & f(n) = \Theta(g(n)) \\\hline\hline
\log^k n & n^\epsilon &&&\\\hline
n^k & c^n &&&\\\hline
\sqrt{n} & n^{\sin n\pi/2} &&&\\\hline
2^n & 2^{n/2} &&&\\\hline
\log(n!) & \log(n^n) &&&\\\hline
\end{array}
\end{equation*}

\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)) & f(n) =
\Theta(g(n)) \\\hline\hline
\log^k n & n^\epsilon & \y & \n & \n \\\hline
n^k & c^n & \y & \n & \n \\\hline
\sqrt{n} & n^{\sin n\pi/2} & \n & \n & \n\\\hline
2^n & 2^{n/2} & \n & \y & \n \\\hline
\log(n!) & \log(n^n) & \y & \y & \y \\\hline
\end{array}
\end{equation*}

Following are some hints on deriving the table above:\\ \iffalse (a) See
notes on $O$-notation. (to appear)\\ \fi

Row:

(2) Polynomial growth versus exponential growth. (See Theorem 7.6, Notes
7.)

(3) $n^{\sin n\pi/2}=1$ for even values of $n$.  So no constant times
$n^{\sin n\pi/2}$ will be an upper bound on $\sqrt n$ as $n$ ranges over
even numbers.  When $n \equiv 1 \bmod 4$, then $n^{\sin n\pi/2}= n^1 =n$,
so no constant times $\sqrt n$ will be an upper bound on $n^{\sin n\pi/2}$
as $n$ ranges over numbers $\equiv 1 \bmod 4$.

(4) $\cfrac{2^n}{2^{n/2}}=2^{n/2}$ grows without bound as $n$ grows -- it
is not bounded by a constant.

(5) See Rosen \S 1.8 Ex. 61,62 
}

\end{problem}
