\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 13}
\author{Taylor Spangler}

\begin{document}
\maketitle
\begin{itemize}
\item (3 min max) Questions about last week's quiz?
\item Questions about lecture / homework so far?
\item Today, Asymptotics and Summations
\item The following is problem 3.2:25 -- Give a good big-$O$ estimate for the following:
\begin{itemize}
\item $(n^2+8)(n+1)$, well we can see that this becomes $n^3+n^2+8n+1$...this is clearly $O(n^3)$
\item $(n\log n + n^2)(n^3+1)$, becomes $n^5+n^4\log n+n^2+n\log n$, again easily this is $O(n^5)$
\item $(n!+2^n)(n^3+\log(n^2+1))$, becomes $n!*n^3+n!*\log(n^2+1)+2^n*n^3+2^n*\log(n^2+1)$. Well, this one is a little bit trickier, any guesses? It is actually $O(n!*n^3)$, can anybody tell me why it's not $O(n!)$ or $2^n$
\end{itemize}

\item Now, problem 3.2:31 -- Show that $f(x) \in \Theta(g(x))$ iff $f(x)\in O(g(x))$ and $g(x)\in \Theta(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$ such that $f(x) \leq c* g(x)$. We also know that $f(x) \geq c*g(x)$.
\item Reversing the second inequality we get $g(x) \leq c*f(x)$ (really $\frac{1}{c}$, but that is also a constant so we'll just use $c$ here for purposes of simplicity.
\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 $f(x)\leq c_1*g(x)$ and $g(x) \leq c_2* f(x)$.
\item so $\frac{1}{c_1}g(x)\leq f(x)\leq c_2*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 ???(x^3)$: big-O
\item  $2^n\log(6) + n^2 \in ???(2^n)$: $\Theta$
\item $ 2^n*n! + 2^n\log(n) \in ???(2^n)$: $\Omega$
\end{enumerate}

\item Why don't we prove the first one of the previous problem? Let's use the limit method
\begin{itemize}
\item $\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$
\item Therefore we can conclude that $x^3$ grows much faster, and so we get that $x^2 + 3x + 4 \in O(x^3)$
\end{itemize}
\item Next up Sequences: Can we name the first 4 terms of the following sequence?
\begin{enumerate}
\item $a_0 = 2^0+1 = 1$
\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$
\begin{itemize}
\item Well clearly this is just 6+6+6+6+6 = 6*5 = 30
\end{itemize}
\item How about the following geometric $\displaystyle\sum_{i=1}^{8} 3* 2^i$
\begin{itemize}
\item Well here we can recognize that this is a geometric sum $\displaystyle\sum_{i=0}^{n}ar^i$ only 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*r^{n+1}-a}{r-1}$, here $r = 2$ and $a = 3$
\item Using the formula we can get $\frac{3*2^9 - 3}{1}$ = 3*512 - 3 = 1533
\item But remember we have to subtract the first term, so 1533 - $3*2^0$ = 1530.
\end{itemize}
\end{itemize}

\end{document}