Skip to main content

DSAPath8 mincore

Divide and Conquer

Divide and conquer solves a problem by splitting it into smaller subproblems, solving them recursively, and combining their results.

DifficultyCore
TierTier 1
ModuleAlgorithmic Techniques
LanguagesPython

Why This Matters

Divide and conquer turns one large problem into several smaller ones. Binary search, merge sort, quicksort, FFT, and many geometric algorithms use this pattern.

Core Idea

The pattern has three steps:

  1. divide the instance
  2. solve the subproblems
  3. combine the results

Worked example: merge sort splits an array in half, sorts each half, then merges the two sorted halves.

The runtime is often described by a recurrence such as:

T(n)=2T(n/2)+O(n).T(n) = 2T(n/2) + O(n).

Common Mistakes

  • Forgetting the combine cost.
  • Assuming every recursive algorithm is divide and conquer. Some recursion is just linear descent.
  • Using the master theorem when subproblem sizes do not match its assumptions.

Exercises

  • Identify divide, solve, and combine steps in merge sort.
  • Explain why binary search has no expensive combine step.
  • Write the recurrence for splitting into three equal subproblems with linear combine cost.

Next Topics

References

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 4.
  • MIT OpenCourseWare. 6.046J Design and Analysis of Algorithms, Spring 2015.