Explain Divide n conquer technique?

Divide and conquer was a successful military strategy long before it became an algorithm design paradigm. Generals observed that it was easier to defeat one army of 50,000 men, followed by another army of 50,000 men than it was to beat a single 100,000 man army. Thus the wise general would attack so as to divide the enemy army into two forces and then mop up one after the other.

To use divide and conquer as an algorithm design technique, we must divide the problem into two smaller subproblems, solve each of them recursively, and then meld the two partial solutions into one solution to the full problem. Whenever the merging takes less time than solving the two subproblems, we get an efficient algorithm. Mergesort, discussed in Section gif, is the classic example of a divide-and-conquer algorithm. It takes only linear time to merge two sorted lists of n/2 elements each of which was obtained in tex2html_wrap_inline24820 time.

Divide and conquer is a design technique with many important algorithms to its credit, including mergesort, the fast Fourier transform, and Strassen's matrix multiplication algorithm. However, with the exception of binary search, I find it to be a difficult technique to apply in practice. Therefore, the examples below will illustrate binary search and its variants, which yield simple algorithms to solve a surprisingly wide range of problems.

See link for more info.

Divide And Conquer Technique

In politics and sociology, divide and conquer (also known as divide and rule) is a strategy of gaining and maintaining power by breaking up larger concentrations of power into chunks that individually have less power than the one implementing the strategy. In reality, it often refers to a strategy where small power groups are prevented from linking up and becoming more powerful, since it is difficult to break up existing power structures.

The phrase comes from the Latin divide et impera, which translates to "divide and rule".

Effective use of this technique allows those with little real power to control those who collectively have a lot of power (or would have much power, if they could get united).

Typical elements of this technique involve

* creating or at least not preventing petty feuds among smaller players. Such feuds drain resources and prevent alliances that could challenge the overlords.

* aiding and promoting those who are willing to cooperate with the overlords, often by giving them the lands and wealth of rebellious local rulers.

* fostering distrust and emnity between local rulers.

* encouraging expenditures on personal frivolities (e.g., showy palaces) that leave little money for political manoeuvering and warfare.

This technique requires a lot of skill and political finesse, as well as a good understanding of political science, history and psychology.

"Divide and rule" works only if the subjects of this technique are willing to go along with it (e.g., because it is to their personal advantage), or behave foolishly. It works best in societies where competition between noble families, clans or social classes was already fierce before the overlord took over.

The strategy was used to great effect by administrators of vast empires, including the British, who would play one tribe against another to maintain control of their colonies with a minimal number of British troops.