Skip to content
BENIBIX Learn

Divide and Conquer

Development🧮 Algorithms & Data StructuresAlgorithm Design Techniques

Also known as Divide-and-Conquer Algorithm

Cutting a big problem into small ones like it. Solve each, then join the answers.

Think of it like

Think of it like cleaning a big house. Split it into rooms, clean each, and the house is done.

Example

Lucy's merge sort splits 1,000 names into halves, then quarters, down to single names. Joining them back gives one sorted list.

Why it matters

It turns many slow O(n²) problems into fast O(n log n) ones.

Definition

Divide and conquer cuts a big problem into smaller copies of itself. Each small piece is solved, often by splitting again, until the pieces are tiny. Then the answers are joined to answer the big problem. Merge sort, quicksort and binary search all work this way. It is usually written with recursion.

Common mistake

Splitting a problem whose pieces overlap. Then one piece is solved again and again. Dynamic programming fits better.

Key takeaways

  1. 1
    Split. Into smaller copies.
  2. 2
    Solve each. Often by splitting again.
  3. 3
    Join. The answers into one.

Compare