Complexity of Algorithms

Table of contents

1. Commonly used complexity classes
2. Asymptotic notation
   1. Big-O notation
   2. Big-Omega notation
   3. Big-Theta notation
3. Master theorem
   1. Divide-and-conquer recurrence relations
      1. Simple form
      2. Advanced form
   2. Decreasing recurrence relations
4. Amortized analysis
5. Examples

---

Commonly used complexity classes

• $1$: constant
• $\log \log (n)$
• $\sqrt{\log (n)}$
• $log(n)$: logarithmic
• $\sqrt{n}$: square root
• $n$: linear
• $\log (n!)$
• $n\log (n)$: loglinear
• $n^c$: polynomial
• $c^n$: exponential
• $n!$: factorial

Commonly used definitions in complexity analysis

Properties of logarithms

$$\log (x^y)=y\log (x)$$ $$a^{{\log }_b(x)}=x^{{\log }_b(a)}$$ $$\log (xy)=\log (x)+\log (y)$$ $$\log (\frac{x}{y})=\log (x)-\log (y)$$ $${\log }_b(x)=\frac{{\log }_a(x)}{{\log }_a(b)}$$ $$\sum _{k=1}^n\log (k)\approx n\log (n)$$

Arithmetic series

$$\sum _{k=1}^{n}k=1+2+\cdots +n=\frac{n(n+1)}{2}$$ $$\sum _{k=a}^{b}k=(b-a+1)\frac{b+a}{2}$$

Geometric series

$$\sum _{k=0}^{n}a{r}^k=a+ar+a{r}^2+\cdots +a{r}^n=\frac{a(1-r^{n+1})}{1-r}$$

Harmonic series

$$\sum _{k=1}^n\frac{1}{k}=1+\frac{1}{2}+\cdots +\frac{1}{n}\approx \log (n)$$

Faulhaber’s formula

Special case of power sum.

$$\sum _{k=1}^n{k}^p=1^p+2^p+\cdots +n^p\approx \frac{n^{p+1}}{p+1}$$

---

Asymptotic notation

Big-O notation

Big-O $O$ is for the upper bound (worst case).

Not necessarily tight.

For some function $f$ and $g$,

$$\mathrm{\exists }{n}_0,c>0\text{ s.t. }\mathrm{\forall }n\ge n_0,f(n)\le cg(n)⟹f(n)=O(g(n))$$

• Transitivity: $f(n)=O(g(n))\wedge g(n)=O(h(n))⟹f(n)=O(h(n))$
• Reflexivity: $f(n)=O(f(n))$

Big-Omega notation

Big-Omega $\mathrm{\Omega }$ is for the lower bound (best case).

Not necessarily tight.

For some function $f$ and $g$,

$$\mathrm{\exists }{n}_0,c>0\text{ s.t. }\mathrm{\forall }n\ge n_0,f(n)\ge cg(n)⟹f(n)=\mathrm{\Omega }(g(n))$$

• Transitivity
• Reflexivity
• Transpose symmetry: $f(n)=\mathrm{\Omega }(g(n))⟺g(n)=O(f(n))$

Big-Theta notation

Big-Theta $\mathrm{\Theta }$ is for the tight bound (average case).

For some function $f$ and $g$,

$$\mathrm{\exists }{n}_0,c_1,c_2>0\text{ s.t. }\mathrm{\forall }n\ge n_0,c_{1}g(n)\le f(n)\le c_{2}g(n)⟹f(n)=\mathrm{\Theta }(g(n))$$

• Transitivity
• Reflexivity
• Symmetry: $f(n)=\mathrm{\Theta }(g(n))⟺g(n)=\mathrm{\Theta }(f(n))$

---

Master theorem

Divide-and-conquer recurrence relations

For recursive, divide-and-conquer algorithms, the master theorem can be used to determine the asymptotic complexity.

Simple form

If the algorithm has the following recurrence relation,

$$T(n)=aT(\frac{n}{b})+O(n^d)$$

where $a>0$, $b>1$, and $d\ge 0$, you may use the following rules of Master theorem.

• If $a<b^d$ (dominated by the work at root),

  $$T(n)=O(n^d)$$

• If $a=b^d$ (work is evenly distributed in each layer),

  $$T(n)=O(n^d\log (n))$$

• If $a>b^d$ (dominated by the work at leaves),

  $$T(n)=O(n^{{\log }_b(a)})$$

Advanced form

Advanced form of Master theorem

If the algorithm has the following recurrence relation,

$$T(n)=aT(\frac{n}{b})+\mathrm{\Theta }(n^k{\log }^p(n))$$

where $a\ge 1$, $b>1$, $k\ge 0$, and $p\in \mathbb{R}$, you may use the following rules of Master theorem.

• If $a>b^k$,

  $$T(n)=\mathrm{\Theta }(n^{{\log }_b(a)})$$

• If $a=b^k$,
  • If $p>-1$,

    $$T(n)=\mathrm{\Theta }(n^{{\log }_b(a)}{\log }^{p+1}(n))$$

  • If $p=-1$,

    $$T(n)=\mathrm{\Theta }(n^{{\log }_b(a)}\log \log (n))$$

  • If $p<-1$,

    $$T(n)=\mathrm{\Theta }(n^{{\log }_b(a)})$$

• If $a<b^k$,
  • If $p\ge 0$,

    $$T(n)=\mathrm{\Theta }(n^k{\log }^p(n))$$

  • If $p<0$,

    $$T(n)=O(n^k)$$

Decreasing recurrence relations

If the algorithm has the following recurrence relation,

$$T(n)=aT(n-b)+O(n^d)$$

where $a>0$, $b>0$, you may use the following rules of Master theorem.

• If $a<1$ (dominated by the work at root),

  $$T(n)=O(n^d)$$

• If $a=1$ (work is evenly distributed in each layer),

  $$T(n)=O(n^{d+1})$$

• If $a>1$ (dominated by the work at leaves),

  $$T(n)=O(n^d{a}^{n/b})$$

---

Amortized analysis

Amortized analysis is a method for analyzing a sequence of operations. It is often used to show that a sequence of operations is efficient.

Even if a single operation is expensive, the amortized cost of each operation can be small if the expensive operation is performed rarely.

Amortized analysis is used when the worst-case asymptotic analysis over a sequence of operations is unfairly pessimistic.

---

Examples

Go to page