What is the divide and conquer paradigm?
Divide and Conquer is an algorithm design paradigm that involves breaking up a larger problem into non-overlapping sub-problems, solving each of these sub-problems, and combining the results to solve the original problems. A problem has non-overlapping sub-problems if you can find its solution by solving each sub-problem once.
The three main steps in the divide and conquer paradigm are:
- divide: involves breaking the problem into smaller, non-overlapping chunks.
- conquer: involves solving the sub-problems recursively.
- combine: involves combining the solutions of the smaller sub-problems to solve the original problem.
Take a look at the pictorial representation of the concept:
Merge sort, binary search, and quick sort are some of the most famous divide and conquer algorithms.
Let’s go over some pros and cons of the divide and conquer paradigm.
Pros
-
Solves difficult problems with less time complexity than its brute-force counterpart.
-
Since the sub-problems are independent, they can be computed in parallel.
Cons
-
Includes recursion which consumes more space.
-
Recursion into small base cases may lead to huge recursive stacks.
