
\documentstyle[12pt,twoside]{article}
\input{macros-course}

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{6}{March 23,1995}{In recitation, April 7}

\bigskip


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Give an example of two functions $f$ and $g$ that are incomparable using
asymptotic notation. (i.e. $f(n)$ is not $O(g(n))$, $g(n)$ is not $O(f(n))$,
$f(n)$ is not $\Omega(g(n))$, and so on) 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

Rank the following functions by order of growth; that is find an arrangement
$g_1,g_2,\ldots,g_{30}$ of the functions satisfying $g_1 = \Omega(g_2), g_2 =
\Omega(g_3), \ldots, g_{29} = \Omega(g_{30})$.  Partition your list into
equivalence classes such that $f(n)$ and $g(n)$ are in the same class iff
$f(n) = \Theta(g(n))$.

\[
\begin{array}{cccccc}
\lg(\lg^* n) & 2^{\lg^* n} & (\sqrt{2})^{\lg n} & n^2 & n! & (\lg n)! \\
(3/2)^n & n^3 & \lg^2 n & \lg(n!) & 2^{2^n} & n^{(1/\lg n)} \\
\ln\ln n & \lg^* n & n2^n & n^{\lg\lg n} & \ln n & 1 \\
2^{\lg n} & (\lg n)^{\lg n} & e^n & 4^{\lg n} & (n+1)! & \sqrt{\lg n} \\
\lg^*(\lg n) & 2^{\sqrt{2\lg n}} & n & 2^n & n\lg n & 2^{2^{n+1}} 
\end{array}
\]

Here's a definition for $\lg^* n$ (``log star of $n$'').  We first define
the function $\lg^{(i)} n$.
\[
\lg^{(i)} n = \left\{ \begin{array}{ll}
					n & {\rm if\ } i = 0,\\
					\lg(\lg^{(i-1)} n) & {\rm if\ } i > 0 \text{ and }
\lg^{(i-1)} n > 0,\\
					\text{undefined} & {\rm if\ } i > 0 \text{ and }
\lg^{(i-1)} n \leq 0 \text{ or } \lg^{(i-1)} n \text{ is undefined }
			          \end{array}
			   \right.
\]
Now $\lg^* n = \min\{i \geq 0 : \lg^{(i)} n \leq 1\}$.  For example $\lg^* 2 =
1, \lg^* 4 = 2, \lg^* 16 = 3, \lg^* 65536 = 4, \lg^* (2^{65536})  = 5$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Let $f(n)$ and $g(n)$ be asymptotically positive functions.  Prove or
disprove each of the following conjectures.

\bparts
\ppart $f(n) = O(g(n))$ implies $g(n) = O(f(n))$.
\ppart $f(n)+g(n) = \Theta(\min(f(n),g(n)))$.
\ppart $f(n) = O(g(n))$ implies $2^{f(n)} = O(2^{g(n)})$.
\ppart $f(n) = O((f(n))^2)$.
\ppart $f(n) + o(f(n)) = \Theta(f(n))$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Prove that:
\[
{n \choose {n/2}} = \Theta(2^n/\sqrt{n})
\]

Please be careful when you're manipulating the $\Theta$s.  Remember that you
have to prove both an upper and a lower bound.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Give asymptotic upper and lower bounds for $T(n)$ in the following
recurrence.

\[
T(n) = 2T(n/2) + n^3.
\]


\end{problems}

\end{document}
