# Divide-And-Conquer

Information on this page is taken from *The Algorithm Design Manual* by Steven
S. Skiena.

One of the most powerful techniques for solving problems is to break them
down into smaller, more easily solved pieces. A recursive algorithm starts to
become apparent when we break the problem into smaller instances of the same
type of problem. **Divide-and-conquer** splits the problem in (say) halves,
solves each half, then stitches the pieces back together to form a full
solution. Whenever the merging takes less time than recursively solving the
two subproblems, we get an efficient algorithm. For example, mergesort takes
linear time to merge two sorted lists of \(n/2\) elements, each of which was
obtained in \(O(n \lg n)\) time.

## Recurrence Relations

Many divide-and-conquer algorithms have time complexities that are naturally
modeled by **recurrence relations**. A recurrence relation is an equation that
is defined in terms of itself. The Fibonacci numbers are described by the
recurrence relation \(F_n = F_{n - 1} + F_{n - 2}\). Many other natural
functions are easily expressed as recurrences. For example, \(a_n = 2a_{n -
1}, a_1 = 1 \rightarrow a_n = 2^{n - 1}\).

Divide-and-conquer algorithms tend to break a given problem into some number of smaller pieces (say \(a\)), each of which is of size \(n/b\). Further, they spend \(f(n)\) time to combine these subproblem solutions into a complete result. Let \(T(n)\) denote the worst-case time the algorithm takes to solve a problem of size \(n\). Then \(T(n)\) is given by the following recurrence relation.

\begin{equation} T(n) = aT(n/b) + f(n) \end{equation}For example, the running time behavior of mergesort is governed the recurrence \(T(n) = 2T(n/2) + O(n)\). This recurrence evaluates to \(T(n) = O(n \lg n)\). Binary search is governed by the recurrence \(T(n) = T(n/2) + O(1)\).