Divide-and-conquer algorithm

An algorithmic strategy that divides a problem into smaller subproblems, solves them recursively, and combines their results. Its efficiency often depends on how the subproblems shrink and how much work combination requires.

Recursion: A computational process in which a function or procedure invokes itself on smaller or simpler inputs. Each recursive call solves a smaller subproblem until a base case is reached.
Merge sort: A sorting algorithm that recursively sorts two halves of an array and merges the sorted halves. It exemplifies balanced splitting followed by a linear-time merge.
Brute-force search: A method that tests candidates systematically without using a more specialized structure to reduce the search. It contrasts with reducing the problem through recursive subproblems.
Induction (mathematics): A proof method that establishes a base case and then proves each case from a smaller case. Its structure mirrors the base cases and recursive steps used to justify algorithms.
Parallel algorithm: An algorithm designed to perform multiple computations simultaneously on parallel processing resources. Independent subproblems can often be solved concurrently.
Recurrence relation: An equation that defines a sequence using values at smaller indices. It expresses an algorithm’s running time in terms of the work on its subproblems.
Quicksort: A sorting algorithm that partitions elements around a pivot and recursively sorts the resulting regions. Its partition step creates subproblems whose balance controls performance.
Dynamic programming: An algorithmic method that stores and reuses solutions to overlapping subproblems. Unlike typical divide-and-conquer, it avoids repeatedly solving shared subproblems.
Problem reduction: The transformation of one problem into another to use the latter’s solution or properties. A recursive split reduces the original instance to instances of simpler size.
Work-span model: A model of parallel computation that measures total operations and the longest chain of dependent operations. It distinguishes total recursive work from the depth that limits parallel speedup.

Linked from 8 pages

Akra–Bazzi methodNarrower topic: The method analyzes the running-time recurrences produced by this strategy.