\documentclass[12pt]{article}
\usepackage{light}

\hidesolutions
%\showsolutions


\newcommand{\bigbox}{\fbox{\vspace{0.5in} \hspace{0.75in}}}


\begin{document}

\recitation{11}{March 16, 2005}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The Quest}

An explorer is trying to reach the Holy Grail, which she believes is
located in a desert shrine $d$ days walk from the nearest
oasis.
In the
desert heat, the explorer must drink continuously.  She can carry at
most 1 gallon of water, which is enough for 1 day.  However, she is
free to create water caches out in the desert.

\noindent
For example, if the shrine were $2/3$ of a day's walk into the desert,
then she could recover the Holy Grail with the following strategy.
She leaves the oasis with 1 gallon of water, travels $1/3$ day into
the desert, caches $1/3$ gallon, and then walks back to the oasis---
arriving just as her water supply runs out.  Then she picks up another
gallon of water at the oasis, walks $1/3$ day into the desert, tops
off her water supply by taking the $1/3$ gallon in her cache, walks
the remaining $1/3$ day to the shine, grabs the Holy Grail, and then
walks for $2/3$ of a day back to the oasis--- again arriving with no
water to spare.

\noindent
But what if the shrine were located farther away?
\bparts

\ppart What is the most distant point that the explorer can reach and
return from if she takes only 1 gallon from the oasis.?

\solution[\vspace{0.75in}]{At best she can walk $1/2$ day into the
desert and then walk back.}

\ppart What is the most distant point the explorer can reach and
return form if she takes only 2 gallons from the oasis?  No proof is
required; just do the best you can.

\solution[\vspace{1in}]{The explorer walks $1/4$ day into the
desert, drops $1/2$ gallon, then walks home.  Next, she walks $1/4$
day into the desert, picks up $1/4$ gallon from her cache, walks an
additional $1/2$ day out and back, then picks up another $1/4$ gallon
from her cache and walks home.  Thus, her maximum distance from the
oasis is $3/4$ of a day's walk.}

\ppart What about 3 gallons?  (Hint: First, try to establish a cache
of 2 gallons \textit{plus} enough water for the walk home as far into
the desert as possible.  Then use this cache as a springboard for your
solution to the previous part.)

\solution[\newpage]{Suppose the explorer makes three
trips $1/6$ day into the desert, dropping $2/3$ gallon off units each
time.  On the third trip, the cache has 2 gallons of water, and the
explorer still has $1/6$ gallon for the trip back home.  So, instead of
returning immediately, she uses the solution described above to
advance another $3/4$ of a day into the desert and then returns home.
Thus, she reaches 
%
\[
\frac{1}{6} + \frac{1}{4} + \frac{1}{2} = \frac{11}{12}
\]
%
of a days' walk into the desert.}

\ppart How can the explorer go as far as possible is she withdraws $n$
gallons of water?  Express your answer in terms of the Harmonic number
$H_n$, defined by:
%
\[
H_n = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots \frac{1}{n}
\]

\solution[\vspace{3in}]{With $n$ gallons of water, the explorer can
reach a point $H_n / 2$ days into the desert.

Suppose she makes $n$ trips $1/(2n)$ days into the desert, dropping off
$(n-1)/n$ gallons each time.  Before she leaves the cache for the last
time, she has $n$ gallons plus enough for the walk home.  So she
applies her $(n-1)$-day strategy to go an additional $H_{n-1} / 2$
days into the desert and then returns home.  Her maximum distance from
the oasis is then:
%
\[
\frac{1}{2n} + \frac{H_{n-1}}{2} = \frac{H_n}{2}
\]
}

\ppart Use the fact that
%
\[
H_n \sim \ln n
\]
%
to approximate your previous answer in terms of logarithms.

\solution[\vspace{1in}]{An approximate answer is $(\ln n)/ 2$.  }

\ppart Suppose that the shrine is $d = 10$ days walk into the desert.
Relying on your approximate answer, how many days must the explorer
travel to recover the Holy Grail?

\solution{
She obtains the Grail when:
%
\[
\frac{H_n}{2} \approx \frac{\ln n}{2} \geq 10
\]
%
This requires about $n \geq e^{20} = 4.8 \cdot 10^8$ days.
}

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\section{Asymptotic notation}

\textbf{(a)} 
Which of these symbols
\hfill
$
\Theta \qquad O \qquad \Omega \qquad o \qquad \omega
$
\hfill
can go in these boxes?

{\large
\begin{align*}
2 n + \log n \qquad & = \qquad \bigbox \ ( n ) \\
\insolutions{& \Theta, O, \Omega} \\
\log n \qquad & = \qquad \bigbox \ ( n ) \\
\insolutions{& O, o} \\
\sqrt{n} \qquad & = \qquad \bigbox \ ( \log^{300} n ) \\
\insolutions{& \Omega, \omega } \\
n 2^n \qquad & = \qquad \bigbox \ ( n ) \\
\insolutions{& \Omega, \omega } \\
n^7 \qquad & = \qquad \bigbox \ ( 1.01^n ) \\
\insolutions{& O, o}
\end{align*}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\insolutions{\newpage}
\instatements{\vfill}
\noindent
\textbf{(b)} 
Indicate which of the following holds for each pair of functions $f(n),
g(n)$ in the table below;  $k\geq 1$, $\epsilon > 0$, and $c > 1$
are constants.  Be prepared to justify your answers.

{\large
\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*}
}

\instatements{\vfill}

\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.\notag
\end{eqnarray}
where $a \leq c_n,d_n \leq b$ for some constants $a,b \in \mathbb{R}$ 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 because any constant,
$\log n$, and $n$ are all $o(n \log n)$ and hence so is their sum.

\iffalse

\dots follows\textbf{from Problem~\ref{o+o}, part~\ref{f+o} because any
constant, $\log n$, and $n$ are all $o(n \log n)$.}
\fi

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

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

\end{itemize}

}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\noindent
\hrulefill\textbf{cheat sheet}\hrulefill
\vspace{1ex}

\noindent
\textbf{Definitions.} Intuitively and precisely the notations mean
the following:
\textbox{
{\small
\vspace*{-1ex}
\begin{tabular}{cp{1.9in}p{2.7in}}
$f = \Theta(g)$ 

		& $f$ grows \emph{as fast} as $g$

		& There exists $n_0$ and
                  $c_1, c_2 > 0$ such that for all $n > n_0$:\:
                  $c_1 g(n) \leq |f(n)| \leq c_2 g(n)$. \\[0.75ex]

$f = O(g)$

		& $f$ grows \emph{no faster} than $g$

		& There exists $n_0$ and $c > 0$ such that 
                  \mbox{for all $n > n_0$:} \: 
                  $|f(n)| \leq c g(n)$. \\[0.75ex]

$f = \Omega(g)$

		& $f$ grows \emph{no slower} than $g$

		& There exists $n_0$ and $c > 0$ such that 
                  \mbox{for all $n > n_0$:} \: 
                  $c g(n)\leq |f(n)|$. \\[0.75ex]

$f = o(g)$
		& $f$ grows \emph{slower} than $g$

		& For all $c > 0$, there exists $n_0$ such that 
                  \mbox{for all $n > n_0$:} \: 
                  $|f(n)| \leq c g(n)$. \\[0.75ex]

$f = \omega(g)$
		&  $f$ grows \emph{faster} than $g$

		& For all $c > 0$, there exists
		  $n_0$ such that 
                  \mbox{for all $n > n_0$:} \: 
		  $c g(n) \leq |f(n)|$. \\[0.75ex] 

$f \sim g$
		&  $f / g$ approaches 1

		&  $\lim_{n\rightarrow\infty} f(n)/g(n) = 1$
\end{tabular}\vspace*{-2ex}}}

\noindent
\textbf{Relationships.} 
Some asymptotic relationships between functions imply others:
\textbox{\vspace*{-1ex}
$
\begin{array}{rclcrcl}
f = O(g) \text{ and } f = \Omega(g) & \Leftrightarrow & f = \Theta(g)
    & \qquad & f = o(g) & \Rightarrow & f = O(g) \\
f = O(g) & \Leftrightarrow & g = \Omega(f)
    & & f = \omega(g) & \Rightarrow & f = \Omega(g) \\
f = o(g) & \Leftrightarrow & g = \omega(f)
    & & f \sim g & \Rightarrow & f = \Theta(g)
\end{array}\vspace*{-1ex}
$
}

\noindent
\textbf{Limits.} 
If the $\lim_{n \to \infty} f(n) / g(n)$ exists, it reveals a lot
about the relationship of $f$ and $g$:
\textbox{\vspace*{-1ex}
$\displaystyle
\begin{array}{lclclcl}
\lim_{n \to \infty} f/g \neq 0, \infty & \implies & f = \Theta(g)
& \qquad &
\lim_{n \to \infty} f/g = 1 & \implies & f \sim g \\
\lim_{n \to \infty} f/g \neq \infty & \implies & f = O(g)
& \qquad &
\lim_{n \to \infty} f/g = 0  & \implies & f = o(g) \\
\lim_{n \to \infty} f/g \neq 0 & \implies & f = \Omega(g)
& \qquad &
\lim_{n \to \infty} f/g = \infty & \implies & f = \omega(g)
\end{array}
$\vspace*{-1ex}}

\noindent
In this context, L'Hospital's Rule is often useful: 
\[
	\text{If} \  
\lim_{n\rightarrow\infty} f(n) = \infty
	\ \text{and} \ 
\lim_{n\rightarrow\infty} g(n) = \infty,
	\ \text{then} \  
\lim_{n\rightarrow\infty} \frac{f(n)}{g(n)} =
	\lim_{n\rightarrow\infty} \frac{f'(n)}{g'(n)}.
\]

\noindent
\textbf{Logarithms vs.\ polynomials vs.\ exponentials.} 
\emph{Everybody} knows the following two facts: 
\textbox{\vspace*{-1ex}
\noindent $\bullet$\quad
polylogarithms grow \emph{slower} than polynomials:
for all $a,b > 0$,\quad $(\ln n)^a = o(n^b)$.

\noindent $\bullet$\quad
polynomials grow \emph{slower} than exponentials:
for all $b,c > 0$,\quad $n^b = o\bigl(\; (1+c)^n \;\bigr)$.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
