Computational complexity

Watching the function growth based on selected parameter
Omitting multiplicative and additive constants

Asymptotical upper bound $O$

$g(n)$ is asymptotical upper bound for $f(n)$ (at most $n$ instructions)

$$O(g(n))=\{f(n);\exists c,n_0>0,\forall n>n_0:0\le f(n)\le c\ast g(n)\}$$ $$f(n)=O(g(n))⟺\underset{n\to \infty }{\lim }\frac{|f(n)|}{g(n)}<\infty$$

Asymptotical lower bound $\Omega$

$g(n)$ is asymptotical lower bound for $f(n)$ (at least $n$ instructions)

$$\Omega (g(n))=\{f(n);\exists c,n_0>0,\forall n>n_0:0\le c\ast g(n)\le f(n)\}$$

Asymptotically tight bound $\Theta$

$g(n)$ is asymptotical tight bound for $f(n)$ (approximately $n$ instructions)

$$\Theta (g(n))=\{f(n);\exists c_1,c_2,n_0>0,\forall n>n_0:0\le c_1\ast g(n)\le f(n)\le c_2\ast g(n)\}$$ $$f(n)=\Theta (g(n))⟺f(n)=O(g(n))\wedge f(n)=\Omega (g(n))$$

Imprecise bounds $o$ and $\omega$

$o(g(n))$ is an imprecise upper bound for $f(n)$

$$o(g(n))=\{f(n);\exists c,n_0>0,\forall n>n_0:0\le f(n)<c\ast g(n)\}$$ $$f(n)=o(g(n))⟺\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=0$$

$\omega (g(n))$ is an imprecise lower bound for $f(n)$

$$o(g(n))=\{f(n);\exists c,n_0>0,\forall n>n_0:0\le c\ast g(n)<f(n)\}$$ $$f(n)=o(g(n))⟺\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=\infty$$

Properties of asymptotic bounds

Transitivity:

$$\begin{array}{rl}f(n)=\Theta (g(n))\wedge g(n)=\Theta (h(n))& ⟹f(n)=\Theta (h(n))\\ f(n)=O(g(n))\wedge g(n)=O(h(n))& ⟹f(n)=O(h(n))\\ f(n)=\Omega (g(n))\wedge g(n)=\Omega (h(n))& ⟹f(n)=\Omega (h(n))\\ f(n)=o(g(n))\wedge g(n)=o(h(n))& ⟹f(n)=o(h(n))\\ f(n)=\omega (g(n))\wedge g(n)=\omega (h(n))& ⟹f(n)=\omega (h(n))\end{array}$$

Reflexivity:

$$\begin{array}{rl}f(n)& =\Theta (f(n))\\ f(n)& =O(f(n))\\ f(n)& =\Omega (f(n))\end{array}$$

Symmetry:

$$f(n)=\Theta (g(n))⟺g(n)=\Theta (f(n))$$

Transpose symmetry:

$$\begin{array}{rl}f(n)=O(g(n))& ⟺g(n)=\Omega (f(n))\\ f(n)=o(g(n))& ⟺g(n)=\omega (f(n))\end{array}$$

$f(n)$ and $g(n)$ are not always in relation - either with $\Theta$/$O$/$\Omega$

Analysis of algorithms

Watching algorithm’s complexity through resource requirements:

• number of operations - time
• memory consumption
• network accesses

Random-Access Machine: abstract machine for approximating hardware

• uniprocessor, random access to memory locations
• constant time for most operations, numbers take limited amount of memory
• no parallelism, memory hierarchies (caches)

In most cases:

• only worst and average cases are important
• only the fastest growing (asymptotically important) terms are important