Divide and Conquer Algorithms Cheat Sheet

Updated 2026-05-19

Next Topic: Dynamic Programming Cheat Sheet

🧠Study flashcards on this topic74 cards · spaced repetition→

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, 74 flashcards. 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

Quick IndexSubscribe to unlock

A jump-to index of every table row in this cheat sheet.

Mind MapSubscribe to unlock

An interactive map of every table and concept in this topic.

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.
Independent subproblems	Merge sort left and right halves share no elements	• D&C requires subproblems to be independent (no shared state) • overlapping subproblems → use dynamic programming instead
Recursion depth	Merge sort depth $= \log_2 n$ levels	• Depth $= \log_b n$ • determines stack space usage $O(\log_b n)$ and total number of recursive calls $a^{\log_b n} = n^{\log_b a}$.
Decrease-and-conquer	Binary search: $T(n) = T(n/2) + O(1)$	• Special case with $a = 1$: only one subproblem per level • reduces rather than divides
Cache-oblivious property	Merge sort on arrays achieves good cache behavior without explicit tile sizes	D&C recursion naturally produces cache-friendly access patterns at all cache levels without tuning.

Table 2: Recurrence Relations — Common Forms

Every divide-and-conquer algorithm produces a recurrence of the form $T(n) = aT(n/b) + f(n)$. This table lists the canonical recurrences for the most important algorithms — memorizing these allows instant recognition and classification by Master Theorem case.

Technique	Example	Description
Merge sort recurrence	$T(n) = 2T(n/2) + \Theta(n)$ → $\Theta(n \log n)$	• $a=2, b=2$ • merge step costs $\Theta(n)$ • Master Theorem Case 2 ($c_{crit} = \log_2 2 = 1 = c$).

The rest of this section is part of the full cheat sheet

Table 3: Solving Recurrences — Substitution Method

The substitution method proves a recurrence's complexity by guessing a closed-form bound and verifying it by induction. It requires a good initial guess (often suggested by Master Theorem or recursion tree), then tight constant selection via the induction step.

Technique	Example	Description
Guess the form	Guess $T(n) = O(n \log n)$ for $T(n) = 2T(n/2) + n$	First step: hypothesize the asymptotic form based on Master Theorem or recursion tree analysis.

The rest of this section is part of the full cheat sheet

Table 4: Solving Recurrences — Recursion Tree Method

The recursion tree method visualizes a recurrence as a tree where each node represents the non-recursive work at one recursive call. Summing work across all levels gives the total cost and reveals which part of the tree dominates — forming the intuition behind the three Master Theorem cases.

Technique	Example	Description
Tree structure	Merge sort: root costs $n$; level 1 has 2 nodes each costing $n/2$; level 2 has 4 nodes each costing $n/4$	• Each level $d$ has $a^d$ nodes • each node at depth $d$ costs $f(n/b^d)$ • total cost at depth $d$ is $a^d \cdot f(n/b^d)$.

The rest of this section is part of the full cheat sheet

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.
Independent subproblems	Merge sort left and right halves share no elements	• D&C requires subproblems to be independent (no shared state) • overlapping subproblems → use dynamic programming instead
Recursion depth	Merge sort depth $= \log_2 n$ levels	• Depth $= \log_b n$ • determines stack space usage $O(\log_b n)$ and total number of recursive calls $a^{\log_b n} = n^{\log_b a}$.
Decrease-and-conquer	Binary search: $T(n) = T(n/2) + O(1)$	• Special case with $a = 1$: only one subproblem per level • reduces rather than divides
Cache-oblivious property	Merge sort on arrays achieves good cache behavior without explicit tile sizes	D&C recursion naturally produces cache-friendly access patterns at all cache levels without tuning.

Table 2: Recurrence Relations — Common Forms

Technique	Example	Description
Merge sort recurrence	$T(n) = 2T(n/2) + \Theta(n)$ → $\Theta(n \log n)$	• $a=2, b=2$ • merge step costs $\Theta(n)$ • Master Theorem Case 2 ($c_{crit} = \log_2 2 = 1 = c$).

Table 3: Solving Recurrences — Substitution Method

Technique	Example	Description
Guess the form	Guess $T(n) = O(n \log n)$ for $T(n) = 2T(n/2) + n$	First step: hypothesize the asymptotic form based on Master Theorem or recursion tree analysis.

Table 4: Solving Recurrences — Recursion Tree Method

Technique	Example	Description
Tree structure	Merge sort: root costs $n$; level 1 has 2 nodes each costing $n/2$; level 2 has 4 nodes each costing $n/4$	• Each level $d$ has $a^d$ nodes • each node at depth $d$ costs $f(n/b^d)$ • total cost at depth $d$ is $a^d \cdot f(n/b^d)$.