Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Top-Down Algorithms: Divide-and-Conquer

In this section we discuss a top-down algorithmic paradigm called divide and conquer . To solve a given problem, it is subdivided into one or more subproblems each of which is similar to the given problem. Each of the subproblems is solved independently. Finally, the solutions to the subproblems are combined in order to obtain the solution to the original problem.

Divide-and-conquer algorithms are often implemented using recursion. However, not all recursive methods are divide-and-conquer algorithms. Generally, the subproblems solved by a divide-and-conquer algorithm are non-overlapping.

Example-Binary Search
Example-Computing Fibonacci Numbers
Example-Merge Sorting
Running Time of Divide-and-Conquer Algorithms
Example-Matrix Multiplication