[FrontPage] [TitleIndex] [WordIndex]

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Divide and conquer is an algorithm design technique where we split a problem into to or more subproblems of approximately the same size.

A typical divide and conquer algorithm has a running time given by a recurrence of the form

• T(n) = 2T(n/2) + f(n)

or more generally

• T(n) = aT(n/b) + f(n),

where f(n) is the cost of generating the recursive subproblems and combining their results.

Such recurrences can usually be solved using the MasterTheorem.

For the first recurrence, the solution is

• Theta(n) if f(n) is O(n1-epsilon) for some epsilon > 0.

• Theta(n log n) if f(n) is Theta(n).
• Theta(f(n)) if f(n) is Omega(n1+epsilon) for some epsilon > 0, and satisfies the geometric-series requirement that 2T(n/2) is less than cT(n) for some c < 1.

Since most functions fit into one of these three cases, the cost of an even-split divide and conquer algorithm is largely determined by f(n).

2014-06-17 11:58