Algorithm Complexity Reference
Time and space costs for all 92 translated learning pages
Complexity describes how resource use grows with the input. Use this table for comparison, then open a learning page to see what each operation actually means in motion.
92 learning pages
| Topic | Time | Space | Notes |
|---|---|---|---|
| Quick Sort | Average O(n log n) | O(log n) | In-place; worst case O(n^2) with consistently poor pivots. |
| Bubble Sort | O(n^2) | O(1) | Stable and in-place, but quadratic even when this basic version is already sorted. |
| Merge Sort | O(n log n) | O(n) | Stable with predictable time; the array implementation needs auxiliary storage. |
| Heap Sort | O(n log n) | O(1) | In-place with a worst-case O(n log n) bound, but not stable. |
| Counting Sort | O(n+k) | O(k) | Excellent for a compact integer range k; unsuitable when the range is very sparse. |
| Binary Search | O(log n) | O(1) | Requires sorted data and discards half of the candidate range per probe. |
| Lower and Upper Bound | O(log n) | O(1) | Two boundary searches locate an equal range without a special found branch. |
| Fenwick Tree | O(log n) | O(n) | Both point updates and prefix queries follow a lowbit chain. |
| Dijkstra's Shortest Path | O((V+E) log V) | O(V) | Heap-based implementation for graphs with non-negative edge weights. |
| Kruskal's Minimum Spanning Tree | O(E log E) | O(V+E) | Edge sorting dominates; disjoint-set operations are nearly constant amortized. |
| Prim's Minimum Spanning Tree | O(E log V) | O(V+E) | A binary heap gives the sparse-graph bound; a dense implementation can use O(V^2). |
| Bellman-Ford Shortest Paths | O(VE) | O(V) | Supports negative edges; one additional relaxation round detects a reachable negative cycle. |
| Topological Sort | O(V+E) | O(V) | Every vertex and edge is processed once; leftover vertices reveal a directed cycle. |
| 0/1 Knapsack | O(nW) | O(nW) | Pseudo-polynomial in capacity W; space can be reduced to O(W). |
| Edit Distance | O(mn) | O(mn) | The full table supports reconstruction; distance alone can be computed with O(n) space. |
| Longest Common Subsequence | O(mn) | O(mn) | Keeping the table makes the backward reconstruction path explicit. |
| Longest Increasing Subsequence | O(n^2) | O(n) | This DP exposes predecessors; a patience-sorting variant reaches O(n log n). |
| N-Queens | O(N!) | O(N) | Conflict checks prune the search, while recursion stores at most one choice per column. |
| Subsets | O(n*2^n) | O(n*2^n) | There are 2^n outputs, and materializing each subset copies up to n values. |
| Maze Solving with DFS | O(RC) | O(RC) | Each open cell is visited at most once; recursion and visited state can cover the grid. |
| KMP String Matching | O(n+m) | O(m) | The text pointer never moves backward; preprocessing builds the LPS table. |
| Rabin-Karp String Matching | Average O(n+m) | O(1) | Character verification prevents collision errors; adversarial collisions can cause O(nm) time. |
| Manacher's Longest Palindromic Substring | O(n) | O(n) | Mirror reuse ensures expansion work advances the right boundary only linearly overall. |
| Sieve of Eratosthenes | O(N log log N) | O(N) | Starting at p^2 avoids work already performed by smaller prime factors. |
| Euclidean Algorithm | O(log min(a,b)) | O(1) | Each remainder strictly reduces the pair until the second value reaches zero. |
| Convex Hull | O(n log n) | O(n) | Andrew's monotone chain is dominated by sorting the points. |
| Closest Pair of Points | O(n log n) | O(n) | Presorting and a y-ordered merge strip keep each recursion level linear. |
| Array | Access O(1); insert/delete O(n) | O(n) | Appending to a doubling dynamic array is amortized O(1). |
| Linked List | Access O(n); known-node update O(1) | O(n) | Finding an insertion position still requires traversal unless its node is already known. |
| Stack | Push/pop O(1) amortized | O(n) | A linked stack makes push and pop worst-case O(1); an array stack is usually more compact. |
| Queue and Deque | End operations O(1) | O(n) | A circular array or linked representation avoids shifting the remaining values. |
| Binary Search Tree | Average O(log n); worst O(n) | O(n) | Self-balancing variants guarantee logarithmic height while preserving the BST order. |
| Binary Heap | Peek O(1); insert/extract O(log n) | O(n) | Bottom-up heap construction takes O(n), despite each individual insertion costing O(log n). |
| Hash Table | Expected O(1); worst O(n) | O(n) | A suitable hash function and controlled load factor keep expected chains or probe runs short. |
| Graph | Traversal O(V+E) | O(V+E) | Adjacency lists store sparse graphs compactly; matrices trade O(V^2) space for direct edge tests. |
| Trie | Insert/search O(L) | O(total characters) | Runtime depends on key length L rather than the number of stored words, at a potentially high pointer cost. |
| Disjoint Set Union | Amortized O(alpha(n)) | O(n) | Path compression with union by size or rank is effectively constant time in practice. |
| LRU Cache | Get/put O(1) expected | O(capacity) | The hash table locates nodes while the linked list maintains recency without linear scans. |
| Skip List | Expected O(log n); worst O(n) | Expected O(n) | Random promotion gives logarithmic expected height without tree rotations. |
| Segment Tree | Query/update O(log n) | O(n) | Any associative aggregate can replace sum, and lazy propagation supports range updates. |
| B+ Tree | Search/update O(log_B n) | O(n) | A large branching factor minimizes storage-page reads, while linked leaves make ranges sequential. |
| Bloom Filter | Add/query O(k) | O(m) bits | Standard Bloom filters allow false positives but never false negatives for inserted items. |
| Cocktail Shaker Sort | O(n^2) | O(1) | Stable and in-place; bidirectional passes help some inputs but do not change the quadratic bound. |
| Bitonic Sort | O(n log^2 n) | O(1) auxiliary | The data-independent network suits parallel hardware and normally expects a power-of-two length. |
| Selection Sort | O(n^2) | O(1) | It performs only O(n) swaps but is generally unstable and always makes quadratic comparisons. |
| Insertion Sort | Average/worst O(n^2); best O(n) | O(1) | Stable, adaptive, and effective for small or nearly sorted inputs. |
| Binary Insertion Sort | O(n log n) comparisons; O(n^2) moves | O(1) | Binary search reduces comparisons, but contiguous insertion still requires shifting the suffix. |
| Shell Sort | Gap-dependent; common worst O(n^2) | O(1) | In-place and often faster than insertion sort on medium arrays, but not stable. |
| Top-Down Merge Sort | O(n log n) | O(n) | Stable with predictable work; recursion adds O(log n) stack frames beside the merge buffer. |
| Three-Way Quick Sort | Average O(n log n); worst O(n^2) | Average O(log n) | Three-way partitioning is especially effective when many input values are equal. |
| Dual-Pivot Quick Sort | Average O(n log n); worst O(n^2) | Average O(log n) | Good partitions reduce recursion depth and can improve cache behavior, but the worst case remains quadratic. |
| Radix Sort | O(d(n+k)) | O(n+k) | Avoids comparisons when keys have d bounded digits over radix k; every digit pass must be stable. |
| Bucket Sort | Average O(n+k); worst O(n^2) | O(n+k) | Near-linear behavior assumes values distribute reasonably evenly across k buckets. |
| Floyd-Warshall | O(V^3) | O(V^2) | Handles negative edges but not negative cycles; the matrix is practical for dense, moderate graphs. |
| Strongly Connected Components | O(V+E) | O(V) | Each vertex enters and leaves the Tarjan stack once, and every directed edge is inspected once. |
| 2-SAT | O(V+E) | O(V+E) | A formula is impossible exactly when a variable and its negation share one strongly connected component. |
| Maximum Flow | O(EF) for integer Ford-Fulkerson | O(V+E) | The bound depends on maximum flow F; Edmonds-Karp or Dinic gives stronger path-selection guarantees. |
| Bipartite Matching | O(VE) | O(V) | The DFS-based Hungarian method finds maximum cardinality matching; weighted assignment needs a different variant. |
| Lowest Common Ancestor | Build O(V log V); query O(log V) | O(V log V) | Binary lifting answers many static-tree ancestor and distance queries efficiently. |
| Eulerian Path | O(V+E) | O(V+E) | Connectivity and odd-degree conditions determine whether an undirected Eulerian trail exists. |
| Unbounded Knapsack | O(nW) | O(nW) | A one-dimensional table uses O(W) space when capacities iterate upward for reusable items. |
| Coin Change | O(nA) | O(A) | The amount A defines the pseudo-polynomial state space; unreachable states remain infinite. |
| Stone Merging | O(n^3) | O(n^2) | Each interval considers all split points; prefix sums make its merge cost O(1). |
| Traveling Salesperson DP | O(n^2 2^n) | O(n 2^n) | Held-Karp is exponential but far smaller than checking all n! tours. |
| Tree Dynamic Programming | O(n) | O(n) | Each edge contributes once to a constant number of states; recursion depth follows tree height. |
| Digit DP | O(d × states × radix) | O(d × states) | Memoization collapses all prefixes that share position, constraint state, and tightness. |
| Rerooting DP | O(n) | O(n) | A local reroot transition turns one rooted result into answers for every possible root. |
| Permutations | O(n × n!) | O(n) | There are n! outputs, and writing each arrangement requires O(n) work. |
| Combination Sum | Exponential in target depth | O(target/min candidate) | Output size dominates, while sorted candidates permit early pruning and canonical ordering. |
| Number of Islands | O(RC) | O(RC) | Every grid cell is visited at most once; iterative traversal can replace recursion. |
| Word Search | O(RC × 4^L) | O(L) | Character checks and no-revisit rules prune the worst-case branching for word length L. |
| Sudoku Solver | Worst O(9^m) | O(m) | Constraint checks and good cell ordering drastically reduce the search below the m-empty-cell bound. |
| A* Search | Worst O((V+E) log V) | O(V) | An admissible consistent heuristic preserves optimality and often explores far fewer states than Dijkstra. |
| Boyer-Moore String Matching | Often sublinear; worst O(nm) | O(m+alphabet) | Large safe shifts make it excellent in practice, while preprocessing depends on the chosen heuristics. |
| Suffix Array | O(n log^2 n) | O(n) | Comparison sorting in each doubling round gives this bound; radix ranking can reach O(n log n). |
| LCP Array | O(n) | O(n) | The reused prefix length decreases by at most one per text position, bounding total comparisons. |
| Aho-Corasick Automaton | O(P+n+z) | O(P × alphabet) dense | P is total pattern length and z is output count; sparse transitions reduce memory. |
| Z Function | O(n) | O(n) | Comparisons that extend the Z-box move its right boundary forward, so total extension work is linear. |
| Linear Sieve | O(N) | O(N) | The break rule prevents a composite from being produced by more than its smallest prime factor. |
| Binary Exponentiation | O(log exponent) | O(1) | Modular reduction can be applied after every multiplication without changing the recurrence. |
| Extended Euclidean Algorithm | O(log min(a,b)) | O(1) iterative | Bezout coefficients provide modular inverses whenever the gcd is one. |
| Chinese Remainder Theorem | O(k log M) | O(k) | The direct form assumes pairwise coprime moduli; generalized merging checks gcd compatibility. |
| Euler's Totient Function | O(sqrt n) trial division | O(1) | Each distinct prime factor p multiplies the running result by (1 - 1/p). |
| Miller-Rabin Primality Test | O(k log^3 n) | O(1) | A fixed witness set is deterministic for bounded machine integers; random witnesses give tiny error probability. |
| Fast Fourier Transform | O(n log n) | O(n) | Pointwise multiplication between forward and inverse transforms yields fast polynomial convolution. |
| Pollard's Rho Factorization | Expected O(n^1/4) | O(1) | Random restarts handle unlucky cycles; primality testing separates terminal factors. |
| Rotating Calipers | O(n) after the hull | O(1) | Monotone orientation changes ensure each pointer makes at most one full circuit. |
| Line Segment Intersection | O(1) | O(1) | Robust implementations must handle zero orientation and numeric precision explicitly. |
| Bentley-Ottmann Sweep Line | O((n+k) log n) | O(n+k) | The output-sensitive bound reports k intersections without comparing every pair of n segments. |
| Search in a Rotated Sorted Array | O(log n) | O(1) | The logarithmic guarantee assumes distinct values; duplicates can obscure which half is sorted. |
| Binary Search on the Answer | O(check × log range) | O(1) beyond the check | Correctness depends on a monotone predicate and a precisely defined first-true or last-true boundary. |
| Ternary Search | O(log range) | O(1) | The objective must be unimodal; continuous search stops at a chosen precision. |