\documentclass[12pt,twoside]{article}
\usepackage{light}

\begin{document}

\generic{The Asymptotic Cheat Sheet}{October 15, 2004}

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

{\small
\begin{tabular}{cp{1.9in}p{3.25in}}
$f = \Theta(g)$ 

		& $f$ grows at the same rate as $g$

		& 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)$

		& $f$ grows no faster than $g$

		& 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)$

		& $f$ grows at least as fast as $g$

		& There exists an $n_0$ and a
		constant $c > 0$ such that for all $n > n_0$, $c g(n)
		\leq |f(n)|$. \\ \\

$f = o(g)$

		& $f$ grows slower than $g$

		& 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)$

		&  $f$ grows faster than $g$

		& For all $c > 0$, there exists an
		$n_0$ such that for all $n > n_0$, $c g(n) \leq |f(n)|$. \\ \\

$f \sim g$

		&  $f / g$ approaches 1

		&  $\lim_{n\rightarrow\infty} f(n)/g(n) = 1$

\end{tabular}
}

\bigskip

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 almost never used in practice.
Some asymptotic relationships between functions imply other
relationships.  Some examples are listed below.

\[
\begin{array}{rclcrcl}
f = O(g) \text{ and } f = \Omega(g) & \Leftrightarrow & f = \Theta(g)
    & \qquad & f = o(g) & \Rightarrow & f = O(g) \\
f = O(g) & \Leftrightarrow & g = \Omega(f)
    & & f = \omega(g) & \Rightarrow & f = \Omega(g) \\
f = o(g) & \Leftrightarrow & g = \omega(f)
    & & f \sim g & \Rightarrow & f = \Theta(g)
\end{array}
\]

\newpage

\section*{Limits}

The definitions of the various asymptotic notations are closely
related to the definition of a limit.  As a result, $\lim_{n \to
\infty} f(n) / g(n)$ reveals a lot about the asymptotic relationship
between $f$ and $g$, provided the limit exists.  The table below
translates facts about the limit of $f / g$ into facts about the
asymptotic relationship between $f$ and $g$.
%
\[
\begin{array}{lclclcl}
\lim_{n \to \infty} f(n)/g(n) \neq 0, \infty & \implies & f = \Theta(g)
& \qquad &
\lim_{n \to \infty} f(n)/g(n) = 1 & \implies & f \sim g \\
\lim_{n \to \infty} f(n)/g(n) \neq \infty & \implies & f = O(g)
& \qquad &
\lim_{n \to \infty} f(n)/g(n) = 0  & \implies & f = o(g) \\
\lim_{n \to \infty} f(n)/g(n) \neq 0 & \implies & f = \Omega(g)
& \qquad &
\lim_{n \to \infty} f(n)/g(n) = \infty & \implies & f = \omega(g)
\end{array}
\]

Therefore, skill with limits can be helpful in working out asymptotic
relationships.  In particular, recall L'Hospital'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)}.
\]

Every computer scientist knows two rules of thumb about asymptotics:
logarithms grow more slowly than polynomials and polynomials grow more
slowly than exponentials.  We'll prove these facts using limits.

\begin{theorem*}
For all $\alpha, k > 0$:
%
\begin{align}
(\ln n)^k & = o(n^\alpha) \\
n^k & = o((1+\alpha)^n)
\end{align}
\end{theorem*}

\begin{proof}
\[
\lim_{n\to\infty} \frac{(\ln n)^k}{n^\alpha}
  = \left(\lim_{n\to\infty} \frac{\ln n}{n^{\alpha/k}}\right)^k
  \stackrel{*}{=}
    \left(\lim_{n\to\infty} \frac{1 / n}{(\alpha/k) n^{\alpha/k - 1}}\right)^k
  = \left(\lim_{n\to\infty} \frac{1}{(\alpha/k) n^{\alpha/k}}\right)^k
  = 0
\]
\[
\lim_{n\to\infty} \frac{n^k}{(1+\alpha)^{n}}
  = \left(\lim_{n\to\infty} \frac{n}{(1+\alpha)^{n/k}}\right)^k
  \stackrel{*}{=}
    \left(\lim_{n\to\infty} \frac{1}{(n/k) \cdot (1+\alpha)^{n/k-1}}\right)^k
  = 0
\]
%
The starred equalities follow from L'Hospital's Rule.
\end{proof}

\end{document}