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\ \Leftrightarrow \ \exists \ n_{0}\in \mathbb {N} \ :\ f(n)\leq g(n)\ \forall \ n\geq 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)\rightarrow f(n)\leq Cn\rightarrow 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))\Leftrightarrow \exists \ C;n_{0}\in \mathbb {N} :|f(n)|\leq C|g(n)|\ \forall \ n\geq n_{0}$
Precise definition

Big Ω

A lower bound on a function $f$ :

$f(n)=\Omega (n)\rightarrow f(n)\geq Cn\rightarrow 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)=\Omega (g(n))\Leftrightarrow \exists \ C;n_{0}\in \mathbb {N} :|f(n)|\geq C|g(n)|\ \forall \ n\geq n_{0}$

Note: $f(n)=\Omega (g(n))\Leftrightarrow 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)=\Theta (g(n))\Rightarrow \exists \ L<\infty :\lim _{n\to \infty }{\frac {|f(n)|}{|g(n)|}}=L$

$f(n)=\Theta (g(n))\Leftrightarrow \exists \ L,U;n_{0}\in \mathbb {N} :L|g(n)|\leq |f(n)|\leq U|g(n)|\ \forall \ n\geq n_{0}$
Precise definition

Note

${\begin{aligned}L|g(n)|&\leq |f(n)|\ \forall \ n\geq n_{L}&{\mbox{so}}\ f(n)=\Omega (g(n))\\U|g(n)|&\geq |f(n)|\ \forall \ n\geq n_{U}&{\mbox{and}}\ f(n)=O(g(n))\\f(n)&=\Theta (g(n))\ \forall \ n\geq \max(n_{L},n_{U})\end{aligned}}$

Examples

Example 1

• Claim $5n=O\left(n^{2}\right)$
• Choose $C=5$ and $n_{0}=1$
• ${\begin{Bmatrix}5n&<&5n^{2}\\\left|5n\right|&\leq &5\left|n^{2}\right|\end{Bmatrix}}\ {\mbox{true}}\ \forall \ n\geq 1$

Example 3

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

Example 4

(See Wikipedia:Binomial coefficient→)

${\begin{aligned}{\binom {n}{2}}&={\frac {n\left(n-1\right)}{2}}\\&={\frac {n^{2}}{2}}+{\frac {n}{2}}\\&={\frac {n^{2}}{2}}+O\left(n\right)\\&=O\left(n^{2}\right)\end{aligned}}$

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)\leq {\sqrt {n}}$ up to a constant factor