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

$\lim _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|={\begin{cases}c\neq 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)

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

Example: Factorials

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