Divide and conquer

From Glossary

Jump to: navigation, search

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.

Personal tools