Divide and Conquer Algorithms Cheat Sheet

Updated 2026-05-19

Next Topic: Dynamic Programming Cheat Sheet

Divide and conquer is a fundamental algorithm design paradigm that recursively breaks a problem into independent subproblems, solves each, and combines their solutions. It underpins the most efficient known algorithms for sorting, searching, matrix multiplication, polynomial multiplication, and geometric problems — and its performance is analyzed through recurrence relations solved by the Master Theorem, recursion tree method, or substitution method.

What This Cheat Sheet Covers

This topic spans 13 focused tables and 78 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Core Paradigm and Design PrinciplesTable 2: Recurrence Relations — Common FormsTable 3: Solving Recurrences — Substitution MethodTable 4: Solving Recurrences — Recursion Tree MethodTable 5: Master Theorem — Three CasesTable 6: Akra–Bazzi MethodTable 7: Merge Sort — Algorithm and VariantsTable 8: Quicksort — Partitioning SchemesTable 9: Quicksort — Pivot Selection and Hybrid StrategiesTable 10: Binary Search and VariantsTable 11: Fast Multiplication AlgorithmsTable 12: Geometric Divide and ConquerTable 13: Other Classic Divide and Conquer Algorithms

Table 1: Core Paradigm and Design Principles

The three-phase structure (divide → conquer → combine) defines every divide-and-conquer algorithm. Understanding these phases and their cost contributions is the foundation for analyzing any D&C algorithm via its recurrence relation.

Technique	Example	Description
Divide step	Merge sort: split array at midpoint $mid = \lfloor (lo + hi)/2 \rfloor$	Splits the problem into $a$ subproblems each of size $n/b$ ; ideally $O(1)$ or $O(n)$ work.
Conquer step	Recursively sort left half and right half	Solves each subproblem recursively; base case handles $n \leq$ threshold directly.
Combine step	Merge two sorted halves in $O(n)$	Merges subproblem solutions; this cost appears as $f(n)$ in the recurrence $T(n) = aT(n/b) + f(n)$ .
Base case	`if n <= 1: return` (sort trivially sorted list)	Smallest subproblem solved directly; must be reached to prevent infinite recursion.
Recurrence relation	$T(n) = aT(n/b) + f(n)$	Mathematical model capturing total work: $a$ = subproblems, $b$ = size reduction factor, $f(n)$ = non-recursive work.

Table 1: Core Paradigm and Design Principles

Technique	Example	Description
Divide step	Merge sort: split array at midpoint $mid = \lfloor (lo + hi)/2 \rfloor$	Splits the problem into $a$ subproblems each of size $n/b$ ; ideally $O(1)$ or $O(n)$ work.
Conquer step	Recursively sort left half and right half	Solves each subproblem recursively; base case handles $n \leq$ threshold directly.
Combine step	Merge two sorted halves in $O(n)$	Merges subproblem solutions; this cost appears as $f(n)$ in the recurrence $T(n) = aT(n/b) + f(n)$ .
Base case	`if n <= 1: return` (sort trivially sorted list)	Smallest subproblem solved directly; must be reached to prevent infinite recursion.
Recurrence relation	$T(n) = aT(n/b) + f(n)$	Mathematical model capturing total work: $a$ = subproblems, $b$ = size reduction factor, $f(n)$ = non-recursive work.