Notes

Skiena Chapter 4

Powerful technique for solving problems - break problems down into smaller problems.

The basic idea behind divide and conquer is, you are looking for a problem where it is faster to solve the problem in pieces AND TO MERGE THE PIECES than it is to solve the overall problem.

Merge sort is a good example of divide and conquer: merge must take less time than solving the two subproblems, which will make the algorithm efficient overall. Merge sort is just merging two lists, which is O(n), and getting each of the lists costs O(n log n).

Analyzing divide-and conquer algorithms depends on solving the asymptotic behavior of the divide-and-conquer algorithm's recurrence relations.

Recurrence Relations

A recurrence relation is an alternative representation for functions. (Somewhat related is Stephen Wolfram's idea that the universe is fundamentally digital, and that we need cellular autonoma and self-replicating patterns, to effectively understand and describe the world.)

We can represent a polynomial using a recurrence. Multiplication is achieved by having a recurrence relation in which things are added together:

$a_{n}=a_{n-1}+1,a_{1}=1\rightarrow a_{n}=n$

We can also represent exponential functions by multiplying successive terms together:

$a_{n}=2a_{n-1},a_{1}=1\rightarrow a_{n}=2^{n-1}$

We can also describe more unusual, or harder-to-describe, functions, like the factorial function, with very succinct notation:

$a_{n}=na_{n-1},a_{1}=1\rightarrow a_{n}=n!$

In general, recurrence relations take the form:

$T(n)=aT(n/b)+f(n)$

These terms are broken down as follows:

${\mbox{Time total}}={\mbox{Time per subproblem}}+{\mbox{Time to merge}}$

Here, the sub-problems are broken down into smaller number $a$ of pieces of size ${\frac {n}{b}}$ .

The Master Theorem

Main article: Divide and Conquer/Master Theorem

The Master Theorem is used to analyze three distinct cases for divide-and-conquer recurrences:

Case 1: Subproblems Dominate (Leaf-Heavy)

If $f(n)=O(n^{\log _{b}{(a-\epsilon )}})$ for some constant $\epsilon >0$ then $T(n)=\Theta (n^{\log _{b}{a}})$

Case 2: Split/Recombine ~ Subproblems

If $f(n)=\Theta (n^{\log _{b}{a}}\log ^{k}{(x)})$ , then $T(n)=\Theta (n^{\log _{b}{a}}\log ^{k+1}{n})$ (note that usually $k=0$ )

Case 3: Split/Recombine Dominates (Root Heavy)

If $f(n)=\Omega (n^{\log _{b}{(a+\epsilon )}})$ for some constant $\epsilon >0$ , and if $af(n/b)\leq cf(n)$ for some $c<1$ , then $T(n)=\Theta (f(n))$