Reference
Algorithm Complexity Reference
Big-O time and space complexity for every algorithm category used in simulations, with practical notes on when each matters at interactive frame rates.
O(1) / O(log N)
O(N)
O(N log N)
O(N²)
O(N³)+ Avoid for N>100 at 60fps
| Algorithm | Category | Time (Average) | Time (Worst) | Space | Notes |
|---|---|---|---|---|---|
| Quicksort | Sorting | O(N log N) | O(N²) | O(log N) | Worst case on sorted input. In-place. Cache-friendly. Standard choice. |
| Merge Sort | Sorting | O(N log N) | O(N log N) | O(N) | Stable. Guaranteed O(N log N). Extra memory = N. |
| Heapsort | Sorting | O(N log N) | O(N log N) | O(1) | In-place but not stable. Poor cache behaviour. |
| Insertion Sort | Sorting | O(N²) | O(N²) | O(1) | Fast for almost-sorted N<50. Stable. Online. |
| Counting Sort | Sorting | O(N+K) | O(N+K) | O(K) | K = range of values. O(N) when K ≈ N. |
| Radix Sort | Sorting | O(d·N) | O(d·N) | O(N+K) | d = digit width. Stable. Used in GPU particle sort. |
| Binary Search | Searching | O(log N) | O(log N) | O(1) | Sorted array required. 1M elements → 20 comparisons. |
| Hash Table Lookup | Searching | O(1) | O(N) | O(N) | Worst case with collisions. Average case amortised O(1). |
| Linear Search | Searching | O(N) | O(N) | O(1) | Cache-friendly. Only choice for unsorted subsets. |
| BFS | Graph | O(V+E) | O(V+E) | O(V) | Shortest path in unweighted graphs. FIFO queue. |
| DFS | Graph | O(V+E) | O(V+E) | O(V) | Stack-based. Used for topological sort, maze generation. |
| Dijkstra (binary heap) | Graph | O((V+E) log V) | O((V+E) log V) | O(V) | Shortest path in non-negative weighted graph. Used in pathfinding. |
| A* Search | Graph | O(E log V) | O(V²) | O(V) | Heuristic-guided Dijkstra. Optimal with admissible heuristic. |
| Bellman-Ford | Graph | O(V·E) | O(V·E) | O(V) | Handles negative edge weights. Detects negative cycles. |
| Floyd-Warshall | Graph | O(V³) | O(V³) | O(V²) | All-pairs shortest paths. Impractical for V>1000. |
| Prim's MST | Graph | O(E log V) | O(E log V) | O(V+E) | Minimum spanning tree. Used for maze generation. |
| KD-Tree build | Spatial | O(N log N) | O(N²) | O(N) | After build, kNN query is O(log N). Degrades in high dims. |
| Quad/Octree build | Spatial | O(N log N) | O(N²) | O(N) | Adaptive subdivision. Used in Barnes-Hut N-body: O(N log N). |
| Spatial Hash lookup | Spatial | O(1) avg | O(N) | O(N) | O(1) amortised. Best for uniform particle distributions (SPH). |
| Uniform Grid | Spatial | O(k) | O(N) | O(W·H) | k = avg particles per cell. Very fast for dense simulations. |
| FFT | Numerical | O(N log N) | O(N log N) | O(N) | Fast Fourier Transform. Replaces O(N²) DFT. GPU FFT in WebGL ocean. |
| Conjugate Gradient | Numerical | O(N√κ) | O(N²) | O(N) | κ = condition number. O(N^1.5) for 2D Laplacian. Iterative solver. |
| Gaussian Elim. (LU) | Numerical | O(N³) | O(N³) | O(N²) | Direct solver. Exact. Only practical for N ≤ 10³ in real-time. |
| Newton's Method | Numerical | O(log 1/ε) | O(N²·iter) | O(1) | Quadratic convergence near root. Jacobian needed for systems. |
| Broad-phase AABB | Physics | O(N log N) | O(N²) | O(N) | Sort-and-sweep. Near O(N) for slowly moving objects. |
| Narrow-phase GJK | Physics | O(1) per pair | O(1) | O(1) | Convex-convex distance computation. Iterative, typically 10–15 iters. |
| SPH (neighbour find) | Physics | O(N·k) | O(N²) | O(N) | k = particles in kernel radius. Spatial hash reduces to O(1) lookup. |
| Spring-lattice | Physics | O(N·springs) | O(N·springs) | O(N) | Springs ≈ 4–8× N for regular lattice. Linear in N. Used for cloth, fracture. |
| N-body O(N²) | Physics | O(N²) | O(N²) | O(N) | Pairwise gravity. GPU-parallel = ~16k particles at 60fps. |
| Barnes-Hut N-body | Physics | O(N log N) | O(N²) | O(N) | Octree + multipole: distant clusters treated as single mass. θ = 0.5–0.9. |
Big-O Quick Reference
O(1)
Constant — independent of input size. Always fast.
Hash table lookup, array index access
O(log N)
Logarithmic — halves problem each step. 1B → 30 steps.
Binary search, balanced BST ops
O(N)
Linear — scales directly with size. Standard scan.
Find max, count, Verlet integration
O(N log N)
Linearithmic — optimal comparison-based sorting lower bound.
Mergesort, FFT, Dijkstra
O(N²)
Quadratic. Fine for N≤10⁴; at 60fps, N≤~3000.
Naive N-body, insertion sort, naive SPH
O(N³)
Cubic. Practical limit N≤~300 per frame.
Gaussian elimination, Floyd-Warshall
O(2^N) / O(N!)
Exponential / factorial. Only tiny N. NP-hard territory.
Subset sum (brute force), naïve TSP