Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

divide and conquer
algorithms
paradigm

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:

svg viewer
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
paradigm
Copyright ©2022 Educative, Inc. All rights reserved

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.

Keep Exploring