Algorithms For Dummies

Dividing and Conquering

If solving problems were easy, everyone would do it. However, the world is still 

filled  with  unsolved  problems  and  the  condition  isn’t  likely  to  change  anytime 

soon, for one simple reason: Problems often appear so large that no solution is 

imaginable. Ancient warriors faced a similar problem. An opposing army would 

seem so large and their forces so small as to make the problem of winning a war 

unimaginably hard, perhaps impossible. Yet, by dividing the opposing army into 

small  pieces  and  attacking  it  a  little  at  a  time,  a  small  army  could  potentially 

defeat  a  much  larger  opponent.  (The  ancient  Greeks,  Romans,  and  Napoleon 

Bonaparte  were  all  great  users  of  the  divide-and-conquer  strategy;  see  

Napoleon For Dummies, by J. David Markham [Wiley], for details.)

You face the same problem as those ancient warriors. Often, the resources at your 

disposal seem quite small and inadequate. However, by dividing a huge problem 

into small pieces so that you can understand each piece, you can eventually create 

a solution that works for the problem as a whole. Algorithms have this premise at 

---

CHAPTER 2