Prerequisite – What is Algorithm | Introduction to Algorithms
Advantages of Divide and Conquer
- Solving difficult problems: Divide and conquer is an efficient method for solving difficult problems. For example, consider the Tower of Hanoi problem which reduces the degree of difficulty since it divides the problem into subproblems that are easily solvable, solving the trivial cases and combining the subproblems to solve the main problem. It makes easier to solve such problems.
- Parallelism: Divide and conquer allows us to solve the subproblems independently which allows execution in multiprocessor machines, such as shared-memory systems where the communication of data between processors don’t require advance planning, because different subproblems can be solved on different processors.
- Memory access: Divide and conquer algorithms make efficient use of memory caches. When subproblem becomes simple and small, it can be solved within the cache, without accessing the slower main memory which saves time and makes the algorithm more efficient.
Disadvantages of Divide and Conquer
- Slow recursion: One disadvantage of the Divide and conquer approach is that sometimes recursion becomes very slow as compared to the iterative loop due to the overhead of the repeated subproblem calls. Also, Divide and conquer uses stack for storing the calls (the state at each point in the recursion). Actually it depends upon the implementation style. Sometimes for large base cases, the overhead of recursion becomes negligible for many problems.
- Complicates sometimes: For some problems, Divide and conquer becomes more complicated than an iterative approach. For example, to add n numbers, a simple loop to add them is much easier than a Divide and conquer approach which breaks the set of numbers into subparts, adds them recursively, and then adds the sums.
Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.