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