Algorithm Analysis

Basic Notations

We must have some notation to better describe our algorithm.

Definitions

(i) We call \(T(N)=O(f(N))\), if there exists positive constants \(c\), \(n_0\), such that

\[ T(N)\leq cf(N), \quad \forall N\geq n_0 \]

(ii) We call \(T(N)=\Omega(g(N))\), if there exists positive constants \(c\), \(n_0\), such that

\[ T(N)\geq cg(N), \quad \forall N\geq n_0 \]

(iii) we call \(T(N)=\Theta(h(N))\), if and only if \(T(N)=O(h(N))\) and \(T(N)=\Omega(h(N))\).

(iv) we call \(T(N)=o(p(N))\), if forall constant \(c>0\), there exists \(n_0\) such that

\[ T(N)<cp(N),\quad \forall N>n_0 \]

Or less formally, \(T(N)=o(p(N))\) if \(T(N)=O(p(N))\) and \(T(N)\neq \Theta(p(N))\).

The following rules are usually really useful for algorithm analysis.

Rules

(i) If \(T_1(N)=O(f(N))\) and \(T_2(N)=O(g(N))\), then

\[ \begin{align*} T_1(N)+T_2(N)&=O(f(N)+g(N))\quad \text{(steps summation)}\\ T_1(N)\times T_2(N)&=O(f(N)\times g(N)) \quad \text{(steps multiplication)}. \end{align*} \]

(ii) If \(T(N)\) is a polynomial of degree \(k\), then

\[ T(N)=\Theta(N^k). \]

(Proved by find \(c_1\), \(c_2\) to be its upper and lower bound)

(iii) \(\log^kN=O(N)\), \(\forall k\).

Recursions

We take Merge Sort as an example.

Merge

Merge(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q
    L[1...(n1 + 1)]
    R[1...(n2 + 1)]
    for i = 1 to n1
        L[i] = A[p + i - 1]
    for j = 1 to n2
        R[j] = A[q + j]
    L(n1 + 1) = R(n2 + 1) = +inf
    for k = p to r
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else
            A[k] = R[j]
            j = j + 1

whose time cost is \(O(N)\), where \(N=r+p-1\).

MergeSort

MergeSort(A, p, r)
    if p < r
        q = (p + r) / 2
        MergeSort(A, p, q)
        MergeSort(A, q + 1, r)
        Merge(A, p, q, r)

Assume the time cost of MergeSort is \(T(N)\), where \(N=r+p-1\), then we have

\[ T(N)=\begin{cases}O(1),\quad N=1\\ 2T(N/2)+O(N),\quad N>1\end{cases} \]

It is apparent to draw a graph of tree for this recursion, get its time cost and then prove it using Induction.

Generalize the above thoughts and we have the following theorem.

Master Theorem

Assume \(T(N)\) is the time cost for a recursive algorithm, and satisfies

\[ T(N)=\begin{cases}O(1),\quad N=1\\ aT(N/b)+f(N),\quad N>1\end{cases} \]

where \(a\geq 1\), \(b>1\) and \(f(N)>0\) for sufficient large \(N\).

(i) If there exists \(\varepsilon>0\) such that \(f(N)=O(N^{\log_b{a-\varepsilon}})\), then \(T(N)=\Theta(N^{\log_ba})\).

(ii) If \(f(N)=\Theta(N^{\log_ba})\), then \(T(N)=\Theta(N^{\log_b a}\log N)\).

(iii) If there exists \(\varepsilon>0\), such that \(f(N)=\Omega(N^{\log_b a+\varepsilon})\), and for sufficient large \(N\), \(af(N/b)\leq cf(N)\), \(c<1\), then \(T(N)=\Theta(f(N))\).

The above \(\varepsilon\) in (i) and (iii) denotes the relationship on polynomial. And the latter condition in (iii) of the above theorem is called regularity condition.

The focus is to compare the relative size between \(N^{\log_b a}\) and \(f(N)\). If the former is larger, then time cost is determined by \(T(N)=aT(N/b)\), which is \(O(N^{\log_b a})\), meaning the bifurcation of the tree is large enough such that the time cost of each layer can be ignored. However, on the other hand, if the latter is larger, then time cost is determined by \(f(N)\), which is \(O(f(N))\).

Q1. Solve for time cost \(T(n)\) in the following situation

(i) \(T(n)=9T(n/3)+n\)

(ii) \(T(n)=T(2n/3)+1\)

(iii) \(T(n)=3T(n/4)+n\lg n\)

Answer for (i)Answer for (ii)Answer for (iii)

\[ n^{\log_b a}=n^{\log_3 9}=n^2>n \]

so

\[ f(n)=n=O(n^{\log_b a}) \]

which is (i) of Master Theorem. So \(T(n)=\Theta(n^2)\).

\[ n^{\log_b a}=n^{\log_{3/2} 1}=n^0=1 \]

so

\[ f(n)=1=\Theta(1)=\Theta(n^{\log_b a}) \]

which is (ii) of Master Theorem. So \(T(n)=\Theta(\log n)\).

\[ n^{\log_b a}=n^{\log_4 3}<n^1<n\lg n \]

which does not satisfy (i), (ii) of Master Theorem, so we need to confirm if it satisfies the regularity condition of (iii) in Master Theorem. Notice that

\[ af(n/b)=3{\frac{n}{4}}\lg \left({\frac{n}{4}}\right) \]

So if we choose \(c=3/4\), then

\[ af(n/b)\leq cf(n), \forall n\geq 1 \]

So it satisfies (iii) of Master Theorem. Thus time cost \(T(n)=\Theta(n\log n)\)

Notice that there exists gap between (i) and (ii) in Master Theorem, cause some function may not satisfy \(\varepsilon\). There also exsits a gap between (i) and (ii) in Master Theorem, cause the regularity condition.

Q2. Solve for time cost \(T(n)\) in the following situation

(i) \(T(n)=2T(n/2)+n\lg n\)

(ii) \(T(n)=T(n/2)+n(2-\cos n\pi)\)

Answer

The above two could not be solved by Master Theorem. We have to use recursive tree.

Divide & Conquer

• 二分搜索

C++

BinarySearch(A, x)
    left, right = 0, len(A)-1

    while left<=right:
        mid = (left+right)/2
        if(x==A[mid]):
            return mid;
        else if (A[mid]<x):
            left = mid+1;
        else if (A[mid]>x):
            right = mid-1;

    return -1;

time cost \(O(log n)\), space cost \(O(1)\).

C++

BinarySearch(A, x, left, right)
    if left> right:
        return -1;

    mid = (left+right)/2;

    if(A[mid]==x):
        return mid;
    else if (A[mid]<x):
        return BinarySearch(A,x, mid+1,right);
    else if (A[mid]>x):
        return BinarySearch(A,x, left, mid-1);

time cost \(O(log n)\), space cost \(O(log n)\).