Analysis of Algorithms

The issue with the asymptotic complexity analysis is:

  1. We cannot compare algorithms properly.

    Merge sort vs. Quick sort : Merge sort runs in $\Theta(nlogn)$ in the worst case, Quick sort runs in $\Theta(n^2)$ in the worst case but in practice Quick sort is faster and uses half the space.

  2. We cannot predict the running time for a given input size.

Tilde notation may be better since you keep the leading term coefficient & drop lower order terms — asymptotic equivalence.

$$ g(N) \sim f(N) \quad iff \quad \frac {g(N)} {f(N)} \to 1 \quad \text{as} \quad N \to \infty $$

Components of Algorithm Analysis:

Order of growth is used to classify algorithms according to functional growth to describe performance.

<aside> ➗

Galactic Algorithm is an algorithm that will never be used, its benefit wont be seen in this galaxy — for input so large it cant happen in this galaxy.

vs.

Planetary algorithm: Chazelle’s linear time triangulation algorithm (triangulate a polygon in linear time) but the method is much too complicated for implementation.

</aside>

(loglog n factor is less than 6 in this universe??craaazyyyyy)

We not only want the average cost but also the distribution of costs, how likely is the actual thing supposed to be, how close to the average.

e.g. Quick Sort !!

The analysis of quick sort involves defining and solving recurrence relations that mirror directly the recursive nature of the algorithm. In this case, the recurrences must be based on probabilistic statements about the inputs.

If $C_N$ is the average number of compares to sort $N$ elements, we have $C_0 = C_1= 0$ and

$$ C_N = N + 1 + \frac 1 N \sum_{1 \le j \le N} (C_{j-1} + C_{N-j} ), \quad \text{for} \quad N > 1 $$

Then the summation simplifies to $2 \sum_{1\le j \le N} C_{j-1}$ then we multiply by N and subtract the same formula for $N-1$ to eliminate the sum:

$$ NC_N - (N-1)C_{N-1} = 2N + 2C_{N-1} \quad \text{for} \quad N>1 $$

Rearrange & divide both sides by $N(N+1)$ to get

$$ \frac{C_N} {N+1} = \frac{C_{N-1}} {N} + \frac{2} {N+1} \quad \text{for} \quad N>1 $$

Iterating (by substituting several values of $N$ to find a pattern):

$$ \frac{C_N} {N+1} = \frac{C_1} {2} + 2 \sum_{3\le k \le N+1} \frac 1 k $$

which completes the proof, as it follows the well-known approximation to the harmonic number $H_N \approx \ln N + 0.57721$

Recurrences

Recurrences are the first step for building math model, it is an equation that recursively defines a sequence — but we need to carefully specify initial conditions.

Goal is to write a recurrence as a simple function of N.

Basic technique for solving a linear first order recurrence is called Telescoping, once it telescopes to a sum, the issue becomes solving sums (elementary discrete sums) e.g.

$$ a_n = a_{n-1} + n \quad \quad a_0=0 $$

when coefficients are not $1$, multiply/divide by a summation factor :