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

Split a problem into smaller independent subproblems, solve them recursively and combine results. Running time is described by a recurrence like T(n) = 2T(n/2) + O(n).

Where it is used

Merge sort, quicksort, binary search, FFT, Strassen multiplication.

Common pitfall

Combine step may dominate, and tiny subproblems should switch to a simple method to cut overhead.

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, FFT, Strassen multiplication.
What is the most common mistake with Divide and Conquer?
Combine step may dominate, and tiny subproblems should switch to a simple method to cut overhead.
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