Algorithms
Algorithms grouped by topic. More algorithms are added step by step.
Graphs
↑ All topicsGraph traversal
- Articulation pointsFind the nodes whose removal splits the graph, with one DFS and each node's low value (the earliest discovery time reachable from its subtree).Time:
O(V + E) - Breadth-first search (BFS)Explore the graph layer by layer from the source, finding the fewest edges to every node with a queue.Time:
O(V + E) - Chromatic polynomialFind the number of proper colourings of a graph with k colours as a polynomial in k, by deletion and contraction: P(G) = P(G − e) − P(G / e). Exponential in the number of edges.Time:
O(2^m · (n + m)) - Connected componentsGroup the nodes of an undirected graph by whether they can reach each other: each unlabelled node starts a new search.Time:
O(V + E) - Depth-first search (DFS)Go as deep as possible along one path from the source, and when stuck, back up and try another way.Time:
O(V + E) - Euler circuit (Hierholzer)Find a closed walk that uses every edge exactly once; wherever it gets stuck, it splices a side loop into the walk.Time:
O(V + E) - Greedy graph colouringTake the nodes by degree (Welsh–Powell) and give each one the smallest colour none of its neighbours has.Time:
O(V log V + E) - Graph isomorphism (backtracking)Search for a mapping from one graph's vertices to the other's that keeps every edge and non-edge: vertex by vertex, with backtracking and pruning by degree. Up to n! cases in the worst case.Time:
O(n! · n) in the worst case - Hamiltonian cycle (backtracking)Search for a cycle that visits every node exactly once; grow the path node by node and back up at dead ends.Time:
O(V!) - Strongly connected componentsSplit a directed graph into groups where every node can reach every other node of its group, with two DFS passes (Kosaraju's algorithm).Time:
O(V + E) - Topological sortLine up the nodes of a directed acyclic graph so that every edge goes from an earlier node to a later one, like taking courses in prerequisite order.Time:
O(V + E) - Transitive closure (Warshall)Decide for every pair of nodes whether the first can reach the second; like Floyd–Warshall, but with “or” and “and” instead of min and plus.Time:
O(V³) - Disjoint sets (union–find)Read the edges one by one and merge the sets of their two ends; with union by rank and path compression each operation is almost O(1).Time:
O(E · α(V)) - Approximate vertex coverFor every edge not yet covered, take both of its ends; the answer is at most twice the optimum.Time:
O(V + E)
Shortest paths
- Bellman–Ford algorithmShortest paths from a source even with negative edges: relax every edge V − 1 times, and detect a negative cycle too.Time:
O(V · E) - Critical path (AOE network)In an activity network, compute each event's earliest and latest time and find the activities that cannot be delayed at all.Time:
O(V + E) - Shortest paths in a DAGIn a directed acyclic graph, relax the nodes once in topological order; it works with negative edges and is faster than Dijkstra.Time:
O(V + E) - Difference constraintsTurn a system of inequalities x_j − x_i ≤ b into a graph and solve it with Bellman–Ford: the shortest-path distances are a solution, and a negative cycle means there is none.Time:
O(n · m) - Dijkstra's algorithmShortest distances from one source node to every node of a graph with non-negative weights, using a priority queue.Time:
O((V + E) log V) - Floyd–Warshall algorithmShortest paths between every pair of nodes by dynamic programming: the nodes are allowed as middle stops one at a time.Time:
O(V³) - Johnson's algorithmAll-pairs shortest paths with negative edges: Bellman–Ford makes the weights non-negative, then Dijkstra runs from every node.Time:
O(V · E log V) - All-pairs shortest paths by repeated squaringFind the shortest paths between all pairs by “multiplying” the weight matrix by itself, with min in place of + and + in place of ·; repeated squaring needs only log n products. Θ(n³ log n).Time:
Θ(n³ log n)
Minimum spanning trees
- Approximate travelling salesmanBuild a minimum spanning tree and visit the nodes in its preorder; with the triangle inequality, the tour is at most twice the optimum.Time:
O(V²) - Borůvka's (Sollin's) algorithmIn each round, every component takes its lightest outgoing edge; the number of components at least halves each round.Time:
O(E log V) - Kruskal's algorithmGo through the edges from lightest to heaviest and add every edge that does not close a cycle to the minimum spanning tree.Time:
O(E log E) - Prim's algorithmGrow the minimum spanning tree from one node: each time, add the lightest edge that joins a new node to the tree.Time:
O((V + E) log V)
Network flow and matching
- Maximum bipartite matchingMatch each left node through an augmenting path; if its neighbour is taken, move that neighbour's partner somewhere else.Time:
O(V · E) - Gale–Shapley (stable matching)Men propose in order of preference and women always keep the best offer so far; the result is a stable matching: no two people both prefer each other to their partners. At most n² proposals.Time:
O(n²) - Hopcroft–Karp algorithmMaximum bipartite matching in phases: each phase layers the graph with BFS, then finds several short, separate augmenting paths with DFS.Time:
O(E √V) - The Hungarian algorithm (assignment)Give each worker a different job at the least total cost: build the matching on the zeros of the reduced cost matrix only, and make a new zero whenever it gets stuck.Time:
O(n⁴) here (O(n³) with more bookkeeping) - Maximum flow (Edmonds–Karp)While the residual network has a path from the source to the last node, find the shortest one with BFS and push flow along it.Time:
O(V · E²)
Sorting
↑ All topicsComparison sorts
- Bubble sortCompare neighbouring pairs and swap them when needed; in each pass the largest item bubbles up to the end.Time:
O(n²), O(n) if already sorted - Heap sortTurn the array into a max-heap, then repeatedly move the largest item from the root to the end of the array.Time:
O(n log n) - Hoare partitionTwo pointers move towards each other from both ends and swap misplaced items, until the array splits into a ≤ pivot part and a ≥ pivot part.Time:
O(n) - Insertion sortLike sorting playing cards in your hand: take each item and put it in its place in the sorted part on the left.Time:
O(n²) - k-way mergeMerge k sorted runs at once with a min-heap: each time take the smallest of the runs' front items. The basis of external sorting.Time:
O(n log k) - Merge sortSplit the array in half, sort each half recursively, then merge the two sorted halves.Time:
O(n log n) - Priority queue with a heapInsert into a max-heap by sifting the new item up, and extract the maximum by sifting the item placed at the root down; both O(log n).Time:
O(log n) per operation - Quick sortTake the last item as the pivot, move smaller items to its left and larger ones to its right, then sort each side recursively.Time:
O(n log n) on average, O(n²) at worst - Selection sortIn each round, find the smallest item of the unsorted part and move it to the front of that part.Time:
O(n²) - Shell sortInsertion sort on items gap positions apart, with gaps shrinking down to 1; far-away items get near their place early.Time:
O(n²) with gaps n/2, n/4, …; better with other gap sequences - Table sortInstead of moving large records around, sort a table of indices, then move each record just once, following the cycles of the permutation.Time:
O(n²) comparisons, O(n) record moves
Non-comparison sorts
- Bucket sortSplit the range into n equal buckets, drop each number into its bucket, sort the buckets separately and lay them end to end.Time:
O(n) on average for evenly spread input, O(n²) at worst - Counting sortNo comparisons: count how often each value occurs and compute each item's place in the output directly from prefix sums.Time:
O(n + k) - Radix sortSort the numbers digit by digit, starting from the ones digit, with a stable counting sort; after the last digit the whole array is sorted.Time:
O(d·(n + 10)) for d digits
Searching
↑ All topicsArray search
- Binary searchIn a sorted array, compare the middle item of the range with the value you want and throw away half of the range each time.Time:
O(log n) - Fisher–Yates shuffleFrom the end to the start, swap each position with a random position in the part not yet shuffled; every permutation is equally likely.Time:
O(n) - The hiring problemCandidates arrive one by one and anyone better than everyone before is hired; how many hires do we make?Time:
n interviews; about ln n hires on average for a random order - Interpolation searchLike binary search, but instead of the middle it guesses where target should be from its value, the way you look up a word in a dictionary.Time:
O(log log n) for evenly spread data, O(n) at worst - Linear searchCompare the items one by one from the start with the value you want, until it is found or the array ends.Time:
O(n) - Maximum subarray (Kadane)Find the contiguous range with the largest sum in one pass: whenever the running sum turns negative, drop it and start over.Time:
O(n) - Selection by median of mediansFind the k-th smallest item in linear time even in the worst case: the pivot is the median of the medians of groups of five.Time:
O(n) - Minimum and maximum togetherTake the items in pairs: the smaller of a pair is compared only with the minimum and the larger only with the maximum; 3 comparisons per 2 items.Time:
about 3n/2 comparisons - Next permutationBuild the next permutation in dictionary order in place: find the first dip from the end, one swap and one reversal.Time:
O(n) - Quickselect (k-th smallest)Partition like quick sort, but continue only on the side that holds the k-th item; linear time on average.Time:
O(n) on average, O(n²) at worst
Hashing
- Bloom filterTest set membership with a bit array and a few hash functions: “definitely not” or “maybe”, using very little memory.Time:
O(k) per key for k hash functions - Extendible hashingA hash table that grows by splitting just one bucket, doubling its directory only when needed, instead of rebuilding everything; any key is found in one or two accesses.Time:
O(1) expected per operation - Hash table with chainingEach slot of the table holds a list, and keys that hash to the same slot line up in that list; a collision never runs out of room.Time:
O(1 + n/m) on average per operation - Hash table with double hashingLike linear probing, but a second hash function picks the step size from the key itself, so keys that collide follow different paths.Time:
O(1) per insert on average when the table is not too full - Hash table with linear probingEach key goes to slot key mod m; if that is taken, it tries the following slots one by one until it finds an empty one.Time:
O(1) per insert on average when the table is not too full
Strings
↑ All topicsString matching
- String matching with a finite automatonBuild a finite automaton for the pattern whose state is how much of the pattern has matched so far; then read the text with one table look-up per character.Time:
O(n) to match, after O(m³·|Σ|) to build δ here - Knuth–Morris–Pratt (KMP)String matching in O(n + m): no text character is read twice; after a mismatch, the prefix function says how far the pattern moves.Time:
O(n + m) - The KMP prefix functionFor every prefix of the pattern, find the longest proper prefix that is also its suffix; with this table KMP knows how far to move after a mismatch.Time:
O(m) (amortized) - Naive string matchingPut the pattern under every possible position of the text and compare character by character; simple, but O((n − m + 1)·m) in the worst case.Time:
O((n − m + 1)·m) - Rabin–KarpTreat each window of the text as a number mod q, update it in O(1) with a rolling hash, and compare characters only when the remainders agree.Time:
O(n + m) expected, O((n − m + 1)·m) worst - Suffix array and LCPSort all suffixes of a string, and for each pair of neighbouring suffixes find the longest common prefix with Kasai's method in O(n).Time:
O(n² log n) to sort here (O(n log n) with doubling), O(n) for LCP
Expressions and stacks
- Matching bracketsCheck with a stack that parentheses, square brackets and braces open and close properly: each closing one must match the last one opened.Time:
O(n) - Infix to postfixTurn an ordinary expression into postfix (reverse Polish) notation with a stack; precedence and parentheses are kept by the order operators leave the stack.Time:
O(n) - Evaluating postfixEvaluate a postfix expression with a stack in one pass: a number is pushed, and each operator pops the top two numbers and pushes the result.Time:
O(n)
Automata
- DFA minimizationMerge the equivalent states of a deterministic machine: start from accepting versus non-accepting and split the blocks until no more splits happen.Time:
O(n²) here (O(n log n) with Hopcroft's method) - Finite-state machine (sequence recognizer)A three-state machine reads a binary string bit by bit and decides whether its value is a multiple of 3, without ever storing the number.Time:
O(n) - Regular grammar to automatonBuild the automaton for a regular grammar (rules like A → aB): each nonterminal is a state and each rule an edge; then try a string on it.Time:
O(rules + |w| · edges) - NFA to DFA (subset construction)Turn a nondeterministic machine into an equivalent deterministic one: each DFA state is the set of NFA states the nondeterministic machine could be in at once.Time:
O(2ⁿ) states in the worst case
String trees
- Digital search treeLike a binary search tree, but at depth d bit d of the key picks the way instead of comparing keys; the height never exceeds the number of bits.Time:
O(number of bits) per operation - Longest prefix match (IP routing)Put the routing table's prefixes into a binary trie and follow the address bit by bit; the last prefix passed on the way is the longest match.Time:
O(address length) - Suffix treePut every suffix of a string into one compressed tree whose edges are pieces of the text; afterwards any pattern can be found in O(pattern length).Time:
O(n²) here (O(n) with Ukkonen's method) - TrieStore words letter by letter in a tree where shared prefixes share one path; a search depends only on the word's length, not on how many words there are.Time:
O(word length) per insert or search
Coding
- Hamming (7,4) codeAdd 3 parity bits to 4 data bits so that if one bit is flipped on the way, the syndrome tells exactly where, and it can be fixed.Time:
O(1) - Huffman codingBuild a binary code where frequent symbols get shorter codes: each time join the two lightest trees under one root.Time:
O(n + k log k) for k symbols
Trees
↑ All topicsTree traversal
- Copying and comparing treesTwo short recursive algorithms: copy a binary tree node by node, and check whether two trees have the same shape and the same keys; both O(n).Time:
O(n) - Iterative inorder and preorderTraverse a binary tree with an explicit stack instead of recursion: the same orders, but the stack that recursion hides is in plain view.Time:
Θ(n) - Level-order traversalVisit the tree's nodes level by level, top to bottom and left to right, with a queue; BFS on a tree.Time:
O(n) - Threaded binary treePoint each empty right link of the tree at the node's inorder successor (a thread); then an inorder walk needs no stack and no recursion.Time:
Θ(n) - Tree isomorphismCheck whether two rooted trees turn into each other by swapping children: give every subtree a canonical name, bottom up, and compare the two roots' names.Time:
O(n²) with strings (O(n) with integer names) - Tree traversalsPreorder, inorder and postorder traversal of a binary tree with recursion; inorder on a search tree gives the keys sorted.Time:
O(n)
Binary search trees
- AVL tree deletionDelete the key as in an ordinary search tree, then fix every unbalanced node with rotations on the way back to the root; unlike insertion, rotations may be needed at several levels. O(log n).Time:
O(log n) - AVL tree (insert)A binary search tree that, after each insert, keeps the heights of every node's two subtrees within 1 of each other using one or two rotations.Time:
O(log n) per insert - B-treeA balanced search tree whose nodes hold several keys and children, with every leaf at the same depth; full nodes are split on the way down. Built for disks: height O(log_t n).Time:
O(t · log_t n) per insert - Binary search tree: insert and deleteA new key walks down from the root by comparisons to an empty spot; deleting has three cases: a leaf, one child, and two children (using the successor).Time:
O(h) per operation (h = height) - Binary search tree queriesMinimum, maximum, search and successor in a binary search tree; each walks just one path down from the root.Time:
O(h) - Splitting and joining binary search treesSplit a search tree at a key k into two trees (keys below and above k), then join the two again; both O(h). A split followed by a join deletes k.Time:
O(h) - Interval tree searchA search tree of intervals in which every node stores the largest high end in its subtree; with it, an interval overlapping a query is found in O(h).Time:
O(h) - Order-statistic tree (OS-Select, OS-Rank)A search tree in which every node stores the size of its subtree; with it, the i-th smallest key and the rank of any key are found in O(h).Time:
O(h) - Red–black tree (insert)A balanced binary search tree with coloured nodes; after each insert, rotations and colour flips keep the height at most 2 log n.Time:
O(log n) per insert - Splay treeA search tree with no balance information: every key that is accessed is brought to the root by rotations, two levels at a time. Each operation costs O(log n) amortized.Time:
O(log n) amortized
Data structures
↑ All topicsLinked lists
- The available-space listKeep a pool's free nodes in a linked list: getting a node takes one off its front and returning one puts it back in front; both O(1).Time:
O(1) per operation - Concatenating two linked listsAttach the second list to the end of the first: walk to the first list's last node and change one pointer; no node is copied.Time:
O(length of the first list) - Equivalence classesFrom a list of pairs i ≡ j, find the equivalence classes: put each pair on both objects' lists, then gather each class with a stack; O(n + m).Time:
O(n + m) - Sorted linked list (insert, search, delete)Insert items one by one into their places in a sorted linked list, then search for one and delete it; only pointers change, no item moves.Time:
O(n) per operation - Reversing a linked listTurn every link of the list around one by one with three pointers, prev, cur and nxt; in one pass with no extra memory.Time:
O(n)
Stacks and queues
- Circular queueA queue in a fixed-size array that wraps around to the start when it reaches the end; each enqueue and dequeue is O(1) and no space goes to waste.Time:
O(1) per operation - Two stacks in one arrayTwo stacks grow toward each other from the two ends of one array; neither is full until the whole array is.Time:
O(1) per operation
Amortized analysis
- Binary counter (amortized analysis)Increment a binary counter eight times; one increment can flip many bits, but the average is below 2.Time:
O(k) for one increment of k bits, O(1) amortized - Dynamic table (amortized analysis)An array that doubles whenever it fills up; the copies are sometimes expensive, but the amortized cost per insert is at most 3.Time:
O(1) amortized per insert - Stack with MULTIPOP (amortized analysis)One MULTIPOP may remove many items and be expensive, but each item is popped at most once; so n operations cost at most 2n in total.Time:
O(1) amortized per operation
Online algorithms
- Caching policies (LRU, FIFO, furthest-in-future)Three caches of the same size serve one request sequence and their misses are compared; furthest-in-future is optimal but has to know the future.Time:
O(n·k) (furthest-in-future: O(n²·k) here) - Move-to-frontA self-organizing list: each requested item moves to the front, so popular items stay near it; its cost is at most 4 times the best offline method's.Time:
O(position) per request
Heaps and priority queues
- Binomial heapA forest of binomial trees of distinct degrees, like the binary digits of n; merging two heaps works like adding two binary numbers and takes O(log n).Time:
O(log n) per union, insert or extract-min - Fibonacci heapA heap that puts off work as long as it can: insert and decrease-key are O(1) amortized, and only extract-min tidies up the trees (O(log n) amortized). Cascading cuts keep the trees bushy.Time:
O(1) amortized insert and decrease-key; O(log n) amortized extract-min - Leftist heapA heap that merges two heaps in O(log n): all the work happens along the short right spine, and wherever the left side gets shorter the two children swap. Insert and delete-min are merges too.Time:
O(log n) per merge, insert or delete-min - Min-max heapA heap whose even levels are ordered like a min-heap and odd levels like a max-heap; both the minimum and the maximum are found in O(1) and removed in O(log n) (a double-ended priority queue).Time:
O(log n) per insert or delete; O(1) to find the min or max - Winner tree (and loser tree) for k-way mergingMerge k sorted runs with a tournament tree: the root is the smallest head, and after each output only the matches on one leaf-to-root path are replayed; O(log k) per item.Time:
O(n log k) for n items in k runs
Dynamic programming
↑ All topicsClassic problems
- Approximate subset sum (FPTAS)Approximate the largest subset sum not above t; trimming sums that are close together keeps the list short, and the answer is within a factor (1 + ε) of the optimum.Time:
O(n² ln t / ε) - Longest common subsequence (LCS)Find the longest subsequence that appears in both strings (in the same order, not necessarily side by side) with a dynamic-programming table.Time:
O(m·n) - Matrix-chain multiplicationFind the best parenthesization for multiplying several matrices by dynamic programming; the order can change the number of scalar products many times over.Time:
O(n³) - Optimal binary search treeUse dynamic programming to build the search tree with the least expected cost, given how often each key is searched; for every range of keys it tries every root. O(n³).Time:
Θ(n³) (O(n²) with Knuth's speed-up) - Rod cuttingCut a rod of length n so that selling the pieces earns the most; the answer for each length is built from the answers for shorter lengths.Time:
O(n²)
Greedy algorithms
↑ All topicsClassic problems
- Activity selectionPick the most activities that do not overlap: always the one that finishes first, if it does not clash with the last one chosen.Time:
O(n log n) - Fractional knapsackFill a knapsack of capacity W with the most value when any fraction of an item may be taken: items in order of value per unit of weight.Time:
O(n log n) - Greedy set coverEach time, take the set covering the most elements not yet covered; at most H(max |S|) ≈ ln n times the fewest sets possible.Time:
O(|X| · |F| · min(|X|, |F|)) - Optimal merge of runsMerge sorted runs of different sizes two at a time; merging the two smallest each time gives the least total cost.Time:
O(n log n)
Numbers
↑ All topicsNumber theory
- Base conversionConvert a number to another base by repeated division; the remainders, last to first, are the digits.Time:
O(log_b n) - Chinese remainder theoremFind the number with given remainders modulo several pairwise coprime moduli; each term matters in only one modulus.Time:
O(k log N) - The division algorithmFind the quotient q and remainder r with a = q·b + r and 0 ≤ r < b, by subtracting or adding b again and again.Time:
O(|a| / b) - Euclid's algorithm (GCD)Find the greatest common divisor of two numbers by repeated division: gcd(a, b) = gcd(b, a mod b).Time:
O(log min(a, b)) - Extended Euclidean algorithmBesides the gcd, find coefficients s and t with s·a + t·b = gcd(a, b); the basis of modular inverses and RSA.Time:
O(log min(a, b)) - Linear congruences (modular inverse)Find every x with a·x ≡ b (mod n), using the extended Euclidean algorithm. The modular inverse is the case b = 1.Time:
O(log n + d) - Linear congruential generatorMake random-looking numbers with x ← (a·x + c) mod m; the sequence always repeats eventually, and the choice of a, c and m sets the period.Time:
O(count) - Miller–Rabin primality testDecide whether a number is composite or prime with modular powers and square roots of 1, even for the Carmichael numbers that fool Fermat's test.Time:
O(k log³ n) - Modular exponentiation (repeated squaring)Compute aᵇ mod n with about log b multiplications: square the base again and again, and multiply it in for every 1 bit of b.Time:
O(log b) - Pollard's rhoFind a factor of a composite n with the sequence x² + 1: a slow and a fast pointer run along it until the gcd of their difference with n gives a factor.Time:
about O(n^¼) steps - Primality test (trial division)Divide n by 2, 3, … up to √n; if none of them divides n, n is prime.Time:
O(√n) - RSA encryptionBuild the public key (e, n) and the private key (d, n) from two primes, then encrypt a message with modular powers and decrypt it again.Time:
O(log e + log d) multiplications
Counting and combinatorics
- Counting with Burnside's lemma and Pólya's method (necklaces)Count the n-bead necklaces in k colours when turning (and flipping) a necklace does not change it: the average number of colourings each symmetry fixes, where a symmetry with c cycles fixes k^c colourings.Time:
O(n log n) - Catalan numbersCompute the Catalan numbers by dynamic programming; they count binary trees, balanced parenthesizations and paths below the diagonal.Time:
O(n²) - Counting binary trees (recursive)Count the binary trees with n nodes straight from the recursive definition; the call tree shows why the dynamic-programming version (Catalan numbers) is better.Time:
O(3ⁿ) - DerangementsCount the permutations where no item stays in its place; their share of all permutations approaches 1/e.Time:
O(n) - Gray codeOrder all n-bit strings so that any two neighbours differ in exactly one bit, by reflecting the previous list.Time:
O(n · 2ⁿ) - Integer partitionsCount the ways to write n as a sum of positive integers (order does not matter), by dynamic programming that allows one part size at a time.Time:
O(n²) - Magic squareFill an n×n grid (n odd) with 1 to n² so every row, column and diagonal has the same sum, by the Siamese method: one up, one right.Time:
O(n²) - Orthogonal Latin squaresFor a prime n, build two n × n Latin squares with the formula (a·i + j) mod n that are orthogonal: laid on top of each other, every ordered pair of symbols appears exactly once. Used in experimental design.Time:
O(n²) to build (O(n⁴) for this simple check) - Rook polynomialCount the ways to place k non-attacking rooks on any board, for every k, with the rule r(C) = x·r(C_s) + r(C_e) on a chosen cell s. It is used to count permutations with forbidden positions (by inclusion–exclusion).Time:
O(2^c) for c cells
Recursion and backtracking
- Recursive factorialn! = n · (n−1)!, the simplest example of recursion: calls pile up on the stack down to the base case, then the multiplications happen on the way back.Time:
O(n) - Recursive FibonacciCompute F(n) = F(n−1) + F(n−2) straight from the definition; the call tree shows why this is exponential.Time:
O(φⁿ) ≈ O(1.618ⁿ) - Generating all combinationsBuild all k-element subsets of 1 to n in lexicographic order; each next item is larger than the last, so no subset comes twice.Time:
O(k · C(n, k)) - Generating all permutationsBuild all n! permutations of 1 to n in lexicographic order: add an unused item, recurse, then take it back.Time:
O(n · n!) - Instant InsanityStack four coloured cubes so that every side of the column shows all four colours: each cube's opposite faces become edges of a graph on the colours, and we look for two disjoint subgraphs in which each colour appears twice.Time:
O(3^n · 2^n) in the worst case - Maze solving (backtracking)Find a way from the top-left to the bottom-right corner: go forward, and at every dead end mark it and back up.Time:
O(rows · cols) - The n-queens problemPlace n queens on an n×n board so that no two attack each other; row by row, backing up at dead ends.Time:
O(n!) worst case - Tower of HanoiMove n disks from peg A to peg C, one at a time and never a larger disk on a smaller one; exactly 2ⁿ − 1 moves.Time:
O(2ⁿ) - Tromino tilingCover a 2^k × 2^k board with one missing cell using L-shaped three-cell tiles: split the board in four, put one tromino in the middle so every quarter has exactly one filled cell, and solve each quarter recursively. An induction proof turned into an algorithm.Time:
Θ(4^k) (one step per tromino)
Matrices and polynomials
↑ All topicsMatrix operations
- Fast transpose of a sparse matrixKeep a sparse matrix as (row, column, value) triples and build its transpose without sorting, by counting each column's terms, in O(columns + terms).Time:
O(cols + terms) - Matrix multiplicationMultiply an n×m matrix by an m×p one: each cell of the product is the dot product of a row of A and a column of B.Time:
O(n·m·p) - Sparse matrix multiplicationKeep each row by its non-zero terms only and do only the non-zero products; far fewer than n³ for sparse matrices.Time:
O(rows + the number of non-zero products) - Strassen's matrix multiplicationMultiply n×n matrices by divide and conquer: 7 half-size products instead of 8, with some extra additions; time O(n^2.81).Time:
O(n^log₂7) ≈ O(n^2.81)
Numerical linear algebra
- Least squares (fitting a line)Find the line with the smallest sum of squared vertical distances to the points, by solving the two normal equations, in exact fractions.Time:
O(n) - Solving linear systemsSolve A·x = b by LUP decomposition and two substitutions: L·y = P·b forward, then U·x = y backward; in exact fractions.Time:
O(n³), then O(n²) for each new b - LUP decompositionFactor a square matrix as P·A = L·U (L lower triangular, U upper triangular, P a row permutation) by Gaussian elimination with partial pivoting, in exact fractions.Time:
O(n³) - Matrix inverse (Gauss–Jordan)Turn [A | I] into [I | A⁻¹] by row operations; each column gets a pivot of 1 with zeros above and below it. In exact fractions.Time:
O(n³)
Polynomials
- Fast Fourier transform (FFT)Evaluate a polynomial at the n complex roots of unity by divide and conquer in O(n log n) (and back, with the inverse FFT); the basis of fast polynomial multiplication.Time:
O(n log n) - Polynomial multiplication with the FFTMultiply two polynomials in O(n log n): evaluate both at the roots of unity, multiply the values point by point, and get the coefficients back with the inverse FFT.Time:
O(n log n) - Horner's ruleEvaluate a degree-n polynomial with only n multiplications and n additions, by factoring x out again and again.Time:
O(n) - Polynomial additionAdd two sparse polynomials kept as their non-zero terms only, like the merge in merge sort, in order of exponent.Time:
O(m + n)
Logic and circuits
↑ All topicsPropositional logic
- Karnaugh maps, DNF and CNFFrom the true rows of a truth table, build the canonical disjunctive (DNF) and conjunctive (CNF) forms, then merge neighbouring cells as on a Karnaugh map (the Quine–McCluskey method) to find a simplest sum of products.Time:
O(3^n · n) for the prime implicants - MAX-3-CNF: the randomized 7/8-approximation, derandomizedA random assignment satisfies 7/8 of a 3-CNF formula's clauses on average. Fixing the variables one by one so the conditional expectation never drops gives an assignment certain to satisfy at least 7/8 of them.Time:
O(n · m) - ResolutionFrom two clauses, one containing ℓ and the other ¬ℓ, build a new clause holding the rest of both. Reaching the empty clause shows the clauses are unsatisfiable; proof by contradiction works this way.Time:
exponential in the worst case - Expression trees and satisfiabilityTurn a propositional formula into an expression tree and evaluate it for every assignment with a postorder walk; the formula is satisfiable if some row comes out true. 2^n assignments.Time:
O(2^n · size) - Truth tableFor every assignment of the variables, work out each subformula from the inside out, and finally say whether the formula is always true (a tautology), always false (a contradiction) or sometimes true.Time:
O(2^n · size)
Machine learning
↑ All topicsMachine-learning algorithms
- Gradient descentTo minimize a function, step against its gradient again and again. Here it fits a line to some points (least squares). The step size (the learning rate) decides whether it converges or diverges.Time:
O(n) per step - k-means clusteringSplit points into k clusters: each point joins its nearest centre and each centre moves to the mean of its points, until no point changes cluster. The cost falls every round, but the answer may be only a local optimum.Time:
O(n · k) per round - Multiplicative weights (weighted majority)Take predictions from several “experts” and follow their weighted vote; every expert that is wrong has its weight multiplied by (1 − ε). Our mistakes are at most about twice the best expert's plus O(log n / ε).Time:
O(n) per round