MATH 302 Lecture 2

« previous | Wednesday, August 31, 2011 | next »

Binary insertion sort

Insertion sort using linear search requires 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)} comparisons (worst case)

Since the list is already sorted, we can use binary search to find where the element to be inserted should go. The function now becomes 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})}

Asymptotic Analysis

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 \lim_{x\to\infty} \left|\frac{f(x)}{g(x)}\right| = \begin{cases} c \ne 0 & f \in \Theta(g) \\ 0 & f \in O(g) \\ \infty & f \in \Omega(g) \\ \mathrm{DNE} & \mathrm{test\ fails} \end{cases}}

Domination (Big-O)

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) = 7n^2 + 22n} is "asymptotically similar to" $n^{2}$

A function $f:\mathbb {Z} ^{+}\to \mathbb {R}$ is dominated by another function $g$ if there exists positive constants $k,c$ such that every integer $n>k$ we have

$\left|f(n)\right|\leq c\left|g(n)\right|$

The constants $k,c$ are called "witnesses" to the dominating function $g$

We can say that $f$ is not dominated by $g$ if $\left|f(x)\right|>C\left|g(x)\right|$

General Theorem

A polynomial is dominated by its highest-degree term.

Given $f(n)=a_{k}n^{k}+a_{k-1}n^{k-1}+\dots +a_{0}$

Then $f(n)\preccurlyeq n^{k}$

Example

Show $7n^{2}+22n\preccurlyeq n^{2}$

$n^{2}>n$ for $n>1$,

Reversed Point of View (Big-Ω)

There are positive constants $c,k$ so that $\left|g(x)\right|\geq C\left|f(x)\right|$ for $x>k$

Asymptotic Equivalence (Big-Θ)

"$f$ 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 g} are of the same order"

Example: Factorials

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}n! &= \prod_{k=1}^n k = 1 \times 2 \times \dots \times n \\ &\le \underbrace{n \times n \times \dots \times n}_{n}\\ n! &\in O\left(n^n\right)\end{align}}