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

or more generally

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

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).

Examples


CategoryAlgorithmNotes

DivideAndConquer (last edited 2007-12-25 23:42:04 by localhost)