\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{10, Fri.}                    % !! start the paper

\begin{problem}
Prove that asymptotic equality ($\sim$) is an equivalence relation.
\solution{
reflexivity: $\lim_{x\to \infty} f(x)/f(x) = 1$, so $f\sim f$.

symmetry: Say $f \sim g$. Then $\lim_{x\to \infty} f(x)/g(x) = 1$.  So
$\lim_{x\to \infty} g(x)/f(x) = \lim_{x\to \infty} 1/(f(x)/g(x)) =
1/\lim_{x\to \infty} f(x)/g(x) = 1/1 =1$, and therefore $g \sim f$.

transitivity: Say $f \sim g$ and $g \sim h$.  So
\begin{align*}
1 &= 1 \cdot 1\\
 &= [\lim_{x\to \infty} f(x)/g(x)] \cdot [\lim_{x\to \infty} g(x)/h(x)]\\
 &= \lim_{x\to \infty} [f(x)/g(x)] \cdot [g(x)/h(x)]\\
 &= \lim_{x\to \infty} f(x)/h(x),
\end{align*}
so $f \sim h$.}

\end{problem}

\iffalse

%F03 ps6
\begin{problem}
Show that $\log (n!) = \Theta(n\log n)$.

\solution{
First, we have
\begin{align*}
\log (n!) &= \sum_{i=1}^n \log i\\
&< \sum_{i=1}^n \log n\\
&=n\log n. 
\end{align*}

On the other hand, 
\begin{align*}
\log (n!) &= \sum_{i=1}^n \log i\\
 & > \sum_{i=\ceil{(n+1)/2}}^n \log i\\
    & > \sum_{i=\ceil{(n+1)/2}}^n \log (n/2)\\
    & > \frac{n}{2} \cdot \log (n/2)\\
    & = \frac{n ((\log n) -1)}{2}\\
    & = \frac{n \log n}{2} - \frac{n}{2}\\
    & > \frac{n \log n}{2} -\frac{n \log n}{6} & \text{for $n>8$.}\\
    & = \frac{1}{3} \cdot n \log n.
\end{align*}

Therefore, $(1/3)n \log n < \log(n!) <n\log n$ for $n>8$, proving that
$\log(n!)=\Theta(n\log n)$.}

\end{problem}
\fi

%F02 Q2

\begin{problem}
Recall that for functions $f,g$ on the natural numbers, $\naturals$, $f
= O(g)$ iff
\begin{equation}\label{Oh}
\exists c \in \naturals\, \exists n_0 \in \naturals\,
\forall n \geq n_0\quad c \cdot g(n) \geq \abs{f(n)}.
\end{equation}

For each pair of functions below, determine whether $f = O(g)$ and whether
$g = O(f)$.  In cases where one function is O() of the other, indicate the
\emph{smallest natural number}, $c$, and for that smallest $c$, the
\emph{smallest corresponding natural number $n_0$} ensuring that
condition~(\ref{Oh}) applies.

\begin{problemparts}

\problempart $f(n) = n^2, g(n) = 3n$.

$f = O(g)$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If YES, $c =$ \brule{.5in}, $n_0$ = \brule{.5in}

\solution{NO.}

$g = O(f)$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If YES, $c =$ \brule{.5in}, $n_0$ = \brule{.5in}

\solution{YES, with $c = 1$, $n_0 = 3$, which works
because $3^2 = 9$, $3 \cdot 3 = 9$.}

\problempart $f(n) = (3n - 7) / (n + 4), g(n) = 4$

$f = O(g)$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If YES, $c =$ \brule{.5in}, $n_0$ = \brule{.5in}

\solution{YES, with $c = 1, n_0 = 0$  (because $\abs{f(n)}< 3$).}

$g = O(f)$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If YES, $c =$ \brule{.5in}, $n_0$ = \brule{.5in}

\solution{YES, with $c =2, n_0 = 15.$

Since $\lim_{n \to \infty} f(n) = 3$, the smallest possible $c$ is 2.
For $c = 2$, the smallest possible $n_0 = 15$ which follows from the
requirement that $2f(n_0) \ge 4$.}

\iffalse

\problempart  (NOT USED) $f(n) = 2^{(n + 2 \sin(n))}, g(n) = 2^n$

$f = O(g)$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If yes, $c =$ \brule{.5in} $n_0$ = \brule{.5in}

$g = O(f)$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If yes, $c =$ \brule{.5in} $n_0$ = \brule{.5in}


\solution{
$f = O(g)$    YES

$c = 4, n_0 = 0$    (because $2 \sin (n)$ contributes at worst $-2$ to the power)

$g = O(f)$    YES

$c = 4, n_0 = 0$    (because the $2 \sin (n)$ contributes at worst $+2$ to the power)
}

\fi

\problempart $f(n) = 1 + (n \sin(n\pi/2))^2, g(n) = 3n$

$f = O(g)$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If yes, $c =$ \brule{.5in} $n_0$ = \brule{.5in}

\solution{NO, because $f(2n)=1$, which rules out $g =
O(f)$ since $g=\Theta(n)$.}

$g = O(f)$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If yes, $c =$ \brule{.5in} $n_0$ = \brule{.5in}

\solution{NO, because $f(2n+1) = n^2+1 \neq O(n)$ which rules out
$f = O(g)$.}

\end{problemparts}

\end{problem}

%F03 ps6
\iffalse


\begin{problem}
Suppose $f,g$ are nonnegative real-valued functions and
   $\lim_{x\to\infty}f(x) = \infty$.  Show that if $f = \Theta(g)$, then
   $\log f \sim \log g$.

\solution{
If $f=\Theta(g)$, then there exists $c_1, c_2\geq0$ and an $x_0$ such that for all $x\geq x_0, c_1f(x)\leq g(x)\leq c_2f(x)$. It follows that
\begin{align*}
\lim_{x\rightarrow\infty} \frac{\log g(x)}{\log f(x)}
&\geq \lim_{x\rightarrow\infty}\frac{\log(c_1f(x))}{\log f(x)}\\
&= \lim_{x\rightarrow\infty}\frac{\log c_1+\log f(x)}{\log f(x)}\\
&= \lim_{x\rightarrow\infty}\left(1+\frac{\log c_1}{\log f(x)}\right)\\
&=1
\end{align*}
Similarly,
\begin{align*}
\lim_{x\rightarrow\infty} \frac{\log g(x)}{\log f(x)}
&\leq \lim_{x\rightarrow\infty}\frac{\log(c_2f(x))}{\log f(x)}\\
&= \lim_{x\rightarrow\infty}\frac{\log c_2+\log f(x)}{\log f(x)}\\
&= \lim_{x\rightarrow\infty}\left(1+\frac{\log c_2}{\log f(x)}\right)\\
&=1
\end{align*}

Therefore, $\lim_{x\to\infty}\log g(x)/\log f(x) = 1$.  In other words,
$\log f\sim\log g$.  }
\end{problem}
\fi

\iffalse

%F02 cp7F 

\begin{problem}\label{o+o}
Suppose $f_1,f_2,g_1,g_2:\naturals \to \naturals$.  Prove the following:

\bparts

\ppart\label{f+o} If $f_1 = o(g_1)$, then $f_1+g_1 \sim g_1$.

\solution{
\[
\lim_{n \to \infty}\frac{f_1+g_1}{g_1} = \lim_{n \to
\infty}\frac{f_1}{g_1}+ \frac{g_1}{g_1} = 0 + 1 = 1.
\]
}
\ppart If $f_1 = o(g_1)$ and $f_2 = o(g_2)$, then $f_1 + f_2 = o(g_1 +
g_2)$.
\solution{
\begin{eqnarray*}
\lim_{n \to \infty} \frac{f_1+f_2}{g_1+g_2}
           &=& \lim_{n \to \infty} \frac{f_1+f_2}{g_1+g_2}\\
 & = & \lim_{n \to \infty} \frac{f_1}{g_1+g_2} + \frac{f_2}{g_1+g_2}\\
 & \leq & \lim_{n \to \infty} \frac{f_1}{g_1} + \frac{f_2}{g_2}\\
 & = & \lim_{n \to \infty} \frac{f_1}{g_1} + \lim_{n \to \infty}\frac{f_2}{g_2}\\
 & = & 0+0 = 0.
\end{eqnarray*}}

\ppart If $f_1 = O(g_1)$ and $f_2 = O(g_2)$, then $f_1 + f_2 = O(g_1 +
g_2)$.

\solution{
Say $f_1(n) \leq c_1 g_1(n)$ and $f_2(n) \leq c_2 g_2(n)$ for some
constants $c_1,c_2 \geq 0$ and all large $n$.  Then
\[
f_1(n) + f_2(n) \leq c_1 g_1(n) + c_2 g_2(n) \leq c (g_1(n) + g_2(n)),
\]
where $c = \max{c_1,c_2}$.
}

\ppart If $f_1 \sim g_1$ and $f_1 \geq f_2 \sim g_2 \leq g_1$, then it is
\emph{not} necessarily true that $f_1 - f_2 \sim g_1 - g_2$.

\solution{Let $f_1 \eqdef n+1, g_1 \eqdef n + 2, f_2 \eqdef g_2 \eqdef n$.}

\iffalse

\ppart If $f_1 \sim g_1$ and $f_2  \sim g_2$, then $f_1 + f_2  \sim g_1 +
g_2$.

\solution{
\iffalse
I HAVE A COUPLE OF PROOFS, neither of them as slick as I'd like.  Maybe
some students or TA's will find a nicer one---if we actually get to
this problem. -- ARM
\fi

Let $r_1 = f_1/g_1, r_2 = f_2/g_2, r=(f_1+f_2)/(g_1+g_2)$.  Then
\[
r = \frac{g_1 r_1 + g_2 r_2} {g_1+g_2}
\]
\ie $r$ is the weighted average of $r_1$ and $r_2$, where $g_1$ and
$g_2$ are the weights.  Applying the useful lemma below, we see that
$r$ must always lie between $r_1$ and $r_2$.  Since $r_1$ and $r_2$
converge to 1 as $n$ goes to $\infty$, so must $r$.  This implies $f_1
+ f_2  \sim g_1 +g_2$ as desired.
\begin{lemma*}
For any sequence $x_1, x_2... x_m$ of reals, and any sequence
$w_1, w_2... w_m$ of nonnegative reals,
\[
\min_i x_i\leq\frac{\sum_j w_jx_j}{\sum_j w_j}\leq\max_i x_i
\]
with equality holding iff all the $x_i$'s are equal.
\end{lemma*}
The central fraction is called the {\bf weighted average}, where the
$x_j$'s are the variable being averaged and the $w_i$'s are the
weights.  

Clearly if all the $w_i$'s are set equal to 1 then this simplifies to the
standard average (mean), of the variables.
\begin{proof} (of lemma)
\begin{align*}
\min_i x_i  = & \frac{\sum_j w_j}{\sum_j w_j}\min_i x_i=\frac{\sum_j
  w_j\min_i x_i}{\sum_j w_j}\leq\frac{\sum_j w_jx_j}{\sum_j w_j}\\
\max_i x_i  = & \frac{\sum_j w_j}{\sum_j w_j}\max_i x_i=\frac{\sum_j
  w_j\max_i x_i}{\sum_j w_j}\geq\frac{\sum_j w_jx_j}{\sum_j w_j}
\end{align*}
\end{proof}
}
\fi

\eparts
\end{problem}

\fi

\iffalse

% S02 q2

\begin{problem}

\newcommand{\asymptotics}{
\renewcommand{\arraystretch}{2}
\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\sim g 
\\\hline\hline
%% \sim versus \theta
6n+6 & n 
& \y & \n & \y & \n &  \n \\\hline
%% poly versus log
n^4\ln n & n^{4.01} 
& \y & \y & \n & \n &  \n \\\hline
%% Harmonic is \sim lnn (not just \theta)
2\ln(n^3)+2 & \sum_{i=1}^{n} 6/i 
& \y & \n & \y & \n &  \y \\\hline
%% Stirling and O()
n! & \bigl(\dfrac{n}{e}\bigr)^n 
& \n & \n & \y & \y &  \n \\\hline
\iffalse
%% trick
8^{\ln n}  & n^3  
& \y & \y & \y & \y &  \y \\\hline
%% sums of powers
\sum_{i=1}^{n} i^3 &  \sum_{i=1}^{n} i
& \n & \n & \y & \y &  \n \\\hline
\fi
%% integral method
\sum_{i=n}^\infty {1/{i^2}} & 1/2
& \y & \y & \n & \n &  \n \\\hline
%% trick: constant versus polynomial
\sum_{i=1}^{10} {i^2} & n^3 
& \y & \y & \n & \n &  \n \\\hline
\end{array}}

Indicate which of the following holds for each pair of functions
$f(n)$ and $g(n)$ in the table below.  Note that $\ln$ denotes the
natural logarithm.
\begin{equation*}
\newcommand{\y}{}
\newcommand{\n}{}
\asymptotics
\end{equation*}

\solution{
The first row follows easily by the definitions of the asymptotic
notations. 

The second row is really a comparison between $\ln n$ and 
$n^{0.01}$, which is a logarithmic versus polynomial comparison: every  
logarithmic is little-oh of any polynomial. 

The third row is a comparison of $6\ln n$ versus $6 H_n$; but we know
that $H_n\sim\ln n$, and hence $6\ln n\sim 6H_n$, as well. 

For the fourth row, note that 
\[
\frac{(n/e)^n}{n!} \leq 
\frac{1}{\sqrt{2\pi n} e^{1/(12n+1)}} \leq
\frac{1}{\sqrt{2\pi n}} \to 0,
\]
so $(n/e)^n = o(n!)$.

In the fifth row: for every $n\geq 2$, $f(n)$ is bounded above by
\[
\int_{n-1}^\infty \frac{1}{i^2}di = 
\frac{-1}{i} \Bigr|_{n-1}^\infty = 
0 - \frac{-1}{n-1} =
\frac{1}{n-1}.
\]
So, as $n\to\infty$, the value of $f$ tends to~0. This makes $f$
little-oh of any constant. In particular, it is $o(1/2)$.


Finally, $f$ of the last row is clearly a constant. Hence, it
is~$o(n^3)$.  

The complete table follows.
	
\newcommand{\y}{+}
\newcommand{\n}{-}
\begin{equation*}
\asymptotics
\end{equation*}
}

\end{problem}

\fi

\instatements{\newpage}
\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.  Be prepared to justify your answers.
\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.\notag
\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 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}

}
\end{problem}


% SOURCE:  FALL 00, TUTORIAL 7
% TOPIC:  Asymptotic notation
% in-class  SUBSTANTIALLY REVISED, F02 -- ARM

\begin{problem}
It is a standard fallacy to think that given $n$ quantities each of which
is $O(1)$, their sum would have to be $O(n)$.

Namely, let $f_1,f_2,\dots$ be a sequence of functions from $\naturals$ to
$\naturals$, and let
\[
S(n) \eqdef \sum_{i=1}^n f_i(n).
\]
Then given that $f_i = O(1)$ for every $f_i$ in the sequence, we can
try to argue as follows:
\[
S(n) = \sum_{i=1}^n f_i(n) = \sum_{i=1}^n O(1) = n \cdot O(1) = O(n).
\]

This informal argument may seem plausible, but is fundamentally flawed
because it treats O(1) as some kind numerical quantity.  In fact, we ask
you to show that there is no way to determine how fast the sum, $S(n)$,
may grow.

Namely, let $g$ be any function on $\naturals$.  Explain how to define a
sequence of functions $f_1,f_2,\dots$ such that each $f_i = O(1)$, but $S$
is not $O(g)$.  \hint Let $f_i(n) \eqdef 1+ ig(i)$.

\solution{
Pick $f_i$ to be the constant function $i(1+g(i))$.  That is,
\[
f_i(n) \eqdef i(1+g(i)),
\]
for all $n$.  Since $f_i$ is a constant function, it is $O(1)$.  But
\[
S(n) \sum_{i=1}^n f_i(n) \geq f_n(n) = n(1+g(n)),
\]
so $g = o(S)$ and therefore $S \neq O(g)$.
}

\end{problem} 

\instatements{\newpage}
\section*{Asymptotic Notations}

For functions $f,g: \reals \to \reals$, we say $f$ is \emph{asymptotically
equal} to $g$, in symbols,
\[
f(x) \sim g(x)
\]
iff
\[
\lim_{x \rightarrow \infty} f(x)/g(x) = 1.
\]

For functions $f,g: \reals \to \reals$, we say $f$ is \emph{asymptotically
smaller} than $g$, in symbols,
\[
f(x) = o(g(x)),
\]
iff
\[
\lim_{x \rightarrow \infty} f(x)/g(x) = 0.
\]

Given functions $f, g : \reals \mapsto \reals$, with $g$ nonnegative, we
say that\footnote{
\[
\limsup_{x \rightarrow \infty} h(x) \eqdef \lim_{x \rightarrow \infty}
\text{lub}_{y \geq x} h(y).
\]}
\[
f = O(g)
\]
iff
\[
\limsup_{x \rightarrow \infty} \abs{f(x)}/g(x) < \infty.
\]

An alternative, equivalent, definition is
\[
f = O(g)
\]
iff there exists a constant $c \geq 0$ and an $x_0$ such that for all $x \geq
x_0$, $\abs{f(x)} \leq c g(x)$.

Finally, we say
\[
f = \Theta(g) \quad\text{iff}\quad f=O(g) \land g=O(f).
\]


\end{document}
