Divide and Conquer
Divide and Conquer is an algorithmic paradigm that recursively breaks a problem into two or more smaller subproblems of the same type until they become simple enough to solve directly, then combines their solutions to solve the original problem. The three phases are: Divide (split the problem), Conquer (solve subproblems recursively), and Combine (merge results). Famous examples include Merge Sort, Quick Sort, Binary Search, and the Fast Fourier Transform.
Key Formula
T(n) = a * T(n/b) + f(n) [Master Theorem recurrence]
LaTeX: T(n) = aT\!\left(\frac{n}{b}\right) + f(n)
| Symbol | Meaning | Unit |
|---|---|---|
| T(n) | Time complexity for input of size n | operations |
| a | Number of subproblems | dimensionless |
| b | Factor by which input size is reduced | dimensionless |
| f(n) | Cost of dividing and combining | operations |
Worked Example
Problem
Apply Merge Sort (a divide-and-conquer algorithm) to sort the array [38, 27, 43, 3, 9, 82, 10].
Solution
Step 1 (Divide): Split into [38, 27, 43] and [3, 9, 82, 10]. Step 2 (Divide further): [38],[27,43] and [3,9],[82,10]. Step 3 (Divide to base): [38],[27],[43],[3],[9],[82],[10]. Step 4 (Conquer): Merge pairs: [27,38],[3,9],[43] stays, [10,82]. Step 5 (Combine): Merge [27,38] and [43] → [27,38,43]. Merge [3,9] and [10,82] → [3,9,10,82]. Step 6 (Final merge): Merge [27,38,43] and [3,9,10,82] → [3,9,10,27,38,43,82].
Answer
Sorted array: [3, 9, 10, 27, 38, 43, 82]. Time complexity: O(n log n). Space: O(n) for merge.
Common Divide-and-Conquer Algorithms
| Algorithm | Divide | Conquer | Combine | Time Complexity |
|---|---|---|---|---|
| Merge Sort | Split array in half | Sort each half | Merge two sorted halves | O(n log n) |
| Quick Sort | Partition around pivot | Sort partitions | No combine needed | O(n log n) avg |
| Binary Search | Halve search space | Search correct half | Return result | O(log n) |
| Strassen Matrix Multiply | Split matrices | Multiply sub-matrices | Add sub-products | O(n^2.81) |
| Karatsuba Multiplication | Split digits | Multiply parts | Combine with additions | O(n^1.585) |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Recursion
Recursion is a programming and mathematical technique in which a function calls itself with a smaller or simpler version of the original problem, progressing toward one or more base cases that terminate the chain of calls. Every recursive solution requires a base case (stopping condition) and a recursive case (self-referential reduction). Recursion is fundamental to tree traversal, divide-and-conquer algorithms, backtracking, and functional programming.
Dynamic Programming
Dynamic Programming (DP) is an algorithmic paradigm that solves complex problems by breaking them into overlapping subproblems, solving each subproblem only once, and storing results to avoid redundant computation (memoization or tabulation). It applies when a problem exhibits two key properties: optimal substructure (optimal solution contains optimal solutions to subproblems) and overlapping subproblems. DP is used in sequence alignment, shortest-path problems, knapsack optimization, and compiler design.
Backtracking
Backtracking is an algorithmic technique for solving constraint satisfaction and combinatorial problems by incrementally building a solution and abandoning (backtracking from) a partial solution as soon as it is determined to violate the problem constraints, then trying the next possibility. It is essentially a depth-first search through the space of candidate solutions, pruning branches that cannot lead to a valid solution. Backtracking is used to solve N-Queens, Sudoku, crossword puzzles, subset-sum, and graph coloring problems.
From Latin "divide et impera" (divide and rule), a political and military strategy attributed to Julius Caesar and later Philip II of Macedon. Applied to algorithms in the 1960s by computer scientists such as John von Neumann (Merge Sort, 1945) and Tony Hoare (Quick Sort, 1959).