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


\begin{problem}
Determine which of the eight choices 
\[
\varTheta(n), \quad
\varTheta(n!), \quad
\varTheta(n\log n), \quad
\varTheta(n^2), \quad
\varTheta(1), \quad
\varTheta(2^n), \quad
2^{\gamma} \text{ for } \gamma(n) = \varTheta(n), \quad
\text{none of these}
\]
best describes each function's asymptotic behavior.  


\begin{problemparts}
\problempart  
\[
g(n) \eqdef n + \ln n + (\ln n)^2.
\]

\solution{
$\varTheta(n)$.
We know that for sufficiently large $n$, $n > (\ln n)^2 > \ln n$.  
Thus, for sufficiently large $n$, 
\[
n + \ln n + (\ln n)^2 < n + n + n = 3n.
\]
Furthermore, as long as $\ln n$ is positive, 
\[
n + \ln n + (\ln n)^2 > n.
\]
Thus, for all sufficiently large $n$,  $n < g(n) < 3n$, so $g(n) = 
\varTheta(n)$.  

Even better:
\[
\lim_{n\to \infty} \frac{g(n)}{n} =
\lim_{n\to \infty} \frac{n}{n} + \lim_{n\to \infty} \frac{\ln n}{n} +
 \lim_{n\to \infty} \frac{(\ln n)^2}{n}
= 1 + 0 + 0 = 1
\]
so in fact $g(n) \sim n$.
}

\problempart 
\[
h(n) \eqdef \frac{n^2 + 2n - 3}{n^2 - 1}.
\]

\solution{$\varTheta(1)$.
Dividing the top and bottom by $n-1$ yields $h(n) = (n+3)/(n+1)$.
Now, since the top is greater than the bottom, $h(n) > 1$ for all
$n\geq 0$.  Furthermore, solving the equation $(n+3)/(n+1) < 2$
yields the solution $n > 1$.  So for all $n > 1$, $h(n) < 2$.

Thus, for all $n > 1$, we have $1 < h(n) < 2$, so $h(n) =
\varTheta(1)$. 

Even better:
\[
\lim_{n\to \infty} \frac{n^2 + 2n - 3}{n^2 - 1} = \lim_{n\to \infty}
 \frac{n^2 -1}{n^2 - 1} + \lim_{n\to \infty} \frac{2n}{n^2 - 1} +
 \lim_{n\to \infty} \frac{1-3}{n^2 - 1}
= 1 + 0 + 0 = 1
\]
so in fact $h(n) \sim 1$.
}

\problempart 
\[
j(n) \eqdef \sum_{i = 0}^n 2^{2i+1}.
\]

\solution{
$2^{\gamma}$.
Putting the summation in closed form yields $j(n) = (2/3)(4^{n+1}-1)$.

Now certainly, 
\[
\tfrac{2}{3}4^n \leq 
\tfrac{2}{3}(4^{n+1}-1) \leq
\tfrac{2}{3}4^{n+1}.
\]
Taking the base-2 logarithm of both sides, we get
\[
\lg\tfrac{2}{3} + \lg 4^n \leq 
\lg j(n) \leq
\lg\tfrac{2}{3} + \lg 4^{n+1},
\]
or
\[
(\lg 4)n + (1-\lg 3) \leq 
\lg j(n) \leq
(\lg 4)n + (3-\lg3).
\]
This clearly implies that $\lg j(n) \sim (\lg 4) n$ and $j(n) =
\varTheta(4^n)$.

Notice that because $4^n$ is \emph{not} $O(2^n)$, it is also \emph{not}
true that $j(n) =\varTheta(2^n)$.  So among the possible choices,
$2^{\gamma}$ for $\gamma=\varTheta(n)$ best describes the asymptotic
behavior of $j(n)$.
}

\problempart 
\[
k(n) \eqdef (2 + \sin (n))2^{n + \sin(n)}.
\]

\solution{
$\varTheta(2^n)$.
We know that $\sin n \geq -1$ so $k(n) \geq (2-1)2^{n-1} = (1/2)2^n$.
We also know that $\sin n \leq 1$, so $k(n) \leq (2+1)2^{n+1} = 6\cdot2^n$.
Thus, $(1/2) 2^n \leq k(n) \leq 6\cdot2^n$, so $k(n) = \varTheta(2^n)$.
}

\problempart 
\[
f(n) \eqdef \ln (n^2 !).
\]

\solution{
None of the above.
By Stirling's approximation, we know that $f(n) = \varTheta(n^2 \ln n^2) =
\varTheta (n^2 \ln n)$.  Now, this grows faster than $\varTheta(1), \varTheta(n),
\varTheta(n^2)$ and $\varTheta(n \log n)$, and slower than
$\varTheta(n!), \linebreak[2] \varTheta(2^n)$ and $2^{\gamma}$,
so ``none of these'' is the correct answer. 
}
\end{problemparts}
\end{problem}

