\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\usepackage{psfig}
\input{macros-course}

\begin{document}

\handout{Onotes}{Notes on Asymptotic Notations}{November 1, 1999}

\section{$O()$ and $\Theta$}
Intuitively, ``$f = O(g)$'' means that, to within a constant factor, $g$
grows ``at least as fast'' as $\abs{f}$.  More precisely, for functions
$f,g:\reals \to \reals$, we say that $f = O(g)$ iff $\abs{f}$ is bounded
above by some positive constant multiple of $g$ for any sufficiently large
argument of the functions.

Saying that a property holds for a ``sufficiently large'' number, means
that there is a real number $x_0$ such that the property holds for all
real numbers $\geq x_0$.  Here's the definition expressed as a logical
expression:

\begin{defin}
For functions $f,g:\reals \to \reals$,  define $f=O(g)$  to mean
\[
\exists c>0\: \exists x_0\: \forall x \geq x_0(|f(x)| \leq c\cdot g(x)).
\]
\end{defin}

When we think of $f = O(g)$ as meaning roughly that $f \leq g$, the
property of transitivity is captured by

\begin{lemma}
If $f = O(g)$ and $g = O(h)$, then $f = O(h)$.

\begin{proof}
$\abs{f(x)} \leq c\cdot g(x)$ for $x > x_0$ and $\abs{g(x)} \leq d\cdot
h(x)$ for $x > x_1$ implies  $\abs{f(x)} \leq (cd)\cdot
h(x)$ for all  $x > \max(x_0,x_1)$.
\end{proof}
\end{lemma} 

Another growth rate notation, $\Theta()$, is defined in terms of $O()$.
Intuitively, $f= \Theta(g)$ corresponds to $f \approx g$, that is, $f$ is
``approximately'' equal to $g$.  The precise definition is simple:
\begin{defin}
\[
f=\Theta(g) \mbox{   iff   } [f=O(g) \mbox{ and } g = O(f)].
\]
\end{defin}

The value of these notations is that they highlight growth rates and allow
suppression of distracting factors and low-order terms.  For example, if
the running time of an algorithm is
\[T(n) = 10n^3 - 20n^2 + 1,\]
then
\[T(n) = \Theta(n^3).\]
In words, we would say that ``$T(n)$ grows \emph{cubically},'' meaning it
is bounded both above and below by constant multiples $n^3$.

Another such example is
\[
\pi^23^{x-7} + \frac{(2.7x^{113} + x^9- 86)^4}{\sqrt{x}} - 1.08^{3x} =
\Theta(3^x).\]

\section{$O()$ but not Conversely}
Let's use the notation $f \prec O(g)$ to mean $f=O(g) \wedge
\neg[g=O(f)]$. \textbf{Warning}: this is nonstandard notation used only in
6.042.

\begin{lemma}\label{xlnx}
\[
\frac{x}{\ln x} \prec O(x).
\]
\end{lemma}

\begin{proof}
$(x / \ln x) < x$ as long as $x > 0$ and $\ln x > 1$, that is, when $x
> e$.  So $(x / \ln x) = O(x)$ by definition of $O()$ (with $x_0 = e$
and $c =1$).

To show $\prec O()$, we must show that for all $c > 0$
and all $x_0$, there is an $x_1 \geq x_0$, such that $\abs{x_1} > c
x_1/\ln x_1$.  But $\abs{x} > (c/\ln x) x = c (x/\ln x)$ if $c/ {\ln x} <
1$, that is, if $e^c < \ln x$.  So let $x_1 = \max(e^c + \epsilon, x_0)$.
\end{proof}

Notice that the only fact we really used about $\ln x$ in the above proof
is that it is an unbounded increasing function.

\medskip

When we think of $f = O(g)$ as ordering $f$ below $g$, we have to think
about \emph{partial} orderings.  For example, neither of $\abs{x \sin x}$
nor $\abs{x \cos x}$ is $O()$ of the other -- because there are infinitely
many $x$'s where one is zero and the other is not, and no constant
multiple of zero can ``catch up'' with the positive value of the other.
This $O()$-incomparibility is not just confined to functions with an
infinite number of roots: consider $\abs{x \sin x} + \ln x$ and
$\abs{x \cos x} + \ln x$.

\section{Growth rates of common functions}

\subsection{Examples}

\begin{lemma}\label{mainO}
The main facts to remember are:

\begin{enumerate}

\item $p(x) = \Theta(x^dn)$ for any polynomial $p$ of degree $d$ with
positive leading coefficient,

\item $x^a \prec O(x^b)$ for $0 \leq a < b$.

\item $x^k \prec O(a^x)$ for any $k>0, a>1$,

\item $a^x \prec O(b^x)$ for $1 \leq a < b$,

\item $\ln(x)^k \prec O(x^\epsilon)$ for any $k,\epsilon >0$.

\end{enumerate}

\end{lemma}
These facts are most easily proved using elementary calculus.  For the
record, we include some of the proofs in an Appendix.  These proofs will
not be required material.

Some additional useful rules (with elementary proofs directly from the
definitions) are

\begin{enumerate}

\item $f \pm g = O(\max(\abs{f}, \abs{g}))$,

\item $f \cdot  g = O(\abs{f} \cdot \abs{g})$.

\item If $f(x) = O(g(x))$ and $\lim_{x \rightarrow \infty} h(x) = \infty$, then
     $f(h(x)) = O(g(h(x))$.

\end{enumerate}

Other operations may not behave so nicely, e.g., $2x = O(x)$ but $2^{2x}
\neq O(2^x)$.


\subsection{A note on O notation}

Sometimes you may see an expressions like:
\[(1 + 1/x)^n = 1 + n/x + O(1/x^2).\]
The above expression really means that 
\[(1 + 1/x)^n - 1 - n/x = O(1/x^2).\]
That is, the error term in the approximation for $(1+1/x)^n$ is at most a
constant divided by $x^2$.


\section{Asymptotic equality}

A tighter relationship between growth rates is
\emph{asymptotic equality}, $\sim$:
\begin{defin}
\[f \sim g \mbox{  iff  } \lim_{x\rightarrow \infty} \frac{f(x)}{ g(x)} = 1.\]
\end{defin}
This was the relation described in lecture for the Harmonic number
\[H_n \sim \ln n.\]

For example, $x + 1/x \sim x - \sqrt{x}$.  Note that if the values of $f$
and $g $ are nonnegative, then $f \sim g$ implies $f = \Theta(g)$.  The
converse implication obviously does not hold.

\section{Limits of Quotients}
The reason why the $\prec O()$ notation is not found outside 6.042 is that
another, more common and informative relation that implies $\prec O()$ is
widely used.  This is the ``Little Oh'' relation, $=o()$.  We don't need,
and will not study, this relation in 6.042.  For the record, here is the
definition:

\begin{defin}
$f = o(g) \mbox{ iff } \forall c > 0\: \exists x_0\: \forall x \geq x_0 :
\abs{f(x)} \leq c g(x)$.
\end{defin}
This definition is a little hard to follow because of all the quantifiers.
For functions, $f, g$, which are nonnegative --- which is generally all we
care about in this context --- a clearer way to say $f=o(g)$ is:
\[
\lim_{x\rightarrow \infty} \frac{f(x) }{ g(x)} = 0.
\]

For comparison purposes, it helps to express $O()$ and $\sim$ as similar
statements about limits.  First, $f \sim g$ iff
\[
\lim_{x\rightarrow \infty} \frac{f(x) }{ g(x)} = 1.
\]
It's almost correct to say that $f
= O(g)$ iff there a constant $c \geq 0$ such that
\[
 \lim_{x\rightarrow \infty} \frac{f(x) }{ g(x)} \leq c,
\]
but this is not quite right because the limit may not exist.  For example,
$f$ might vary between 2 and 3 times $g$.  The proper statement for $g
\geq 0$ is that $f = O(g)$ iff and there a constant $c \geq 0$ such that
\[
 \limsup_{x\rightarrow \infty} \frac{\abs{f(x)}}{g(x)} \leq c.
\]

These formulations make it clear that $f= o(g)$ implies $f \prec O(g)$.
The converse implication may fail in general, but we note that each of the
statements of the form ``$f \prec O(g)$'' in Lemma~\ref{mainO}, could have
been replaced by ``$f= o(g)$''.  For example, $x^a = o(x^b)$ where $0 \leq
a < b$.

\section{Appendix: proofs about $O()$}

\begin{theorem}\label{lno}
\[\forall \epsilon > 0: \ln x = O(x^\epsilon).\]
\end{theorem}

\begin{proof}
Remember L'H$\hat{\mbox{o}}$pital's rule:  if $\lim_{x\rightarrow \infty}
f(x) = \infty = \lim_{x\rightarrow \infty} g(x)$, then
\[\lim_{x\rightarrow \infty} {f(x) / g(x)} = \lim_{x\rightarrow \infty}
{f'(x)/ g'(x)}\]
where $f',g'$ are the derivatives of $f,g$, and $f, g, f', g'$ are
continuous.
So
\[
\lim_{x\rightarrow \infty} \frac{\ln x}{ x^\epsilon} =  
\lim_{x\rightarrow \infty} \frac{{1/x}}{ {\epsilon x^{\epsilon-1}}} = \lim_{x\rightarrow
\infty} \frac{1}{\epsilon x^\epsilon} = 0.
\]

The last equality follow from the familiar fact -- which we'll take for
granted -- that that for all $\epsilon>0$, the value of $x^\epsilon$ grows
unboundedly as $x$ approaches infinity.  Since the limit is 0, we can be
sure that once $x$ is large enough, $\ln x/x^\epsilon \leq 1$, that is
$\ln x \leq x^\epsilon$.  So indeed $\ln x = O(x^\epsilon)$.
\end{proof}

Similarly,
\begin{theorem}\label{expo}
\[
\forall a >1: x = O(a^x).
\]
\end{theorem}
\begin{proof}
We know that $\ln a > 0$, so in the Taylor series
\[a^x = a^0 + x (\ln a)a^0 + x^2 (\ln a)^2a^0/2 + \dots\]
all the coefficients are positive.  Hence
\[a^x > 1 + (\ln a)x > (\ln a)x \mbox{ for }x>0.\]
\end{proof}

\begin{corollary}\label{expk}
\[
\forall k\in \naturals, a >1: y^k = O(a^y).
\]
\end{corollary}
\begin{proof}
By induction on $k$.  In the base case $k=0$, we have $y^k = y^0 = 1 < a
\leq a^y$ for $y\geq 1$, so $y^0 = O(a^y)$.  Notice that the only facts we
have used here about $a^y$ are that $a^1 = a$ and $a^y$ is a nondecreasing
function of $y$.

We now assume the induction hypothesis $y^k = O(b^y)$ for all $b>1$ and
prove $y^{k+1} = O(a^y)$ for all $a>1$.  For any $a > 1$, let
$b=\sqrt{a}$, so also $b > 1$.  By hypothesis, $y^k
\leq cb^y$ for some $c>0$ and all $y \geq$ some $y_0$.  Also, by
Theorem~\ref{expo}, $y \leq c'b^y$ for some $c'>0$ and all $y \geq$ some
$y'_0$.  So 
\[
\begin{array}{lclclcl}
y^{k+1}& = & y(y^k) & \leq & c'b^y(cb^y) & = & cc'(b^y)^2\\
& = & cc'b^{2y} & = & cc'(b^2)^y & = & cc'a^y
\end{array}
\]
for $y\geq \max(y_0, y'_0)$, which shows that $y^{k+1} = O(a^y)$.
\end{proof}


\end{document}


