📅 July 2026
📊 67 algorithms
🗂 9 domains
Algorithm Complexity: The Big Table
One long, scrollable table with the time and space complexity of every major algorithm used across this site's simulations — sorting, graphs, spatial/collision structures, computational geometry, numerical integration, machine learning, procedural generation, cryptography and rendering. For a narrower, filterable sorting/searching/graph/spatial/numerical/physics cheat sheet with best/average/worst columns, see the Algorithm Complexity Reference.
N input size
V, E vertices, edges
K key range / distinct values
d dimensions / depth
k iterations / clusters / nearby items
| Algorithm | Time | Space | Notes |
|---|---|---|---|
| Sorting & Selection | |||
| Timsort | O(N log N) | O(N) | Hybrid merge+insertion sort. Stable. Default in V8 (Array.prototype.sort) and Python. |
| Introsort | O(N log N) | O(log N) | Quicksort that falls back to heapsort on deep recursion. Used by C++ std::sort. |
| Counting Sort | O(N + K) | O(K) | K = range of integer keys. Not comparison-based; no lower bound of O(N log N) applies. |
| Radix Sort | O(d·(N + K)) | O(N + K) | d = number of digits/passes. Fast for fixed-width integer or string keys. |
| Quickselect | O(N) avg / O(N²) worst | O(1) | Finds the k-th smallest element without fully sorting. Basis of median-of-medians (guaranteed O(N)). |
| Graphs & Pathfinding | |||
| BFS | O(V + E) | O(V) | Shortest path in unweighted graphs. FIFO queue. |
| DFS | O(V + E) | O(V) | Cycle detection, topological sort, connected components. |
| Dijkstra (binary heap) | O((V+E) log V) | O(V) | Non-negative weights only. Fibonacci heap improves to O(E + V log V). |
| Bellman-Ford | O(V·E) | O(V) | Handles negative weights; detects negative cycles. |
| Floyd-Warshall | O(V³) | O(V²) | All-pairs shortest paths via dynamic programming. |
| A* Search | O(E) worst | O(V) | Dijkstra + admissible heuristic h(n). Explores far fewer nodes in practice. |
| Topological Sort (Kahn’s) | O(V + E) | O(V) | Orders a DAG so every edge points forward. Used for build/dependency graphs. |
| Union-Find (path compression) | O(α(N)) amortized | O(N) | α = inverse Ackermann, effectively constant. Kruskal’s MST relies on it. |
| Kruskal’s MST | O(E log E) | O(V) | Sort edges, add via Union-Find while avoiding cycles. |
| Prim’s MST (binary heap) | O(E log V) | O(V) | Grows one tree from a start vertex. Better than Kruskal on dense graphs. |
| PageRank (power iteration) | O(k·E) | O(V) | k = iterations to converge. Each iteration is one sparse matrix-vector multiply. |
| Minimax + Alpha-Beta | O(b^(d/2)) best / O(b^d) worst | O(d) | b = branching factor, d = depth. Good move ordering approaches the best case. |
| Spatial Structures & Collision | |||
| k-d Tree (build) | O(N log N) | O(N) | Query (nearest neighbour): O(log N) average, O(N) worst case in high dimensions. |
| Octree / Quadtree (build) | O(N log N) | O(N) | Depth typically capped; rebuild or incrementally update per frame for moving bodies. |
| Barnes-Hut (N-body) | O(N log N) | O(N) | θ parameter trades accuracy for speed vs. naive O(N²) all-pairs. |
| Fast Multipole Method | O(N) | O(N) | Asymptotically faster than Barnes-Hut for very large N; harder to implement. |
| Spatial Hash Grid | O(1) avg | O(N) | Insert/query per cell in constant average time. Cell size should match interaction radius. |
| BVH Build (SAH) | O(N log N) | O(N) | Surface Area Heuristic gives near-optimal ray-tracing traversal cost. |
| Sweep and Prune (broad phase) | O(N log N) | O(N) | Sort AABBs along one axis; sweep for overlapping intervals. |
| GJK (narrow phase) | O(1) amortized | O(1) | Iterative simplex refinement; a handful of iterations typically suffice per pair. |
| EPA (penetration depth) | O(k) iterations | O(k) | Runs after GJK detects overlap; expands the polytope until convergence. |
| Computational Geometry | |||
| Convex Hull (Graham scan) | O(N log N) | O(N) | Sort by angle, then sweep with a stack. |
| Convex Hull (QuickHull) | O(N log N) avg / O(N²) worst | O(N) | Divide-and-conquer, analogous to quicksort. |
| Delaunay Triangulation | O(N log N) | O(N) | Divide-and-conquer or incremental with edge flips. Dual of the Voronoi diagram. |
| Voronoi Diagram (Fortune’s sweep) | O(N log N) | O(N) | Sweep-line algorithm using a beach line of parabolic arcs. |
| Marching Cubes | O(N) | O(N) | N = voxel cells. One lookup-table case per cell (256 configurations). |
| Marching Squares | O(N) | O(N) | 2D analogue of Marching Cubes (16 configurations). Used for terrain contours, metaballs. |
| Numerical Integration & Physics | |||
| Explicit Euler | O(N) / step | O(N) | 1st-order accurate. Energy drifts over time — avoid for orbital mechanics. |
| Semi-implicit (Symplectic) Euler | O(N) / step | O(N) | Updates velocity first, then position. Bounded energy error — the default for games. |
| Velocity Verlet | O(N) / step | O(N) | 2nd-order accurate, time-reversible, excellent energy conservation. |
| Runge-Kutta 4 (RK4) | O(4N) / step | O(N) | 4 derivative evaluations per step for 4th-order accuracy. Not symplectic. |
| Position-Based Dynamics (PBD) | O(N · iter) | O(N) | Iterative constraint projection. Stable but iteration-count-dependent stiffness. |
| XPBD | O(N · iter) | O(N) | Compliance-based extension of PBD — stiffness becomes independent of iteration count. |
| SPH (per step) | O(N) with spatial hash | O(N) | O(N²) naive all-pairs neighbour search; spatial hashing brings it down to near-linear. |
| Lattice Boltzmann (LBM, per step) | O(N) | O(N) | N = lattice cells (D2Q9/D3Q19). Collision + streaming, embarrassingly parallel on GPU. |
| Finite Difference (per step) | O(N) | O(N) | N = grid points. Stencil update; stability governed by CFL condition. |
| Conjugate Gradient | O(N·√κ) iterations | O(N) | κ = condition number of the (symmetric positive-definite) system matrix. |
| Fast Fourier Transform (FFT) | O(N log N) | O(N) | Underpins spectral methods, audio analysis, and ocean/water wave synthesis (FFT water). |
| Machine Learning & AI | |||
| k-Means Clustering | O(N·k·i·d) | O(N + k) | N points, k clusters, i iterations, d dimensions. Converges to a local optimum only. |
| k-Nearest Neighbours (brute-force) | O(N·d) | O(N) | Per query. A k-d tree or ball tree reduces this to roughly O(log N) in low dimensions. |
| PCA (via SVD) | O(min(N²d, Nd²)) | O(Nd) | N samples, d dimensions. Randomized SVD gives a much faster approximation for large d. |
| Gradient Descent (per step) | O(N·d) | O(d) | N samples, d parameters. Mini-batch variants trade N for batch size B per step. |
| Backpropagation (per layer) | O(N) | O(N) | N = number of weights in that layer; one forward + one backward pass per training step. |
| Genetic Algorithm (per generation) | O(pop · fitness cost) | O(pop) | pop = population size. Total cost scales with generations × population × fitness evaluation. |
| MCMC / Metropolis-Hastings (per sample) | O(1) / step | O(1) | Constant work per proposed step, but many steps are needed to reach the target distribution (mixing time). |
| Procedural Generation & Noise | |||
| Perlin Noise (3D, per sample) | O(1) | O(1) | 8 gradient lookups + trilinear interpolation per query, independent of grid size. |
| Simplex Noise (3D, per sample) | O(1) | O(1) | Fewer corner evaluations than Perlin in higher dimensions (4 vs 8 in 3D); no directional artefacts. |
| Worley / Cellular Noise | O(k) | O(1) | k = feature points checked in neighbouring cells (typically 9-27). Basis of cellular/cracked-earth textures. |
| L-System (expand n iterations) | O(len₀ · r^n) | O(len₀ · r^n) | r = average rule expansion factor. String length grows exponentially with iteration depth n. |
| Diamond-Square (terrain) | O(N²) | O(N²) | N×N heightmap grid. Classic fractal terrain generator, simple but visible grid artefacts. |
| Hydraulic Erosion (droplet-based) | O(D · steps) | O(N) | D = number of simulated droplets; each walks "steps" cells depositing/eroding sediment. |
| Strings, Compression & Cryptography | |||
| Knuth-Morris-Pratt (KMP) | O(N + M) | O(M) | N = text length, M = pattern length. No backtracking in the text thanks to the failure function. |
| Levenshtein / Edit Distance | O(N·M) | O(min(N,M)) | Classic DP; space can be reduced to one row with rolling arrays. |
| Huffman Coding (build) | O(N log N) | O(N) | N = distinct symbols. Optimal prefix-free code for known symbol frequencies. |
| Run-Length Encoding | O(N) | O(N) worst | Trivial single pass; only effective on data with long repeated runs. |
| SHA-256 | O(N) | O(1) | N = message length in 512-bit blocks. Fixed-size internal state, one-way (non-invertible). |
| AES-256 (encrypt one block) | O(1) | O(1) | Fixed 14 rounds per 128-bit block regardless of message size. |
| RSA Modular Exponentiation | O(log e) | O(1) | Square-and-multiply; e is the public exponent. Security relies on factoring being hard, not this algorithm. |
| Rendering | |||
| Ray-Sphere / Ray-Triangle Test | O(1) | O(1) | Closed-form quadratic (sphere) or Möller-Trumbore (triangle) solve per test. |
| Ray Marching (SDF) | O(steps) / pixel | O(1) | Sphere-tracing steps bounded by max iterations and max distance; cost scales with scene SDF complexity. |
| Path Tracing (per pixel) | O(bounces · samples) | O(1) / pixel | Monte Carlo integration of the rendering equation; noise decreases as O(1/√samples). |
| Rasterization (per triangle) | O(pixels covered) | O(1) / pixel | Screen-space edge functions; GPU hardware parallelizes across all covered pixels/fragments. |
No algorithms match your filter.
Complexities are typical/average-case figures used for engineering decisions, not formal worst-case proofs in every row — see each algorithm's linked tutorial or the Algorithms Glossary for definitions and derivations.