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}$ Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)=\Omega(g(n)) \Leftrightarrow \exists \ C; n_0 \in \mathbb{N} : |f(n)| \ge C|g(n)| \ \forall \ n \ge n_0}

Note: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)=\Theta(g(n)) \Rightarrow \exists \ L<\infty : \lim_{n\to\infty}\frac{|f(n)|}{|g(n)|}=L}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)=\Theta(g(n)) \Leftrightarrow \exists \ L, U; n_0 \in \mathbb{N} : L|g(n)| \le |f(n)| \le U|g(n)| \ \forall \ n \ge n_0}
Precise definition

Note

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} L|g(n)| & \le |f(n)| \ \forall \ n \ge n_L & \mbox{so}\ f(n) = \Omega(g(n))\\ U|g(n)| & \ge |f(n)| \ \forall \ n \ge n_U & \mbox{and}\ f(n) = O(g(n))\\ f(n) & = \Theta(g(n)) \ \forall \ n \ge \max(n_L, n_U) \end{align}}

Examples

Example 1

• Claim Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5n=O\left(n^2\right)}
• Choose Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C=5} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_0=1}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{Bmatrix}5n&<&5n^2\\\left|5n\right|&\le&5\left|n^2\right|\end{Bmatrix}\ \mbox{true}\ \forall\ n\ge 1}

Example 3

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}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{align}}

Example 4

(See Wikipedia:Binomial coefficient→)

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}

Order of dominance

1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^n)}
2. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n!)}
3. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^2)}
4. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n\log{n})}
5. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)}
6. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\sqrt{n})}
7. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\log{n})}
8. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)}

Comparing Functions

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)=g(n)+O(\sqrt{n})}

This means that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)-g(n)\le \sqrt{n}} up to a constant factor