LearnViz CompSci
Home / Learn / Algorithms / Divide and Conquer

Intermediate Topic 22 of 51 Algorithms

Divide and Conquer

Splitting a problem into subproblems solved independently then combined.

How it works

Divide and conquer splits a problem into smaller independent subproblems of the same kind, solves them recursively and combines their answers. Running time is described by recurrences such as T(n) = 2T(n/2) + O(n), solved with the master theorem. The approach naturally exposes parallelism because subproblems do not depend on each other.

Step-by-step walkthrough

  1. Split the problem into independent smaller parts.
  2. The second half is split too.
  3. Each half is solved recursively down to trivial cases.
  4. Sub-answers flow back up.
  5. The combine step merges them into the answer, as merge sort does.

Where it is used

Merge sort, quicksort, binary search, fast exponentiation, Karatsuba multiplication, the closest pair of points, FFT and Strassen's matrix multiplication use divide and conquer.

Common pitfall

If subproblems overlap, the same work is repeated exponentially and dynamic programming is the better tool. Recursion overhead hurts for tiny inputs, so use a cutoff to a simple method. The combine step can dominate cost, and unbalanced splits degrade performance.

Where it fits in the course

Divide and Conquer is topic 22 of 51 in Algorithms, rated Intermediate. It follows Timsort. The next topic is Master Theorem.

Practice and explore

How to study this topic

  1. Read the explanation above and restate the definition in your own words.
  2. Open the interactive lesson and answer its mini quiz.
  3. Read the common pitfall, then write a short example that avoids it.
  4. Check your understanding in the Algorithms quiz, and revisit the topic if you miss a question.

Frequently asked questions

What is Divide and Conquer?
Splitting a problem into subproblems solved independently then combined. It belongs to Algorithms and is an intermediate-level topic.
Where do people use Divide and Conquer?
Merge sort, quicksort, binary search, fast exponentiation, Karatsuba multiplication, the closest pair of points, FFT and Strassen's matrix multiplication use divide and conquer.
What is the most common mistake with Divide and Conquer?
If subproblems overlap, the same work is repeated exponentially and dynamic programming is the better tool.
What should I learn before this topic?
Start with Timsort, the topic just before it in Algorithms.
How can I practice it?
Answer the mini quiz in the interactive lesson, then take the Algorithms quiz.
Is Divide and Conquer hard to learn?
It is an Intermediate topic. Be comfortable with the Beginner topics in this area first, then read the common pitfall carefully, since it is where most mistakes happen.
How long does it take to learn Divide and Conquer?
Most learners can read the explanation and finish the interactive lesson in under an hour. Fluency comes from applying the idea, so plan a few short practice sessions with the quiz.
Which topics are related to Divide and Conquer?
Timsort, Master Theorem, Bucket Sort are closely connected. The full list is in the related topics section of this page.
What should I study after Divide and Conquer?
Continue with Master Theorem, the next topic in Algorithms.

Related topics