\documentstyle[11pt]{article}
\def\doublespaced{\baselineskip=\normalbaselineskip	%reset to normal
    \multiply\baselineskip by 140			%doublespacing is
    \divide\baselineskip by 100}			%really 1.5 of normal
\def\doublespace{\doublespaced}				%synonym
\setlength{\topmargin}{0.1in}
\setlength{\textwidth}{6.0in}
\setlength{\textheight}{8.0in}
\setlength{\oddsidemargin}{0.25in}
\setlength{\evensidemargin}{0in}
\begin{document}
\begin{center}
{\Large\bf Introduction to Asymptotic Notation\\[\smallskipamount]}
{\large\sf Dr. Russ Miller}\\
\today
\end{center}
\vspace{0.50in}
\doublespaced
We use $\Theta$ to mean `order exactly', O to mean `order at most',
and $\Omega$ to mean `order at least'.

\noindent
{\bf Definition of $\Theta$:}
Given nonnegative functions $f$ and $g$ defined on the
positive integers, we write $f = \Theta (g)$ if and only if there are
positive constants $C_{1}$, $C_{2}$, and a positive integer $N$
such that
\begin{center}
$C_{1} \ast g(n) \leq f(n) \leq C_{2} \ast g(n)$, 
whenever $n>N$.
\end{center}
{\bf Definition of O:}
Given nonnegative functions $f$ and $g$ defined on the positive integers,
we write $f=$O$(g)$ if and only if there is a positive constant $C$ and an
integer $N$ such that
\begin{center}
$f(n) \leq C \ast g(n)$, for all $n>N$.
\end{center}
{\bf Definition of $\Omega$:}
Given nonnegative functions $f$ and $g$ defined on the positive integers,
we write $f = \Omega (g)$ if and only if there is a positive constant $C$
and an integer $N$ such that
\begin{center}
$C \ast g(n) \leq f(n)$, for all $n>N$.
\end{center}

When using order notation, one wants to use the simplest function
possible within the $\Theta $, O, or $\Omega $.
The idea is to use the notation to reduce complicated functions to
simpler ones whose behavior is easier to understand.

{\bf Proposition 1}:
Suppose $f$ and $g$ are positive functions defined
on the positive integers, and that
\( \lim_ {n \rightarrow \infty} \frac {f(n)}{g(n)}= a\),
for some nonzero $a$.
Then $f= \Theta (g)$.
\nopagebreak

{\em Proof:} \(lim_ {n \rightarrow \infty} \frac {f(n)}{g(n)} = a \)
means that for any $c>0$ there
is an integer $N$ such that  $\left | \frac {f(n)}{g(n)} - a \right | \leq c$,
for all $n \geq N$.
If we chose $c = \frac {a}{2}$ then there is an $N$ such that
$\frac{a}{2} \leq \frac {f(n)}{g(n)} \leq \frac {3a}{2}$ for all $n \geq N$.
So, $\left ( \frac {a}{2} \right ) \ast g(n) \leq f(n)
\leq \left ( \frac {3 a}{2} \right ) \ast g(n)$,
for all $n \geq  N$. $\Box$
\newpage

Proposition 1 is useful because there are many techniques,
such as L'Hopital's rule, for evaluating limits.
However, there are some instances where Proposition 1 cannot be
used.

For example, $2 + sin(n) = \Theta (1)$, even though
\( \lim_{n \rightarrow \infty} \frac {[2 + sin(n)]}{1} \) is undefined.

{\bf Examples of $\Theta $:}
If $f(n) = 3n + 6$ and $g(n) = n$, then
$f(n) = \Theta (g(n))$, or $f = \Theta (g)$, or $3n + 6 = \Theta (n)$,
as can be seen by using $C_{1} = 3, C_{2} = 4$, and $N=5$.

Notice that if $f=\Theta (g)$ then $g=\Theta (f)$, since if there
are positive constants $C_{1}, C_{2}$, and $N$ such that
$C_{1} \ast g(n) \leq f(n) \leq C_{2} \ast g(n)$ for all $n>N$, then
$\left ( \frac {1}{C_{2}} \right ) \ast f(n) \leq g(n) \leq
\left ( \frac{1}{C_{1}} \right ) \ast f(n)$, 
for all $n>N$.

$3n + 2 = \Theta (n)$.
$10 n^{2} + 4n + 2 = \Theta (n^{2})$.
$10 n^{2} + 4n + 2 \neq \Theta (n)$.
$10 \ast \log n + 4 = \Theta (\log n). \Box$ 

\vspace{.30in}
\noindent{\bf Useful Properties of $\Theta $:}

1. If $f(n) = \Theta (h(n))$ and $g(n) = \Theta (h(n))$, then
$(f+g)(n) = \Theta (h(n))$.

2. If $f(n) = \Theta (g(n))$ and $g(n) = \Theta (h(n))$, then
$f(n) = \Theta (h(n))$.

3. $a_{k} n^{k} + a_{k -1} n^{k - 1} + \cdots + a_{1} n + a_{0}
= \Theta (n^{k}), a_{k}> 0$.

4. $\log_{a} (n) = \Theta (\log_{b} (n))$ for any $a,b>1$.

5. $\sum_{i=1}^{n} i = \Theta (n^{2})$

6. $\sum_{i=1}^{n} \log_{a} (i) = \Theta (n\log n), a>1$.

7. $\sum_{i=1}^{n} \frac {1}{i}= \Theta (\log(n))$.

8. $\sum_{i=1}^{n} \frac {1}{i^{2}} = \Theta (1)$.

9. If $f(n) = \Theta (h(n)), g(n) = \Theta (h(n))$,
and $f(n) \leq e(n) \leq g(n)$,
then $e(n) = \Theta (h(n))$.

\newpage
\noindent{\bf O and $\Omega$ Notation}

It is not always possible to determine the behavior of an algorithm
using $\Theta$-notation.
For example, given a problem with $n$ inputs, we may have
an algorithm to solve the problem which takes $Dn^{2}$ time when $n$ is even
and $Cn$ time when $n$ is odd.
Or, we may only be able to prove that an algorithm
never uses more than $En^{2}$ time and never less than
$Fn$ time.
In either circumstance we can claim neither $\Theta (n)$ nor
$\Theta (n^{2})$ to be the order of the time usage of the algorithm.
O and $\Omega $ notation will allow us to give at least partial information.

{\bf Proposition 2:} Suppose $f$ and $g$ are positive functions
defined on the positive integers, and that
\( \lim_{n \rightarrow \infty} \frac {f(n)}{g(n)} = 0 \), 
then $f=$O$(g)$. $\Box$

{\bf Examples of O:}
$3 n + 2 = $O$(n)$, since $3 n + 2 \leq 4 n$, for all $n \geq 2$.
$100 n + 6 = $O$(n)$, since $100 n + 6 \leq 101 n$, for all $n \geq 10$.
$10 n^{2} + 4 n + 2 = $O$(n^{2})$, since $10 n^{2}+ 4 n + 2 \leq 11 n^{2}$,
for all $n \geq 5$.
$3 n + 2 \neq $O$(1)$, since $3 n + 2$ is not less than or equal to
$c$ for any constant $c$ and all $n , n \geq N$.
$10 n^{2} + 4 n + 2 \neq $O$(n)$.
$10 n^{2} + 4 n + 2 = $O$(n^{4})$. $\Box$

{\bf Proposition 3:} Suppose $f$ and $g$ are positive functions
defined on the positive integers, and that
\( \lim_ {n \rightarrow \infty} \frac {f(n)}{g(n)} = \infty\),
then $f=\Omega (g)$. $\Box$

{\bf Examples of $\Omega $:}
$3 n + 2 = \Omega (n)$, since $3 n + 2 \geq 3 n$ for all $n \geq 1$.
$100 n + 6 = \Omega (n)$, since $100 n + 6 \geq 100 n$ for all $n \geq 1$.
$10 n^{2} + 4 n + 2 = \Omega (n^{2})$ since 
$10 n^{2} + 4 n + 2 \geq n^{2}$ for all $n \geq 1$.
$10 n^{2} + 4 n + 2 = \Omega (n)$.
$10 n^{2} + 4 n + 2 = \Omega (1)$. $\Box$

%\newpage
\vspace{.30in}
\noindent{\bf Useful Properties of O and $\Omega $:}

1. $f = \Theta (g)$ if and only if $f=$O$(g)$ and $f = \Omega (g)$.

2. If $f=$O$(h)$ and $g=$O$(h)$ then $f+g=$O$(h)$.

3. If $f = \Omega (h)$ and $g = \Omega (h)$ then $f+g = \Omega (h)$.

4. If $f=$O$(g)$ and $g=$O$(h)$ then $f=$O$(h)$.

5. If $f = \Omega (g)$ and $g = \Omega (h)$ then $f = \Omega (h)$.

6. Suppose $0<a<b$.  Then $n^{a} = $O$(n^{b})$ and $n^{b} = \Omega (n^{a})$.

7. Suppose $0<a$ and $1<b$, then $\log_{b}n =$O$(n^{a})$ and
$n^{a} = \Omega (\log_{b}n)$.

8. Suppose $1<c$ and $0<a$, then $n^{a}=$O$(c^{n})$ and $c^{n}= \Omega (n^{a})$.
\end{document}
