\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fullpage}
\usepackage[plain,linesnumbered]{algorithm2e} %algo2e for compatibility

\title{Recitation 11: Asymptotics and Summations}
\author{Created by Taylor Spangler, Adapted by Beau Christ}
\date{\today}

\begin{document}
\maketitle
\begin{itemize}
\item Problem 3.2:25: Give a good big-$O$ estimate for the following functions:
\begin{itemize}
\item $(n^2+8)(n+1)= n^3+n^2+8n+1$. We can find $n_0, c$ to prove that it is $O(n^3)$
\item $(n\log n + n^2)(n^3+1)= n^5+n^4\log n+n^2+n\log n$, again easily this is $O(n^5)$, perhaps using the limit method.
\item $(n!+2^n)(n^3+\log(n^2+1)) = n!\cdot n^3+n!\cdot \log(n^2+1)+2^n\cdot n^3+2^n\cdot \log(n^2+1)$. Well, this one is a little bit trickier.  It is actually $O(n!\cdot n^3)$, why is it not $O(n!)$ or $2^n$?
\end{itemize}

\item Problem 3.2:31:  Show that 
\[f(x) \in \Theta(g(x)) \Leftrightarrow f(x)\in O(g(x)) \land g(x)\in O(f(x))\]
\begin{enumerate}
\item $\Rightarrow$ First we begin with a definition: $f(x) \in \Theta(g(x))$ if $f(x) \in O(g(x))$ and $f(x)\in \Omega(g(x))$
\begin{itemize}
\item So we can see that $\exists c_1, c_2 \in \mathbb(R)^+$ such that $f(x) \leq c_1\cdot  g(x)$. We also know that $f(x) \geq c_2\cdot g(x)$.
\item Reversing the second inequality we get $g(x) \leq c \cdot f(x)$ where $c= \frac{1}{c_2}$.
\item So then we have $f(x)\in O(g(x))$ and $g(x)\in O(f(x))$
\end{itemize}
\item $\Leftarrow$ 
\begin{itemize}
\item Suppose $f(x)\in O(g(x))$ and $g(x) \in O(f(x))$.
\item Then we know that $\exists c_1, c_2$ such that $f(x)\leq c_1\cdot g(x)$ and $g(x) \leq c_2\cdot  f(x)$.
\item so $\frac{1}{c_1}g(x)\leq f(x)\leq c_2\cdot g(x)$.
\item But this is the definition of $\Theta$, therefore $f(x)\in \Theta(g(x))$. 
\end{itemize}
\end{enumerate}

\item What is the tightest bound we can form here:
\begin{enumerate}
\item $x^2+3x +5 \in \Delta(x^3)$: big-O
\item  $2^n\log(6) + n^2 \in \Delta(2^n)$: $\Theta$
\item $ 2^n\cdot n! + 2^n\log(n) \in \Delta(2^n)$: $\Omega$
\end{enumerate}

\item To prove the first one of the previous questions, we use the limit method
We have:
\[\lim_{x \to \infty} \frac{x^2 + 3x + 4}{x^3} = \lim_{x \to \infty} \frac{2x+3}{3x^2} =  \lim_{x \to \infty} \frac{2}{6x} = 0\]
 Therefore we can conclude that $x^3$ grows much faster, and so we get that $x^2 + 3x + 4 \in O(x^3)$
\item Next up Sequences: Can we name the first 4 terms of the following sequence $\{2^n+1\}_{n=0}^{\infty}$?
\begin{enumerate}
\item $a_0 = 2^0+1 = 2$
\item $a_1 = 2^1+1 = 3$
\item $a_2 = 2^2+1 = 5$
\item $a_3 = 2^3+1 = 9$
\end{enumerate}

\item Now compute the following sum $\displaystyle\sum_{i=1}^{5}6$
We have:
\[\displaystyle\sum_{i=1}^{5}6 =  6\displaystyle\sum_{i=1}^{5}1 = 6 \cdot (5-1+1) = 6\cdot 5 = 30\]

\item How about the following geometric $\displaystyle\sum_{i=1}^{8} 3\cdot  2^i$
\begin{itemize}
\item We can recognize that this expression is the sum of a geometric
  progression (i.e., geometric series), which is in general given as
  $\displaystyle\sum_{i=0}^{n}ar^i$, except that here we start at 1 instead of
  zero, so we can simply compute it by subtracting the first term from
  the sum.
\item The formula for computing this is $\frac{a\cdot r^{n+1}-a}{r-1}$, here $r = 2$ and $a = 3$
\item Using the formula we can get $\frac{3\cdot 2^9 - 3}{1}$ = 3$\cdot$512 - 3 = 1533
\item However, remember we have to subtract the first term, so 1533 - $3\cdot 2^0$ = 1530.
\end{itemize}
\end{itemize}

\end{document}
