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:

The divide and conquer paradigm
The divide and conquer paradigm

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.

Copyright ©2024 Educative, Inc. All rights reserved