MATH 302 Lecture 2

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

Binary insertion sort

Insertion sort using linear search requires $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 $O(n\log n)$

Asymptotic Analysis

$\underset{x\to \mathrm{\infty }}{\lim }\left|\frac{f(x)}{g(x)}\right|=\{\begin{array}{ll}c\ne 0& f\in \mathrm{\Theta }(g)\\ 0& f\in O(g)\\ \mathrm{\infty }& f\in \mathrm{\Omega }(g)\\ \mathrm{D}\mathrm{N}\mathrm{E}& \mathrm{t}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{f}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{s}\end{array}$

Domination (Big-O)

$f(n)=7n^2+22n$ is "asymptotically similar to" $n^2$

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

$|f(n)|\le c|g(n)|$

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

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

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 $|g(x)|\ge C|f(x)|$ for $x>k$

Asymptotic Equivalence (Big-Θ)

"$f$ and $g$ are of the same order"

Example: Factorials

$\begin{array}{rl}n!& =\prod _{k=1}^{n}k=1\times 2\times \dots \times n\\ & \le \underset{n}{\underbrace{n\times n\times \dots \times n}}\\ n!& \in O\left(n^n\right)\end{array}$