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

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

\begin{document}

\psol{6}{April 7, 1995}

\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) 


Here's an example:
\[
f(n) = \left\{ \begin{array}{ll}
				n & \text{if } n \text{ is even} \\
				n2^n & \text{if } n \text{ is odd}
				\end{array} \right.
\\
g(n) = \left\{ \begin{array}{ll}
				n2^n & \text{if } n \text{ is even} \\
				n & \text{if } n \text{ is odd}
				\end{array} \right.
\]

$f(n)$ can't be $O(g(n))$ since it would imply that $n2^n \leq
cn$ for $n$ large and odd.  Similarly $f(n)$ can't be $\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$.


The ranking is: ($f(n) \prec g(n)$ means $f(n) = \Omega(g(n))$ and $f(n) \sim g(n)$ means $f(n) =
\Theta(g(n))$).

\begin{eqnarray*}
\lefteqn{1 \sim n^{1/\lg n} \prec \lg\lg^* n \prec \lg^*\lg n \sim \lg^*n \prec
2^{\lg^* n} \prec \ln\ln n \prec \sqrt{\lg n} \prec \ln n \prec \lg^2 n} \\
 & &\prec 2^{\sqrt{2\lg n}} \prec \sqrt{2}^{\lg n} \prec n \sim 2^{\lg n} 
\prec n\lg n \sim \lg n! 
\prec n^2 \sim 4^{\lg n}  \prec n^3\\
& & \prec (\lg n)! \prec {\lg n}^{\lg n} \sim n^{\lg\lg
n}  \prec (3/2)^n \prec 2^n \prec n2^n \prec
e^n \prec n! \prec (n+1)! \prec 2^{2^n} \prec 2^{2^{n+1}}
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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))$.

This is false.  $1$ is $O(n)$ but $n$ isn't $O(1)$.

\ppart $f(n)+g(n) = \Theta(\min(f(n),g(n)))$.
This is false.  Let $f(n) = 1$, $g(n) = n$. $1+n$ isn't $\Theta(1)$.

\ppart $f(n) = O(g(n))$ implies $2^{f(n)} = O(2^{g(n)})$.
This is false. $2^{n+1}$ is $O(2^n)$ but $2^{2^{n+1}}$ isn't $O(2^{2^n})$.
Why?

\ppart $f(n) = O((f(n))^2)$.
This is false.  Let $f(n) = 1/n$.
There is no way that $1/n \leq c/n^2$ for $n$ large enough for any constant
$c$.

\ppart $f(n) + o(f(n)) = \Theta(f(n))$.

This is true.  We first show that $f(n) + o(f(n)) = O(f(n))$.  Let $g(n) =
o(f(n))$.  We know that there exists $c$ such that for $n$ large enough
$g(n) \leq cf(n)$.  Thus for $n$ large enough, $f(n) + g(n) \leq
(1+c)f(n)$.  

$f(n) + o(f(n))$ is $\Omega(f(n))$.  Since $f(n)$ and $g(n)$ are asymptotically
positive, $f(n) + g(n) \geq f(n)$ for $n$ large.
\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.

We use Stirling's approximation here.  Recall that
\[
n! = \sqrt{2\pi n}(n/e)^n(1 + \Theta(1/n))
\]

So we know that for $n$ large,
\begin{eqnarray*}
n! & \leq & \sqrt{2\pi n}(n/e)^n(1 + a) \\
   & \geq & \sqrt{2\pi n}(n/e)^n \\
\end{eqnarray*}
for some constant $a$.

We first note that ${n \choose {n/2}} = \frac{n!}{(n/2)!^2}$ and so if we
want to upper bound ${n \choose {n/2}}$ it suffices to upper bound the
numerator and lower bound the denominator.  Thus for $n$ large, 

\begin{eqnarray*}
{n \choose {n/2}} & \leq & \frac{\sqrt{2\pi n}(n/e)^nd}{\left(\sqrt{\frac{2\pi n}{2}}(\frac{n}{2e})^{n/2}\right)^2}
\\
				  & \leq & \frac{c\sqrt{n}(n/e)^n}{n(\frac{n}{2e})^n}
\text{for some constant } c
\\
				  & \leq & \frac{c2^n}{\sqrt{n}}
\end{eqnarray*}

Thus ${n \choose (n/2)} = O(2^n/\sqrt{n})$.  To show that ${n \choose (n/2)}
= \Omega(2^n/\sqrt{n})$ we basically do the same thing.  We lower bound the
numerator and upper bound the denominator.  The first step is thus:
\[
{n \choose {n/2}} \geq \frac{\sqrt{2\pi n}(n/e)^n}{\left(\sqrt{\frac{2\pi
n}{2}}(\frac{n}{2e})^{n/2}d\right)^2}
\]
and the other steps are similar.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

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

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

We use the master method here (see Handout $16$).  Note that $a = b =
2$ and so $\log_b a = 1$.  Note also that $f(n) = n^3$  is
$\Omega(n^{1+1})$ ($\epsilon = 1$) and $2*(n/2)^3 = \frac{1}{4}n^3 \leq
\frac{1}{2}n^3$ ($c = 1/2$).  Case $3$ thus holds.  Therefore $T(n) =
\Theta(n^3)$.

\end{problems}

\end{document}
