 In Progress
Lesson 14 of 43
In Progress

# General Method

In Computer Science divide and conquer is an Algorithm design  paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

This divide and conquer technique is the basis of efficient algorithms for all kinds of problems, such as sorting (e.g., quicksort, merge sort), multiplying large numbers (e.g. the Karatsuba algorithm), finding the closest pair of points, syntactic analysis (e.g., top-down parsers), and computing the discrete Fourier transform (FFTs)

The divide and conquer paradigm is often used to find the optimal solution of a problem. Its basic idea is to decompose a given problem into two or more similar, but simpler, sub problems, to solve them in turn, and to compose their solutions to solve the given problem. Problems of sufficient simplicity are solved directly.

To be more precise, suppose we consider the divide-and-conquer strategy when it splits the input into two sub problems of the same kind as the original problem.This splitting is typical of many of the problems we examine here. We can write a control abstraction that mirrors the way an algorithm based on divide-and-conquer will look.By a control abstraction we mean a procedure whose flow of control is clear but whose primary operations are specified by other procedures whose precise meanings are left undefined. DAndC (Algorithm 1)is initially invoked as DAndC(P), where P is the problem to be solved.

Small(P)is a Boolean-valued function that determines whether the input size is small enough that the answer can be computed without splitting.If this is so,the function S is invoked. Otherwise the problem P is divided into smaller sub problems. These sub problems P1,P2,…………….Pk are solved by recursive applications of DAndC. Combine is a function that determines the solution to P using the solutions to the k sub problems. If the size of P is n and the sizes of the k sub problems are n1,n2,…………..nk, respectively,then the computing time of DAndC is described by the recurrence relation.

where T(n) is the time for DAndC on any input of size n and g(n) is the time to compute the answer directly for small inputs. The function f(n) is the time for dividing P and combining the solutions to sub problems. For divide and-conquer- based algorithms that produce sub problems of the same type as the original problem,it is very natural to first describe such algorithms using recursion.

The complexity of many divide-and-conquer algorithms is given by recurrences of the form

where a and b are known constants.We assume that T(1) is known and n is a power of b (i.e.,n = b^k).

One of the methods for solving any such recurrence relation is called the substitution method. This method repeatedly makes substitution for each occurrence of the function Tin the right-hand side until all such occurrences disappear.

The name “divide and conquer” is sometimes applied to algorithms that reduce each problem to only one sub-problem, such as the binary search algorithm for finding a record in a sorted list  These algorithms can be implemented more efficiently than general divide-and-conquer algorithms; in particular, if they use tail recursion, they can be converted into simple loops. Under this broad definition, however, every algorithm that uses recursion or loops could be regarded as a “divide and conquer algorithm ”