Learning Path Catalog Algorithms Philosophy Get Started

Loading...

Learn DSA

Master Data Structures and Algorithms with interactive theory, visualizations, and hands-on simulations. Build your coding skills with comprehensive learning resources.

Quick Links

Data Structures
Algorithms
About
Contact

Data Structures

Arrays
Linked Lists
Stacks
Queues
Trees
Graphs

Algorithms

Sorting
Searching
Graph Algorithms
Dynamic Programming
Greedy
Divide & Conquer

Interactive Theory

Comprehensive explanations with examples

Visual Learning

Dynamic visualizations and animations

Hands-on Practice

Interactive simulations and exercises

© 2026 Learn DSA. All rights reserved.Made with passion for learning

Privacy Policy Terms of Service Cookie Policy DMCA

Learn DSA is an educational platform designed to help students and professionals master data structures and algorithms. All content is provided for educational purposes only. We are not affiliated with any specific company or institution.

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^2) 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^3) 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^2)

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^2) → T(n) = Θ(n^2)

Intuition:

Work is dominated by root of recursion tree

Back to Dynamic Programming Next: Greedy Algorithms