 
\documentstyle[12pt,overhead]{article}
\begin{document}
\input{epsf}
%\input rotate
\epsfverbosetrue
\large
\slabel{}
%\baselineskip=24pt

\begin{slide}{}{}
\section{\bf \LARGE GROWTH RATES AND ASYMPTOTIC NOTATIONS}
{\bf \LARGE Goal:}\\
\begin{itemize}
\item Categorize algorithms based on their asymptotic growth rate.

\item Ignore (small) constant of proportionality $\&$ small inputs 


\item Estimate upper bound on growth rate of time complexity function

\end{itemize}

{\bf \LARGE \bf def1:}
(For arbitrary functions) $f(n)\in O(g(n))$
if there exist two positive constants 
{\bf $c$} and {\bf $n_{0}$} such that 
   \[|f(n)|\leq c|g(n)|\]
for all {\bf $n\geq n_{0}.$}\\


 
eg.
%\baselineskip=24pt
\begin{enumerate}
   \item {\bf $f(n)=5n$  $g(n)=n^{2}$}

         $5n_{0} \leq cn_{0}^{2}$\\   
         $\Rightarrow 5 \leq  cn_{0}$\\
   	 $\Rightarrow n_{0}=5,c=1$\\
     Thus, $5n=O(n^{2})$     
   \item {\bf $f(n)=10^{6}n^{2}$   $g(n)=n^{2}$}

         To prove: $(10^{6}n^{2})\leq cn^{2}$ for $n\geq n_{0}$\\
         choose $C=10^{6}$\\
         Then $n_{0}=1$\\
   	 $\Rightarrow (10^{6}n^{2})=O(n^{2}) $\\

   \item {\bf $A(n)=a_{m}n^{m}+ a_{m-1}n^{m-1}+\ldots +a_{1}n+a_{0}$}

     a polynominal of degree $m$, $n,m\geq 0$  for all $i$, $a_{i}\in R$\\[0.5cm]
     {\bf To Prove: $A(n)=O(n^{m})=a_{m}n^{m}+O(n^{m-1})$}

Example: $5n^3 + 2n^2 - 5\  =\ O(n^3) \ = \ 5n^3 + O(n^2)$\\
{\bf \LARGE Proof:}\\
To Prove: $|A(n)| \ \leq \ c|n^m|$\\[0.5cm]
 $|A(n)|\leq |a_{m}|n^{m}+|a_{m-1}|n^{m-1}+\ldots +|a_{1}|n+|a_{0}|$\\[0.5cm]
      $\leq n^{m}(|a_{m}|+\frac{|a_{m-1}|}{n}+\ldots+\frac{|a_{1}|}{n^{m-1}}
      +\frac{|a_{0}|}{n^{m}})$\\[0.5cm]
      $\leq n^{m}(|a_{m}|+|a_{m-1}|+\ldots +|a_{0}|)$\\[1cm]
      $c=|a_{m}|+|a_{m-1}|+\cdots+|a_{0}|$\\[0.5cm]
      $n_{0}=1$\\[0.5cm]
Example: $5n^3 + 2n^2 - 5\  =\ O(n^3) $\\
	c = $5 + 2 + |-5|$ = 12\\
	
$5n^3 + 2n^2 - 5\  \leq \ 12n^3 $\\
for all {\bf $n\geq 1$}.
      
\end{enumerate}
\end{slide}


\begin{slide}{}{}
\subsection{\bf ORDER NOTATION FOR POSITVE FUNCTIONS}
\paragraph{\bf \LARGE \bf def2:}
     Let $$f:N\rightarrow R^{*}$$\\ 
     $$g:N\rightarrow R^{*}$$  
     $$g(n)= O(f(n))$$, ie., $$g(n) \in O(f(n))$$,\\
     if for some $c\in R^{+}$ and some $n_{0} \in N$\\
     $$g(n)\leq cf(n)$$
 for all $n\geq n_{0},$ where\\
 $R^{*}=R^{+}\cup \{0\}$, \\$R^{+}= $set of positive reals\\
     $N=\{0,1,2,3,\ldots\}$.\\


\paragraph{\bf \LARGE \bf def3:}
 $f\in O(g)$ if $\lim_{n \rightarrow \infty}
\frac{f(n)}{g(n)}\rightarrow c$ for some $c \in R^{*}.$\\[0.5cm]
     Examples:
	\begin{enumerate}
	\item $10^{6}n^{2}=O(n^{2})$\\
     $\lim_{n \rightarrow \infty}  \frac{10^{6}n^{2}}{n^{2}}\rightarrow 10^{6}$\\
   \item  $5n \in O(n^2)$\\
	$\lim_{n \rightarrow \infty} \frac{5n}{n^{2}} \rightarrow 0$\\[1cm]
   \item Prove that $2^{n}\neq O(n^{m})$ for any integer $m$.\\[0.5cm]
   {\em (By Contradiction:)}   Suppose $2^{n}=O(n^{m})$\\[0.5cm]
   $\lim_{n \rightarrow \infty} \frac{2^{n}}{n^{m}}= \lim_{n \rightarrow \infty}
   \frac{2^{n}\log 2}{mn^{m-1}}$\\[0.5cm]
    $=\lim_{n \rightarrow \infty} \frac{{(\log 2)}^2\  2^{n}}{m(m-1)n^{m-2}}$\\[0.5cm]
    $=\lim_{n \rightarrow \infty} \frac{(\log 2)^{m}2^{n}}{m(m-1)\cdots(2)1}$
    $\rightarrow \infty $\\[0.5cm]
    Thus, polynomial algorithms are distinctly superior     to
    exponential-time algorithms.\\
\end{enumerate}
    
(Project should have polynomial algo's only) 
    
\end{slide}

\begin{slide}{}{}
\subsection{\bf $\Theta$ AND OTHER NOTATIONS}
    {\bf \LARGE \bf def:}
 If $f(n) = O(g(n))$ \\ then $g(n) = \Omega(f(n)).$  \\[0.5cm]

Thus, $O(f)$ contains all function with growth rate "equal or slower."\\[0.5cm]
$\Omega(f)$ contains all function with growth rate "equal or faster."\\[0.5cm]

    {\bf \LARGE \bf def:}
If $f(n)=O(g(n))$ and $g(n)=O(f(n))$  
\\ then $f(n)=\Theta(g(n))$.\\[0.5cm]
Equivalently,  $\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)}=c \in R^+$.\\[0.5cm] 

Thus, $$\Theta(f)$ = $O(f) \cap \Omega(f)$$

\newpage
In terms of growth rate,\\
      $\Theta (f)$ contains functions growing at the same rate as $f$.\\[0.5cm]
        $ O(f)$ contains function growing no faster than $f$\\[0.5cm]
        $ \Omega(f)$ contains function at least as fast as $f$\\[0.5cm]

    {\bf \LARGE \bf def:}
    (Small o and $\omega$ notations): \\[0.5cm]
      $f = o(g)$ if $\lim_{n \rightarrow \infty} f/g \rightarrow 0$\\[0.5cm]
      $f=\omega(g)$ if and only if $g \in o(f)$\\[0.5cm]
\end{slide}


\begin{slide}{}{}
\subsection{$\sqrt(n)$ VERSUS $\log_{2}^{3}n$}
    show $\sqrt{n} = \Omega (\log_{2}^{3} n)$\\[0.5cm]
     $\Rightarrow \ln^3 n = O(\sqrt{n} ) $\\[0.5cm]
$\frac{\ln^{3} n}{\sqrt{n}}=\lim_{n \rightarrow \infty}
     \frac{3\log^{2} n 1/n}{1/2 n^{-1/2}}$\\[0.5cm]
     $=\lim_{n \rightarrow \infty} 6 \frac{\log^{2} n}{\sqrt{n}}=\lim_{n \rightarrow \infty}  6\frac{2\log n 1/n}{1/2n^{-1/2}}$\\[0.5cm]
     $=\lim_{n \rightarrow \infty} 24\frac{\log n}{\sqrt{n}}=\lim_{n \rightarrow \infty} 24\frac{1/n}{1/2 n^{-1/2}}$\\[0.5cm]
     $=\lim_{n \rightarrow \infty} \frac {48}{\sqrt{n} } \rightarrow 0$\\[0.5cm]
     $\Rightarrow  \log^{3} n=O(\sqrt{n})$\\[0.5cm]
\end{slide}

\section{H.W.1}
\begin{itemize}
\item  Use defn. 2 to show that
    $\sqrt{n} = \Omega (\log_{2}^{3} n)$\\[0.5cm]
\item Q. 1-1, p. 13
\item Q. 3-2, p. 58
\end{itemize}  
\end{document}

\begin{slide}{Needs Corrections}{}
     Alternately, find $n_{0} \& c$\\[0.5cm]
     $  n\geq c\log_{2}^{3} n$\\[0.5cm]
     $  2 \geq c \log^{3} 2=c 1$
     $c=1,n_{0}=2$ true?
     $n=9$\\[0.5cm]
     $\sqrt{4} =2 \geq \log_{2}^{3} 4 = 2^{3}=8$\\[0.5cm]
     $\sqrt{16}=4 \geq  \log_{2}^{3} 16  =4^{3}$\\[0.5cm]
     $\sqrt{1024} =2^{5} \geq \log_{2}^{3} 2^{10} =10^{3}=100$\\[0.5cm]
     $\sqrt{2^{14}}=2^{7} \geq \log_{2}^{3} 2^{7} =7^{3}$\\[0.5cm]
     $\sqrt{2^{20}}=2^{10}=1024 \geq \log log_{2}^{3} 2^{20} =(20)^{3}$\\[0.5cm]
     $\sqrt{2^{2^{x}}}= \geq 2^{2^{x-1}} \geq \log_{2}^{3}
     (2^{2^{x}})=(2^{x})^{3}=2^{3x})$\\[0.5cm]
     $2^{2^{x-1}}\geq 2^{3x}$\\[0.5cm]
     $\Rightarrow 2^{x-1} \geq 3x$\\[0.5cm]    
     $x=5$\\[0.5cm] 
     $2^{5-1}=16\geq 3\cdot 5=15$\\[0.5cm]
     $\Rightarrow \eta _{0}=2^{2^{5}}$\\[0.5cm]
     $\eta _{0}=2^{32}$\\[0.5cm]
     $\sqrt{2^{32}}\geq \log_{2}^{3} 2^{32}$\\[0.5cm]
     $2^{16} \geq (32)^{3}= (2^{5})^{3}=2^{15}$\\[0.5cm]
     $ \Rightarrow n_{0}=2^{32}$\\[0.5cm]
     For practical algorithms, do evaluate $n_{0}$  to see if they are  
     reasonable.\\[0.5cm]
\end{slide}   
\end{document}
