\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphics}
\input{macros-course}

\begin{document}

\handout{asymp}{The Asymptotic Cheat Sheet}{October 15, 1998}

\section{Notation}

Asymptotic notation consists of six funny symbols used to describe the
relative growth rates of functions.  These six symbols are defined in
the table below.

\bigskip
\begin{tabular}{cll}

$f = \Theta(g)$

		& \parbox[t]{1.5in}{$f$ grows at the same rate as
		$g$}

		& \parbox[t]{3.0in}{There exists an $n_0$ and
		constants $c_1, c_2 > 0$ such that for all $n > n_0$,
		$c_1 g(n) \leq f(n) \leq c_2 g(n)$.} \\ \\

$f = O(g)$

		& \parbox[t]{1.5in}{$f$ grows no faster than $g$}

		& \parbox[t]{3.0in}{There exists an $n_0$ and a
		constant $c > 0$ such that for all $n > n_0$, $f(n)
		\leq c g(n)$.} \\ \\

$f = \Omega(g)$

		& \parbox[t]{1.5in}{$f$ grows at least as fast as
		$g$}

		& \parbox[t]{3.0in}{There exists an $n_0$ and a
		constant $c > 0$ such that for all $n > n_0$, $c g(n)
		\leq f(n)$.} \\ \\

$f \sim g$

		&  \parbox[t]{1.5in}{$f / g$ approaches 1}

		&  \parbox[t]{3.0in}{$\lim_{n\rightarrow\infty}
		   f(n)/g(n) = 1$} \\ \\

$f = o(g)$

		& \parbox[t]{1.5in}{$f$ grows slower than $g$}

		& \parbox[t]{3.0in}{For all $c > 0$, there exists an
		$n_0$ such that for all $n > n_0$, $f(n) \leq c
		g(n)$.} \\ \\

$f = \omega(g)$

		&  \parbox[t]{1.5in}{$f$ grows faster than $g$}

		& \parbox[t]{3.0in}{For all $c > 0$, there exists an
		$n_0$ such that for all $n > n_0$, $c g(n) \leq f(n)$.}

\end{tabular}
\bigskip

Some sources define these notations a little differently, but these
differences rarely matter.  The $\sim$ and $\Theta$ notations are
confusingly similar; qualitatively, functions related by $\sim$ must
be even more nearly alike then functions related by $\Theta$.  The
$\omega$ notation makes the table nice and symmetric, but is never
used in practice.  Some asymptotic relationships between functions
imply other relationships.  These implications follow from the
definitions in the table above.  Some are listed below.

\begin{eqnarray*}
f = O(g) \text{ and } f = \Omega(g) & \Leftrightarrow & f = \Theta(g) \\
f = O(g) & \Leftrightarrow & g = \Omega(f) \\
f = o(g) & \Leftrightarrow & g = \omega(f) \\
f = o(g) & \Rightarrow & f = O(g) \\
f = \omega(g) & \Rightarrow & f = \Omega(g) \\
f \sim g & \Rightarrow & f = \Theta(g)
\end{eqnarray*}

\newpage

\section{The Limit Method}

The easiest way to prove that an asymptotic relationship holds between
two functions is to look at the limit of the ratio.  The table below
translates facts about the limit of $f / g$ into facts about the
asymptotic relationship between $f$ and $g$.  These rules follow from
the definitions of the various asympototic notations and from the
definition of a limit.  All limits below are taken as $n \rightarrow
\infty$.

\[
\begin{array}{ll}
\lim f(n)/g(n) \neq 0, \infty
	\ \Rightarrow \  f = \Theta(g) &
\lim f(n) /g(n) = 1  \ \Leftrightarrow \  f \sim
	g \\

\lim f(n)/g(n) \neq \infty
	\ \Rightarrow  \ f = O(g) &
\lim f(n) /g(n) = 0  \ \Rightarrow \  f =
	o(g) \\

\lim f(n)/g(n) \neq 0
	\ \Rightarrow \ f = \Omega(g) &
\lim f(n) /g(n) = \infty  \ \Rightarrow \ f
	= \omega(g)
\end{array}
\]

In theory, the limit of $f / g$ might reveal nothing about the
asympototic relationship between $f$ and $g$, because the limit might
not exist.  But in practice, the only difficulty with the limit
approach to determining asymptotic relationships is that you have to
evaluate some tricky limits.  Two theorems make this job managable in
most cases.

\bigskip
{\bf Theorem 1.}
\begin{eqnarray*}
\lim_{n\rightarrow\infty} f(n) + g(n) & = &
	\lim_{n\rightarrow\infty} f(n) +
	\lim_{n\rightarrow\infty} g(n) \\
\lim_{n\rightarrow\infty} f(n) \cdot g(n) & = &
	\lim_{n\rightarrow\infty} f(n) \cdot
	\lim_{n\rightarrow\infty} g(n)
\end{eqnarray*}

\bigskip
{\bf Theorem 2. \quad (L'Hopital's Rule)}

\[
	\text{If} \  
\lim_{n\rightarrow\infty} f(n) = \infty
	\ \text{and} \ 
\lim_{n\rightarrow\infty} g(n) = \infty,
	\ \text{then} \  
\lim_{n\rightarrow\infty} \frac{f(n)}{g(n)} =
	\lim_{n\rightarrow\infty} \frac{f'(n)}{g'(n)}.
\]

If $f$ grows, say, three times faster than $g$, then eventually $f$
should be around three times larger than $g$.  This is the intuition
for why $f'(n)/g'(n) = 3$ should imply that $f(n)/g(n) = 3$ in the
limit.

\bigskip
{\bf Example.} Prove that $\log^2 n = o(\sqrt{n})$.

\begin{eqnarray*}
\lim_{n\rightarrow\infty} \frac{\log^2 n}{\sqrt{n}}
  & = & \left(\lim_{n\rightarrow\infty} \frac{\log n}{n^{1/4}}\right)^2 \\
  & = & \left(\lim_{n\rightarrow\infty} \frac{\frac{1}{n}}
	{\frac{1}{4}n^{-3/4}}\right)^2 \\
  & = & \left(\lim_{n\rightarrow\infty} \frac{4}{n^{1/4}}\right)^2 \\
  & = & 0
\end{eqnarray*}

The first step uses the second part of Theorem 1, the second step uses
Theorem 2, the third step is simplification, and the final step is
evaluation of an easy limit.
\end{document}