Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

divide and conquer
algorithms

# What is the divide and conquer paradigm? Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

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

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.

RELATED TAGS

divide and conquer
algorithms 