classic

SRT Algorithm Binary search Finds the “no → yes” boundary in ordered data in log₂ n checks. O(log n) 2 problems SRT Technique Binary search on the answer If checking an answer is easier than finding it, and the check is monotone, search for the answer by halving. O(log D · cost of a check) 2 problems SRT Algorithm Exponential search Steps 1, 2, 4, 8, … until you overshoot, then binary search: when the bound is unknown or the answer is near. 2⌊log₂ i⌋ + 1 questions to position i 1 problem 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 SRT Algorithm Counting sort and radix sort Without comparisons: count the keys or split them into digits, O(n + k) and O(d·n) instead of n log n. O(n + k) and O(d·(n + b)) 2 problems DS Data structure Dynamic array An array that grows by itself: access by index in O(1), appending to the end in O(1) amortised. O(1) amortised per append 2 problems DS Data structure Cuckoo hashing Two nests per key, a lookup in at most two probes; insertion evicts tenants. Works up to a load of 1/2, with buckets up to 98 %. lookup at most d probes in the worst case; insertion O(1) on average below the threshold 1 problem DS Data structure Binary heap The minimum at hand, insertion and extraction in O(log n): the tree in an array that event calendars live on. O(log n) 2 problems DS Data structure Binary search tree Smaller to the left, larger to the right: search, order and the k-th element in the tree's height, from log n to n. O(h): from O(log n) to O(n) 2 problems DS Data structure AVL tree A search tree where the branch heights at a node differ by at most 1: height up to ~1.44·log₂ n. O(log n) for search, insertion and deletion 2 problems DS Data structure B-tree A tree with hundreds of keys in a page-sized node: a search among a billion keys reads five pages. O(log n) comparisons, O(log_B n) page reads 2 problems DS Data structure Disjoint set union Merge two sets and tell whether elements are in the same one, in almost O(1): a forest of parent links and two tricks. O(α(n)) 2 problems DS Data structure Fenwick tree Prefix sums with updates in O(log n) in a single array: blocks as long as the lowest one bit of the index. O(log n) per prefix sum and per update 2 problems GRA Algorithm Breadth-first search Walks a graph in layers and finds paths with the fewest edges in O(V + E). O(V + E) 2 problems GRA Algorithm Depth-first search Goes deep, marks each vertex's entry and exit and finds cycles by them in O(V + E). O(V + E) 2 problems GRA Algorithm Bridges and articulation points Streets and crossroads without which a graph falls apart: one depth-first search with the numbers tin and low, O(V + E). O(V + E) 2 problems GRA Algorithm Dijkstra's algorithm Shortest paths from one vertex in a weighted graph without negative edges. O((V + E) log V) 3 problems GRA Algorithm A* Dijkstra with a hint of how far is left: the wave stretches towards the goal, and the path stays shortest. O((V + E) log V) 2 problems GRA Algorithm The Bellman–Ford algorithm Shortest paths with negative edges and finding a negative cycle: V rounds over all edges. O(V · E) 2 problems GRA Algorithm Floyd–Warshall algorithm Shortest paths between all pairs of vertices in O(n³): dynamic programming over allowed transfers. O(n³) 2 problems GRA Algorithm Dinic's algorithm Maximum flow in phases: a layered network, a blocking flow, pointers; O(V²E), and O(E√V) in unit networks. O(V² E) 2 problems GRA Algorithm Bipartite matching The largest number of pairs in a bipartite graph: Kuhn, Hopcroft–Karp, the theorems of König and Hall. O(E √V) 2 problems GRA Algorithm Eulerian path Go along every edge exactly once: the odd-vertex rule and Hierholzer's algorithm in O(E). O(V + E) 3 problems STR Algorithm The Aho–Corasick algorithm Every occurrence of thousands of words in one pass: a trie of the words plus failure links, as in the prefix function. O(n + Σ|wᵢ| + z) 1 problem STR Algorithm Boyer–Moore Compares from right to left and skips letters: on long patterns it reads only a small part of the text. O(n + m) 2 problems STR Algorithm Edit distance The fewest insertions, deletions and substitutions between two strings: an m × n table and the alignment read from it. O(m · n) 2 problems DP Technique Dynamic programming Reduce a problem to subproblems, solve each once and keep the answers in a table. states × transitions 2 problems DP Technique Bitmask DP The state is a subset written in the bits of a number: an exact travelling salesman, assignments, tilings by profile. O(2ⁿ · n²) for the travelling salesman 2 problems PAR Technique Backtracking Build a solution step by step, check at once and retreat from dead ends: sudoku, queens, colourings. O(bᵈ) in the worst case 2 problems PAR Technique Branch and bound 38 airports with a direct flight from each to each: a colouring bound shrinks the search from a million nodes to 242. exponential in the worst case 1 problem 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 Euclid's algorithm The greatest common divisor of two numbers in O(log n) divisions with remainder. O(log min(a, b)) 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 Chinese remainder theorem A number from its residues modulo several moduli: Garner's algorithm and exact computation over many primes. O(k²) operations on machine numbers 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 GEO Algorithm Convex hull The smallest convex polygon containing all the points, in O(n log n). O(n log n) 2 problems GEO Algorithm Delaunay triangulation and Voronoi diagram Zones of the nearest point and triangles with empty circles: two sides of one structure. O(n log n) on average 2 problems NUM~ Algorithm Bisection and Newton's method A root of an equation: halving an interval is reliable, Newton's tangents are fast. bisection: log₂((b − a)/ε) steps; Newton: about log₂ of the number of digits 2 problems ML Algorithm k-means Splits points into k groups so that points sit close to the centre of their group. O(n · k · d) per step 2 problems ML Algorithm DBSCAN Gathers dense regions of points of any shape into clusters and marks lone points as noise. O(n·Q + Σ|N(p)|) 2 problems ML Algorithm Decision tree Answers with a chain of questions “feature ≤ threshold?”; each question is chosen so that uncertainty falls the most. O(h · F · n log n) to build; O(h) to answer 2 problems TEC Technique Big O How work grows with the data: O, Ω and Θ, rules for estimating code, and where asymptotics mislead. estimated from the program text 1 problem TEC Technique Amortized analysis A bound on a whole sequence of operations, not on each one: by a sum, by coins and by a potential, and where it does not help. a bound on a sequence 2 problems