Loading...

Back to Algorithms

Divide & Conquer Algorithms

Master the recursive paradigm of breaking problems into smaller subproblems, solving them independently, and combining their solutions. Learn the Master Theorem and analyze recursive algorithms.

The Three-Step Process

Divide

Break the problem into smaller subproblems of the same type

Key Tips:

• Divide into roughly equal parts
• Ensure subproblems are independent
• Base case should be simple

Conquer

Solve subproblems recursively (base case solves directly)

Key Tips:

• Define clear base cases
• Recursive calls on smaller inputs
• Trust the recursion works

Combine

Merge solutions of subproblems to solve original problem

Key Tips:

• Combine step should be efficient
• May require additional data structures
• Sometimes implicit (like quicksort)

Sorting & Searching

Merge sort, Quick sort, Binary search

Mathematical

Matrix multiplication, FFT, Karatsuba

Geometric

Closest pair, Convex hull, Voronoi diagram

Optimization

Maximum subarray, Selection problems

Classic Divide & Conquer Algorithms

Merge Sort

Divide array into halves, sort recursively, then merge sorted halves

Split array into two equal halves

Recursively sort both halves

Merge two sorted halves into one

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

Quick Sort

Choose pivot, partition around it, recursively sort partitions

O(n log n) avg, O(n²) worst

Choose pivot and partition array

Recursively sort both partitions

No explicit combine step needed

T(n) = T(k) + T(n-k-1) + O(n)

Binary Search

Search sorted array by repeatedly dividing search space in half

O(1) iterative, O(log n) recursive

Compare target with middle element

Search appropriate half recursively

Return found index or not found

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

Maximum Subarray (D&C)

Find contiguous subarray with maximum sum using divide and conquer

Divide array into two halves

Find max subarray in each half

Find max crossing subarray and compare

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

Closest Pair of Points

Find closest pair among n points in 2D plane efficiently

Divide points by median x-coordinate

Find closest pair in each half

Check pairs across the dividing line

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

Strassen's Matrix Multiplication

Multiply matrices faster than naive O(n³) algorithm

Divide matrices into 4 blocks each

7 recursive multiplications instead of 8

Combine results using addition/subtraction

T(n) = 7T(n/2) + O(n²)

Fast Fourier Transform (FFT)

Compute discrete Fourier transform in O(n log n) time

Split into even and odd indexed elements

Recursively compute FFT of both halves

Combine using complex number arithmetic

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

Karatsuba Multiplication

Multiply large integers faster than grade-school algorithm

Split numbers into high and low halves

3 recursive multiplications instead of 4

Combine using algebraic identity

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

Median of Medians

Find k-th smallest element in linear time with good pivot

Find median of medians as pivot

Recursively search appropriate partition

Return the k-th element

T(n) ≤ T(n/5) + T(7n/10) + O(n)

Master Theorem for Divide & Conquer Recurrences

General Form:

T(n) = a·T(n/b) + f(n)

where a ≥ 1, b > 1, and f(n) is asymptotically positive

Case 1

Condition:

f(n) = O(n^(log_b(a) - ε)) for some ε > 0

Result:

T(n) = Θ(n^(log_b(a)))

Example:

T(n) = 2T(n/2) + O(1) → T(n) = Θ(n)

Intuition:

Work is dominated by leaves of recursion tree

Case 2

Condition:

f(n) = Θ(n^(log_b(a)) × log^k(n)) for some k ≥ 0

Result:

T(n) = Θ(n^(log_b(a)) × log^(k+1)(n))

Example:

T(n) = 2T(n/2) + O(n) → T(n) = Θ(n log n)

Intuition:

Work is balanced between levels

Case 3

Condition:

f(n) = Ω(n^(log_b(a) + ε)) and regularity condition

Result:

T(n) = Θ(f(n))

Example:

T(n) = 2T(n/2) + O(n²) → T(n) = Θ(n²)

Intuition:

Work is dominated by root of recursion tree

Common Divide & Conquer Patterns

✅ When to Use Divide & Conquer

Problem has Optimal Substructure

Optimal solution contains optimal solutions to subproblems

Subproblems are Independent

No overlapping subproblems (unlike DP)

Divide Step is Efficient

Can split problem quickly into roughly equal parts

Combine Step is Feasible

Can efficiently merge subproblem solutions

⚠️ Common Pitfalls

Unbalanced Partitions

Poor pivot choice in quicksort → O(n²) worst case

Expensive Combine Step

If combining is too costly, D&C may not help

Overlapping Subproblems

Should use DP instead of D&C for efficiency

Stack Overflow

Deep recursion may exceed stack limits

Complexity Analysis Examples

Algorithm	Recurrence	Master Theorem Case	Time Complexity
Binary Search	T(n) = T(n/2) + O(1)	Case 1	O(log n)
Merge Sort	T(n) = 2T(n/2) + O(n)	Case 2	O(n log n)
Strassen	T(n) = 7T(n/2) + O(n²)	Case 1	O(n^2.807)
Karatsuba	T(n) = 3T(n/2) + O(n)	Case 1	O(n^1.585)
Max Subarray	T(n) = 2T(n/2) + O(n)	Case 2	O(n log n)

Master Divide & Conquer

Visualize recursive algorithms and understand how they break down problems

D&C Visualizer Start with Merge Sort

Back to Greedy Algorithms Back to Algorithms Overview