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)\longrightarrow f\in O(g)$
• $O(f)=O(g)\longrightarrow O(f)\subseteq O(g)$

Big-Oh

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

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

$O(g)=\left\{f:\mathbb {N} \to \mathbb {C} \mid \exists u>0\ \exists n_{0}\in \mathbb {N} \ \forall n\geq n_{0}\ \left|f(n)\right|\leq u\,\left|g(n)\right|\right\}$

Little-Oh

$o(g)=\left\{f:\mathbb {N} \to \mathbb {C} ~{\bigg |}~\lim _{n\to \infty }{\frac {\left|f(n)\right|}{\left|g(n)\right|}}=0\right\}$

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

Big-Ω

$\Omega (g)=\left\{f:\mathbb {N} \to \mathbb {C} \mid \exists d>0\ \exists n_{0}\in \mathbb {N} \ \forall n\geq n_{0}\ d\,\left|g(n)\right|\leq \left|f(n)\right|\right\}$

Big-Θ

$\Theta (g)=\left\{f:\mathbb {N} \to \mathbb {C} \mid \exists u,d>0\ \exists n_{0}\in \mathbb {N} \ \forall n\geq n_{0}\ d\,\left|g(n)\right|\leq \left|f(n)\right|\leq u\,\left|g(n)\right|\right\}$

Corrected Proof of Sorting Lower Bound

${\begin{aligned}2^{h}&\geq n!\\\log _{2}{2^{h}}&\geq \log _{2}(n!)=\log _{2}(n(n-1)\dots (2)(1))\\h&\geq \log _{2}(n!)\geq \log _{2}\left(\left({\frac {n}{2}}\right)^{\frac {n}{2}}\right)\\h&\geq {\frac {n}{2}}\log _{2}\left({\frac {n}{2}}\right)={\frac {n}{2}}\log _{2}{n}-{\frac {n}{2}}\log _{2}{2}\\h&\in \Omega (n\log {n})\end{aligned}}$