CSCE 411 Lecture 3

Lecture Slides

« previous | Friday, August 31, 2012 | next »

Time Complexity

We want to asymptotically count the number of operations independent of compilers and optimization settings.

Sad notation:

• $f=O(g)⟶f\in O(g)$
• $O(f)=O(g)⟶O(f)\subseteq O(g)$

Big-Oh

Let $g:\mathbb{\mathbb{N}}\to \mathbb{ℂ}$ be a function.

Then $O(g)$ is the set of functions:

$O(g)=\{f:\mathbb{\mathbb{N}}\to \mathbb{ℂ}\mid \mathrm{\exists }u>0\mathrm{\exists }{n}_0\in \mathbb{\mathbb{N}}\mathrm{\forall }n\ge n_0|f(n)|\le u|g(n)|\}$

Little-Oh

$o(g)=\{f:\mathbb{\mathbb{N}}\to \mathbb{ℂ}|\underset{n\to \mathrm{\infty }}{\lim }\frac{|f(n)|}{|g(n)|}=0\}$

It follows that $o(f)\subseteq O(f)$

Big-Ω

$\mathrm{\Omega }(g)=\{f:\mathbb{\mathbb{N}}\to \mathbb{ℂ}\mid \mathrm{\exists }d>0\mathrm{\exists }{n}_0\in \mathbb{\mathbb{N}}\mathrm{\forall }n\ge n_{0}d|g(n)|\le |f(n)|\}$

Big-Θ

$\mathrm{\Theta }(g)=\{f:\mathbb{\mathbb{N}}\to \mathbb{ℂ}\mid \mathrm{\exists }u,d>0\mathrm{\exists }{n}_0\in \mathbb{\mathbb{N}}\mathrm{\forall }n\ge n_{0}d|g(n)|\le |f(n)|\le u|g(n)|\}$

Corrected Proof of Sorting Lower Bound

$\begin{array}{rl}{2}^h& \ge n!\\ {\log }_2{2}^h& \ge {\log }_2(n!)={\log }_2(n(n-1)\dots (2)(1))\\ h& \ge {\log }_2(n!)\ge {\log }_2\left({\left(\frac{n}{2}\right)}^{\frac{n}{2}}\right)\\ h& \ge \frac{n}{2}{\log }_2\left(\frac{n}{2}\right)=\frac{n}{2}{\log }_{2}n-\frac{n}{2}{\log }_{2}2\\ h& \in \mathrm{\Omega }(n\log n)\end{array}$