Design of Algorithms

Analysis of Algorithms

Analysis of Algorithms

Table of Contents

What analysis measures

Running time

Orders of Growth

Some functions \(\log_{2}n < n < n\log_{2}n < n^2 < n^3 < 2^n < n!\)

Efficiencies

Algorithm run-time can be dependent on particulars of input e.g. sequential search

Efficiency can be:

Asymptotic Notations

Notations for comparing orders of growth:

e.g.
\(n \in O(n^2)\)
\(\frac{n}{2}(n-1)\in O(n^2)\)
\(n^3\not\in O(n^2)\)

Definition: A function $t(n) \in O(g(n))$ if $\exists c \in \R^+, n_0 \in \Z^+$ s.t. $\forall n\ge n_0$: \(t(n) \le cg(n)\)

big_o

Big O

Definition: A function $t(n) \in \Omega(g(n))$ if $\exists c \in \R^+, n_0 \in \Z^+$ s.t. $\forall n\ge n_0$: \(t(n) \ge cg(n)\)

Definition: A function $t(n) \in \Theta(g(n))$ if $\exists c_1,c_2 \in \R^+, n_0 \in \Z^+$ s.t. $\forall n\ge n_0$: \(c_1 g(n) \le t(n) \le c_2 g(n)\)

big_theta

Big $\Theta$

Theorem: If $t_{1}(n) \in O(g_{1}(n))$ and $t_{2}(n) \in O(g_{2}(n))$: \(t_{1}(n)+t_{2}(n) \in O(\max\{g_{1}(n), g_{2}(n)\})\)

Analogous assertions also hold for $\Omega$, $\Theta$

Comparing Orders of Growth

L’Hopital’s rule

\[\lim_{n\rightarrow\infty}\frac{t(n)}{g(n)} = \lim_{n\rightarrow\infty}\frac{t'(n)}{g'(n)}\]

Stirling’s Formula

For large $n$ \(n! \approx \sqrt{2\pi n}\frac{n}{e}^n\)

Efficiency Classes

Class Name Comments
1 constant very few algorithms fall in this class
$\log n$ logarithmic results from cutting problem’s size by constant factor
$n$ linear scan a list of size $n$ e.g. sequential search
$n\log n$ linearithmic divide-and-conquer e.g. mergesort; quicksort
$n^2$ quadratic two embedded loops e.g. basic sorting; $n\times n$ matrix operations
$n^3$ cubic three embedded loops; e.g. often used in linear algebra
$2^n$ exponential generate all subsets of $n$-element set
$n!$ factorial generate all permutations of $n$-element set

Process: Analysing time efficiency of non-recursive algorithms

  1. define parameter indicating input’s size
  2. identify algorithm’s basic operation (typically on innermost loop)
  3. check if number of times basic operation is executed is only a function of input size
    • if not: worst case, average case to be considered separately
  4. set up sum expressing number of times the basic operation is executed
  5. use formulas/sum manipulation to find a closed form solution for the count or determine order of growth

Basic rules

Scalar multiplication

\[\sum_{i=l}^{u}{ca_i} = c\sum_{i=l}^{u}{a_i}\]

Addition

\[\sum_{i=l}^{u}{a_i+b_i} = \sum_{i=l}^{u}{a_i}+\sum_{i=l}^{u}{b_i}\]

\(\sum_{i=l}^{u}1 = u-l+1\) In particular \(\sum_{i=1}^{n}{1} = n\)

Triangle numbers

\[\sum_{i=l}^{n}{i} = \frac{n(n+1)}{2}\]

Geometric series

\[\sum_{i=1}^{n}{x^k} = \frac{1-x^{k+1}}{1-x}\]

Process: analysing time efficiency of recursive algorithms

  1. define parameter indicating input size
  2. identify basic operation
  3. check if number of times basic operation is executed is only a function of input size
    • if not: worst case, average case to be considered separately
  4. set up recurrence relation and initial condition corresponding to number of times basic operation is executed
  5. solve recurrence or ascertain order of growth of its solution

Divide and Conquer

DEFINITION: eventually non-decreasing

DEFINITION: smooth

$f(n)$ is smooth if:

THEOREM:

Let $f(n)$ be smooth. For any fixed integer $b\ge 2$: \(f(bn)\in\Theta(f(n))\) i.e. $\exists c_b, d_b \in \R^+, n_0 \in \Z^+$ s.t. \(d_b f(n) \le f(bn) \le c_b f(n) \text{ for } n\ge n_0\)

THEOREM: Smoothness rule

Let $T(n)$ be an eventually non-decreasing function Let $f(n)$ be a smooth function. If $ T(n) \in \Theta(f(n)) $ for values of $n$ that are powers of $b$ where $b\ge 2$, then: \(T(n) \in \Theta(f(n))\)

THEOREM: Master Theorem

Let $T(n)$ be an eventually non-decreasing function that satisfies the recurrence \(T(n)=aT(n/b)+f(n) \text{ for } n= b^k, k = 1, 2, ...\) \(T(1) = c\) where $a\ge1,b\ge2,c>0$. If $f(n)\in\Theta(n^d)$ where $d\ge0$, then \(T(n)\in\begin{cases}\Theta(n^d)\text{ if }a<b^d\\\ \Theta(n^d\log{n})\text{ if }a=b^d\\\ \Theta(n^{\log{a}_b)}\text{ if }a>b^d\end{cases}\)


Edit this page.