Divide and Conquer
Subject: Computer and Technology noun /dɪˈvaɪd ənd ˈkɑːŋ.kər/ 1 definition
- algorithm-design
- recursive-algorithms
- computational-complexity
- computer-science
-
Definition (noun)
Entry #59 · UpdatedDivide and Conquer is an algorithm design paradigm that solves a complex problem through three recursive stages: dividing the input into smaller subproblems of the same structure, conquering each subproblem recursively until reaching a base case small enough to solve directly, and combining the subproblem results into the final answer. By shrinking the input geometrically at each level, this approach frequently lowers asymptotic complexity—such as reducing quadratic work to O(n log n) or O(log n)—and produces independent subproblems well suited to parallel execution. Unlike dynamic programming, which stores overlapping subproblem results to avoid redundant computation, divide and conquer operates on disjoint subproblems whose solutions do not depend on one another.
Common Forms
Balanced Binary Splitting: Divides an input into two nearly equal halves at every recursive step and merges their outputs, as seen in merge sort and the Fast Fourier Transform (FFT).
Pivot-Based Partitioning: Reorders elements around a selected pivot during the divide phase so each partition can be solved independently without a merge step, powering quicksort and quickselect.
Single-Branch Reduction: Discards half or a fixed fraction of the search space at each step so only one smaller subproblem requires recursion, enabling O(log n) algorithms such as binary search and exponentiation by squaring.
Fork-Join Parallelism: Dispatches independent recursive subproblems across multiple threads or processor cores before synchronizing and combining their results, accelerating workloads in multi-core task schedulers.
Example
To sort a 10-million-record transaction log by timestamp, a merge sort routine recursively divides the array into halves until each subarray holds a single trivially sorted record. It then merges adjacent sorted subarrays back up the recursion tree by comparing their leading timestamps, assembling the complete ordered log in O(n log n) time.