Method
divide and conquer
Articles
SRT
Algorithm
External sorting
A file larger than memory: sorted runs, then a multiway merge; replacement selection gives runs of length 2M.
O(n log n) comparisons; 2n·(1 + ⌈log_k R⌉) line reads and writes
1 problem
GRA
Algorithm
Centroid decomposition
Splitting a tree by centroids: log₂ n levels, and the nearest marked vertex in O(log n) after every mark.
O(log n) per mark and per question
1 problem
DP
Technique
Knuth and divide-and-conquer optimisations
45 thousand towns on a map by population class: 3.5 million evaluations instead of five billion, because the best split is monotone.
O(k · n log n)
2 problems
PAR
Technique
Divide and conquer
Cut, solve the parts the same way, glue; what it costs follows from the levels of the recursion tree and the master theorem.
T(n) = a·T(n/b) + f(n)
2 problems
PAR
Algorithm
Closest pair of points
The two nearest of n points in n log n: a cut, a strip 2d wide and seven neighbours; with a grid, n on average.
O(n log n)
2 problems
NUM
Algorithm
Fast exponentiation
aⁿ in O(log n) multiplications: squares over the bits of the exponent.
O(log n) multiplications
2 problems
NUM
Algorithm
Big integers
Numbers longer than a machine word: digits in base 10⁹ or 2³⁰, carries, column methods and expensive printing.
addition O(n), column multiplication and division O(n²), printing in decimal O(n²) or O(M(n) log n)
2 problems
NUM
Algorithm
Fast Fourier transform
The discrete Fourier transform in O(N log N): spectra, convolutions, multiplying polynomials and big numbers.
O(N log N)
2 problems
TEC
Technique
Complexity from measurements
The growth of running time from measurements: the slope, the ratio test, exponentials, and where measurement lies.
O(B) per attempt
1 problem
Problems
Often together
classic 6 contests 5 interviews 4 sorting 3 geodata 2 recursion 2 security 2 numerical precision 2 in production 2 external memory 1 tree 1 graph 1