# Divide and conquer

An algorithm strategy, such as dynamic programming, that divides a problem into parts. Suppose $LaTeX: T(n)$ is the time complexity for a problem of size $LaTeX: n$, and that dividing the problem into $LaTeX: s$ subproblems, each of size $LaTeX: b$, takes $LaTeX: S(n)$ additional time. Then, $LaTeX: T(n) = sT(n/b) + S(n)$ is called the divide-and-conquer recurrence relation. If $LaTeX: S(n)=c > 0$ (a constant) and $LaTeX: b > 1$, $LaTeX: T(n) = O(n^[\log_b(s)])$ for $LaTeX: n=b,2b,3b, \ldots,$ and $LaTeX: T(n) = O(log(n))$ if $LaTeX: s=1$. For example, if a bisection method is used (as in searching a sorted list), the divide and conquer recurrence is $LaTeX: T(n) = T(n/2) + 2$ for $LaTeX: n=2,4,6,8, \ldots$. This implies $LaTeX: T(n) = O(log(n))$ since $LaTeX: s=1$ and $LaTeX: b=2$.