4. Divide and Conquer

Niccolò Machiavelli, the famous military strategist, in The Art of War (1521) wrote that a captain should endeavor with every act to divide the forces of the enemy. Machiavelli advises that this act should be achieved either by making him suspicious of his men in whom he trusted, or by giving him cause that he has to separate his forces, and, because of this, become weaker.

In politics, sociology and military strategy, the technique of Divide and Rule refers to the strategy of causing rivalries and fomenting discord amongst rivals and subordinates to maintain control and power. In human history, it has been effectively used to empower the sovereign to control subjects, populations, or quash factions of dissent, who collectively might be able to oppose its rule.

In computer science, however, this technique is used to bring down pesky time and space complexities of inefficient algorithms.

Divide and Conquer is a strategy of solving a problem by breaking the problem into smaller subproblems, solving the subproblems, and combining them to get the desired solution. It is applicable to problems that can be expressed recursively in terms of two or more subproblems of the same or related type, called recurrence relations. The original problem is continually divided into smaller subproblems until these become simple enough to be solved directly. The solutions to the subproblems are then combined to give a solution to the original problem.

For the same problem, divide and conquer algorithms often scale better than their brute force counterparts.

Fig. 4.1 Comparison betwen brute force and divide and conquer algorithms is like comparison between brain and brawn.

In case of search, where the brute force algorithm is linear \(O(n)\), the divide and conquer algorithm is logarithmic \(O(\text{log n})\). In case of sorting, where the brute force algorithm is quadratic \(O(\text{n}^2)\), the divide and conquer algorithm is log linear \(O(\text{n log n})\).