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




\begin{problem}
Indicate which of the following holds for each pair of functions $(f(n),
g(n))$ in the table below.  Assume $k\geq 1$,
$\epsilon > 0$, and $c > 1$ are constants.
\begin{equation*}
\begin{array}{|cc|c|c|c|c|c|c|}
\hline
f(n) & g(n) & 
f = O(g) & f=o(g) & 
g = O(f) & g=o(f) & 
f = \Theta(g) & f\sim g 
\\\hline\hline
2^n & 2^{n/2} & & & & & & \\\hline
\sqrt{n} & n^{\sin n\pi/2} & & & & & & \\\hline
\log(n!) & \log(n^n) & & & & & & \\\hline
n^k & c^n & & & & & & \\\hline
\log^k n & n^\epsilon & & & & & & \\\hline
\end{array}
\end{equation*}

%\item $f=O(g)$
%\item $f=o(g)$
%\item $g=O(f)$
%\item $g=o(f)$
%\item $f = \Theta(g)$
%\item $f \sim g$
%\item none of the above.
%
%\begin{equation*}
%\begin{array}{|cc|}
%\hline
%f(n) & 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{array}{|cc|c|c|c|c|c|c|}
\hline
f(n) & g(n) & 
f = O(g) & f=o(g) & 
g = O(f) & g=o(f) & 
f = \Theta(g) & f\sim g 
\\\hline\hline
2^n & 2^{n/2} & 
\n & \n & \y & \y & \n & \n
\\\hline
\sqrt{n} & n^{\sin n\pi/2} & 
\n & \n & \n & \n & \n & \n
\\\hline
\log(n!) & \log(n^n) & 
\y & \n & \y & \n & \y &  \y
\\\hline
n^k & c^n &             
\y & \y & \n & \n & \n & \n
\\\hline
\log^k n & n^\epsilon & 
\y & \y & \n & \n & \n & \n
\\\hline
\end{array}
\]

Following are some hints on deriving the table above:

\begin{itemize}

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

\item[(b)] 
When $n$ is even, then $n^{\sin n\pi/2}=1$.  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$.

\item[(c)] 
\begin{eqnarray}
\log(n!) & = & \log \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \pm
c_n\label{logS}\\
& = & \log n + n(\log n - 1) \pm d_n \label{logprod}\\
& \sim & n \log n\label{sim}\\
& = & \log n^n.
\end{eqnarray}
where $a \leq c_n,d_n \leq b$ for some constants $a,b \in \reals$ and all
$n$.  Here equation~(\ref{logS}) follows by taking logs of Stirling's
formula,~(\ref{logprod}) follows from the fact that the log of a product
is the sum of the logs, and~(\ref{sim}) follows from Problem~\ref{o+o},
part~\ref{f+o} because any constant, $\log n$, and $n$ are all $o(n \log
n)$.

\item[(d)] 
\emph{Polynomial} growth versus \emph{exponential} growth.

\item[(e)] 
\emph{Polylogarithmic} growth versus \emph{polynomial} growth. 

\end{itemize}

}
\end{problem}

