Course contentsShow
← Computer Science
Lesson 855 of 2,87220. Recursion Patterns and TechniquesFree lesson

When to Use Divide and Conquer

Recognizing problems suited for divide and conquer: independent subproblems with efficient combine step.

When to Use Divide and Conquer

What you'll learn: How to recognize when a problem is a good candidate for the divide-and-conquer approach.

The Recognition Pattern

Not every problem benefits from divide and conquer. The strategy shines when you can spot two key characteristics:

  1. Independent subproblems: Breaking the problem into smaller pieces creates subproblems that can be solved separately without needing information from each other. Think of Mergesort—sorting the left half doesn't require knowing anything about the right half while you're working on it.

  2. Efficient combine step: After solving subproblems, you must be able to merge their solutions into the final answer relatively quickly (ideally in linear time or better). In Mergesort, merging two sorted halves takes O(n) time—fast enough that the overall algorithm still achieves O(n log n).

The Antipattern

If your subproblems overlap significantly (solving them requires re-solving the same smaller problems repeatedly), divide and conquer becomes wasteful. That's when dynamic programming is the better choice.

If combining solutions is expensive—say, O(n²) or worse—the divide step might not save you time overall.

Quick Checklist

Ask yourself:

  • Can I split this into independent pieces?
  • Is the combine step fast relative to the problem size?
  • Does splitting actually reduce the work?

If yes to all three, divide and conquer is likely your friend. You've already seen this work beautifully in binary search, sorting algorithms, the maximum subarray problem, and closest pair of points.

Key Takeaway: Use divide and conquer when you can split problems into independent subproblems and have an efficient way to combine their solutions—this combination unlocks powerful logarithmic speedups.