Asymptotic notation

Asymptotic Bounds

• asymptotic upper bound (strict)

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

• asymptotic upper bound

  • $f(n)=O(g(n))$
  • $\forall c>0,\exists n_0>0:\forall n>n_0,0\le f(n)\le c\cdot g(n)$
  • $g(n)=\Omega (f(n))$

• asymptotically tight bounds

  • $f(x)=\Theta (g(n))$
  • $f(n)=O(g(n))\wedge f(n)=\Omega (g(n))$

• asymptotic lower bound

  • $f(n)=\Omega (g(n))$
  • $\forall c>0,\exists n_0>0:\forall n>n_0,0\le c\cdot g(n)\le f(n)$
  • $g(n)=O(f(n))$

• asymptotic lower bound (strict)

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

• The running time of an algorithm is the number of primitive operations or steps executed.

  • The worst-case running time (denoted by $T(n)$) is the maximum number of steps taken on any instance of size $n$.

• $f=O(h)\wedge g=O(h)⟹f+g=O(h)$ (In general, $\forall i,f_i=O(h)⟹\sum f_i=O(h)$)

• If $\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=c>0$ exists, then $f(n)=\Theta (g(n))$

• Transitivity

  • $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))$
  • the same for $\Omega ,o,\omega$

• Reflexivity

  • $f(n)=\Theta (f(n))$
  • $f(n)=O(f(n))$
  • $f(n)=\Omega (f(n))$
  • $n!=o(n^n)$
  • $\log (n!)=\Theta (n\log n)$
  • ${\log }^{k}n=o(n)$ for $k>0$
  • $P_d(n)={\sum }_{k=0}^d{a}_k{n}^k=\Theta (n^d)$

• see also Order of sequences

• $cf(n)=O(f(n))$. (where $c>0$)

• $c\cdot O(f(n))=O(f(n))$ (where $c>0$)

• $c\cdot g(n)=O(f(n))⟺g(n)=O(f(n))$ (where $c>0$)

• $O(f_1(n))+\cdots +O(f_k(n))=O(f_1(n)+\cdots +f_k(n))$

• $O(f_1(n))+\cdots +O(f_k(n))=O(\max \{f_1(n),\dots ,f_k(n)\})$

• $O(f_1(n))\cdots O(f_k(n))=O(f_1(n)\cdots f_k(n))$

• $f(n)=O(g(n))⟹g(n)=\Omega (f(n))$

• If $g=O(f)$ then $f+g=\Theta (f)$ (given $f$ and $g$ are non-negative)

• $f(n)=o(g(n))⟺g(n)=\omega (g(n))$

• $f(n)=o(g(n))⟹\log f(n)=O(\log g(n))$

• $(n+a{)}^b=\Theta (n^b)$ ($b>0$) (e3.1-2)

• $o(g(n))\cap \omega (g(n))=\varnothing$ (e3.1-7)

• $2^{n+1}=O(2^n)$ (e3.1-4)

• If $f(n)$ is a polynomial of degree $d$, in which the leading coefficient $a_d$ is positive, then $f(n)=\Theta (n^d)$

• $\forall b>1,\forall x>0,{\log }_{b}n=O(n^x)$

• $\forall r>1,\forall d>0,n^d=O(r^n)$ (In particular, every exponential grows faster than every polynomial)

Common Running Times

Name	Running Time	$T(n)$
constant time	$O(1)$	$T(n)=c$
log-logarithmic	$O(\log \log n)$
logarithmic time	$O(\log n)$	$\log n,\log (n^2)$
polylogarithmic time	$O((\log n{)}^k),k>1$	$(\log n{)}^2$
fractional power	$O(n^k),0<k<1$
linear time	$O(n)$	$T(n)\le c\cdot n$
linearithmic time	$O(n\log n)$	$T(n)\le c\cdot n\log n$
quasilinear time
quadratic time	$O(n^2)$	$T(n)\le c\cdot n^2$
cubic time	$O(n^3)$	$T(n)\le c\cdot n^3$
polynomial time	$O(n^k),k>1$	$T(n)\le c\cdot n^k$
exponential time	$O(k^n),k>1$
factorial time	$O(n!)$

Chapter 2: Algorithm Analysis

2.1: Computational Tractability

• Proposed Definition of Efficiency:

  1. An algorithm is efficient if it performs well on real input instances.
  2. An algorithm is efficient if it performs quantitatively better than brute-force search in worst-case scenarios.
  3. An algorithm is efficient if it runs in polynomial time.

• A Brute-force search is a straightforward but typically inefficient approach involving the examination of all possible solutions