algorithm design techniques are not we generally insist that the subproblems be disjoint (that isessentially nonoverlappinglet us review some of the recursive algorithms that have been covered in this text we have already seen several divide-and-conquer algorithms in section we saw an ( log nsolution to the maximum subsequence sum problem in we saw linear-time tree traversal strategies in we saw the classic examples of divide and conquernamely mergesort and quicksortwhich have ( log nworst-case and averagecase boundsrespectively we have also seen several examples of recursive algorithms that probably do not classify as divide-and-conquerbut merely reduce to single simpler case in section we saw simple routine to print number in we used recursion to perform efficient exponentiation in we examined simple search routines for binary search trees in section we saw simple recursion used to merge leftist heaps in section an algorithm was given for selection that takes linear average time the disjoint set find operation was written recursively in showed routines to recover the shortest path in dijkstra' algorithm and other procedures to perform depth-first search in graphs none of these algorithms are really divide-and-conquer algorithmsbecause only one recursive call is performed we have also seenin section very bad recursive routine to compute the fibonacci numbers this could be called divide-and-conquer algorithmbut it is terribly inefficientbecause the problem really is not divided at all in this sectionwe will see more examples of the divide-and-conquer paradigm our first application is problem in computational geometry given points in planewe will show that the closest pair of points can be found in ( log ntime the exercises describe some other problems in computational geometry which can be solved by divide and conquer the remainder of the section shows some extremely interestingbut mostly theoreticalresults we provide an algorithm that solves the selection problem in (nworst-case time we also show that -bit numbers can be multiplied in ( operations and that two matrices can be multiplied in ( operations unfortunatelyeven though these algorithms have better worst-case bounds than the conventional algorithmsnone are practical except for very large inputs running time of divide-and-conquer algorithms all the efficient divide-and-conquer algorithms we will see divide the problems into subproblemseach of which is some fraction of the original problemand then perform some additional work to compute the final answer as an examplewe have seen that mergesort operates on two problemseach of which is half the size of the originaland then uses (nadditional work this yields the running-time equation (with appropriate initial conditionst( ( / (nwe saw in that the solution to this equation is ( log nthe following theorem can be used to determine the running time of most divide-and-conquer algorithms