Divide and Conquer

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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_n = a_{n-1} + 1, a_1 = 1 \rightarrow a_n = n }

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_n = 2 a_{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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_{n} = n a_{n-1}, a_1 = 1 \rightarrow a_n = n! }

In general, recurrence relations take the form:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T(n) = a T(n/b) + f(n) }

These terms are broken down as follows:

Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mbox{Time total}}={\mbox{Time per subproblem}}+{\mbox{Time to merge}}}

Here, the sub-problems are broken down into smaller number Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} of pieces of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f(n) = O(n^{ \log_{b}{(a - \epsilon)} })} for some constant Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \epsilon > 0} then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T(n) = \Theta( n^{\log_b{a}} )}

Case 2: Split/Recombine ~ Subproblems

If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f(n) = \Theta( n^{\log_b{a}} \log^k{(x)} )} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T(n) = \Theta( n^{\log_b{a}} \log^{k+1} {n} )} (note that usually Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k=0} )

Case 3: Split/Recombine Dominates (Root Heavy)

If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f(n) = \Omega( n^{\log_b{(a+\epsilon)}} )} for some constant Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \epsilon > 0} , and if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a f(n/b) \leq cf(n)} for some Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c < 1} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T(n) = \Theta( f(n) )}

See Divide and Conquer/Master Theorem for examples.

Resources

MIT OCW

6.046 design and analysis of algorithms

Divide and conquer for FFT: https://www.youtube.com/watch?v=iTMn0Kt18tg

Divide and conquer for Van Emde Boas trees: https://www.youtube.com/watch?v=hmReJCupbNU

Advanced dynamic programming and divide-and-conquer: https://www.youtube.com/watch?v=Tw1k46ywN6E