CSCE 222 Lecture 2

« previous | Friday, January 21, 2011 | next »

Asymptotically Comparing Functions

Let $f(n)=5n$ and $g(n)=n^2$:

• When $n<5$, $f(n)>g(n)$
• Asymptotically, $g$ "grows faster" than $f$, so $g(n)$ ≥ $f(n)$ when $n>5$
• In general, we say $f$ is asymptotically less than or equal to $g$ if and only if there exists a natural number $n_0$ such that $f(n)$ ≥ $g(n)$ for all $n>n_0$ →
  $f\preccurlyeq g\iff \mathrm{\exists }{n}_0\in \mathbb{\mathbb{N}}:f(n)\le g(n)\mathrm{\forall }n\ge n_0$
• Therefore $5n\preccurlyeq n^2$

For more complex problems like $7n^2+6n+2$, take limit to infinity and put it in order notation: $7n^2+6n+2$ is order $n^2$ ($O(n^2)$)

Big O

An upper bound on a function $f$:

$f(n)=O(n)\to f(n)\le Cn\to f(n)\preccurlyeq n$

Precise Definition: $f(n)$ is big oh of (order) $g(n)$ if and only if there exists a constant $C$ and a natural number $n_0$ such that $|f(n)|$ ≤ $C|g(n)|$ for all $n>n_0$ $f(n)=O(g(n))\iff \mathrm{\exists }C;n_0\in \mathbb{\mathbb{N}}:|f(n)|\le C|g(n)|\mathrm{\forall }n\ge n_0$
Precise definition

Big Ω

A lower bound on a function $f$ :

$f(n)=\mathrm{\Omega }(n)\to f(n)\ge Cn\to f(n)\succcurlyeq n$

Precise Definition: $f(n)$ is big omega of $g(n)$ if and only if there exists a constant $C$ and a natural number $n_0$ such that $|f(n)|$ ≥ $C|g(n)|$ for all $n>n_0$ $f(n)=\mathrm{\Omega }(g(n))\iff \mathrm{\exists }C;n_0\in \mathbb{\mathbb{N}}:|f(n)|\ge C|g(n)|\mathrm{\forall }n\ge n_0$

Note: $f(n)=\mathrm{\Omega }(g(n))\iff g(n)=O(f(n))$

Big Θ

Means that function has same asymptotic growth as another function up to multiplication by constants. Similar to squeeze theorem in Calculus for proof of convergence.

$f(n)=\mathrm{\Theta }(g(n))\Rightarrow \mathrm{\exists }L<\mathrm{\infty }:\underset{n\to \mathrm{\infty }}{\lim }\frac{|f(n)|}{|g(n)|}=L$

$f(n)=\mathrm{\Theta }(g(n))\iff \mathrm{\exists }L,U;n_0\in \mathbb{\mathbb{N}}:L|g(n)|\le |f(n)|\le U|g(n)|\mathrm{\forall }n\ge n_0$
Precise definition

Note

$\begin{array}{rlr}L|g(n)|& \le |f(n)|\mathrm{\forall }n\ge n_L& \text{so}f(n)=\mathrm{\Omega }(g(n))\\ U|g(n)|& \ge |f(n)|\mathrm{\forall }n\ge n_U& \text{and}f(n)=O(g(n))\\ f(n)& =\mathrm{\Theta }(g(n))\mathrm{\forall }n\ge \max (n_L,n_U)\end{array}$

Examples

Example 1

• Claim $5n=O\left(n^2\right)$
• Choose $C=5$ and $n_0=1$
• $\left\{\begin{array}{ccc}5n& <& 5n^2\\ \left|5n\right|& \le & 5\left|n^2\right|\end{array}\right\}\text{true}\mathrm{\forall }n\ge 1$

Example 3

$\begin{array}{rl}7n^2+6n+2& =O(n^2)\\ n^3-3n+2& =O(n^3)\\ (7n^2+6n+2)(n^3-3n+2)& =O(n^2\cdot n^3)=O\left(n^5\right)\end{array}$

Example 4

(See Wikipedia:Binomial coefficient→)

$\begin{array}{rl}(\genfrac{}{}{0ex}{}{n}{2})& =\frac{n(n-1)}{2}\\ & =\frac{n^2}{2}+\frac{n}{2}\\ & =\frac{n^2}{2}+O\left(n\right)\\ & =O\left(n^2\right)\end{array}$

Order of dominance

1. $O(n^n)$
2. $O(n!)$
3. $O(n^2)$
4. $O(n\log n)$
5. $O(n)$
6. $O(\sqrt{n})$
7. $O(\log n)$
8. $O(1)$

Comparing Functions

$f(n)=g(n)+O(\sqrt{n})$

This means that $f(n)-g(n)\le \sqrt{n}$ up to a constant factor