Training Trains Internship
Student login
← Algorithm Design learning path
Algorithm Design · Module 2 of 10

Divide and conquer

Split problems, solve parts and combine.

📖 Key ideas

  1. Divide the problem into smaller subproblems.
  2. Conquer each recursively.
  3. Combine results.
  4. Examples: merge sort, quick sort, binary search, Strassen's matrix multiplication.
  5. Often gives O(n log n) solutions.
💡 Real-life example: Divide and conquer is cleaning a house room by room, then the whole house is clean.
DivideSplit into subproblems
ConquerSolve subproblems recursively
CombineMerge sub-results
Merge sortDivide-and-conquer sort