## 2.8 When Not to Use Divide-and-Conquer If possible, we should avoid divide-and-conquer in the following two cases: 1. An instance of size *n* is divided into two or more instances each almost of size *n*. 2. An instance of size *n* is divided into almost *n* instances of size *n/c*, where *c* is a constant. The first partitioning leads to an exponential-time algorithm, where the second leads to a *n*Θ(lg *n*) algorithm. Neither of these is acceptable for large values of *n*. Intuitively, we can see why such partitionings lead to poor performance. For example, the first case would be like Napoleon dividing an opposing army of 30,000 soldiers into two armies of 29,999 soldiers (if this were somehow possible). Rather than dividing his enemy, he has almost doubled their number! If Napoleon did this, he would have met his Waterloo much sooner. As you should now verify, [Algorithm 1.6](LiB0009.html#45) (*n*th Fibonacci Term, Recursive) is a divide-and-conquer algorithm that divides the instance that computes the *n*th term into two instance that compute respectively the (*n* − 1)st term and the (*n* − 2)nd term. Although *n* is not the input size in that algorithm, the situation is the same as that just described concerning input size. That is, the number of terms computed by [Algorithm 1.6](LiB0009.html#45) is exponential in *n*, whereas the number of terms computed by [Algorithm 1.7](LiB0009.html#51) (*n*th Fibonacci Term, Iterative) is linear in *n*. Sometimes, on the other hand, a problem requires exponentiality, and in such a case there is no reason to avoid the simple divide-and-conquer solution. Consider the Towers of Hanoi problem which is presented in Exercise 17. Briefly, the problem involves moving *n* disks from one peg to another given certain restrictions on how they may be moved. In the exercises you will show that the sequence of moves, obtained from the standard divide-and-conquer algorithm for the problem, is exponential in terms of *n* and that it is the most efficient sequence of mvoes given the problem's restrictions. Therefore, the problem requires an exponentially large number of moves in terms of *n*.