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(n^1-epsilon) for some epsilon > 0.

• Theta(n log n) if f(n) is Theta(n).

• Theta(f(n)) if f(n) is Omega(n^1+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).

1. Examples

• MergeSort

• QuickSort

• MedianFinding

• BinaryTrees

• IntegerMultiplication

• StrassensAlgorithm

CategoryAlgorithmNotes