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