| Family |
Name |
Year |
Time Complexity |
Space Complexity
|
| Approximate OBST |
Melhorn's Approximation algorithm (Approximate OBST Optimal Binary Search Trees) |
1975 |
$O(n)$ |
$O(n)$
|
| Approximate OBST |
Karpinski (Approximate OBST Optimal Binary Search Trees) |
1996 |
$O(n^{0.6})$ |
$O({1})$
|
| Alphabetic Tree Problem |
Klawe; Mumey (Alphabetic Tree Problem Optimal Binary Search Trees) |
1993 |
$O(n)$ |
$O(n)$
|
| Approximate OBST |
Larmore (Approximate OBST Optimal Binary Search Trees) |
1987 |
$O(n^{1.6})$ |
$O(n)$
|
| k-ANNS |
Hierarchical Navigable Small World (HNSW) (k-ANNS Nearest Neighbor Search) |
2018 |
$O(nlogn)$ |
$O(M)$
|
| k-ANNS |
Locality-sensitive hashing (k-ANNS Nearest Neighbor Search) |
2010 |
$O(nLkt)$ (pre-processing)
$O(L(kt+dnP_2^k))$ (query-time) || $O(nL)$
|
| k-ANNS for a dense 3D map of geometric points |
Projected radial search (k-ANNS for a dense 3D map of geometric points Nearest Neighbor Search) |
2013 |
$O(k)$ |
$O({1})$
|
| k-ANNS |
Compression/Clustering (Vector Quantization) (k-ANNS Nearest Neighbor Search) |
1992 |
Varies by codebook structure |
Varies by codebook structure
|
| Subset Sum |
Pisinger (Subset Sum The Subset-Sum Problem) |
2003 |
$O(nt/logt)$ |
$O(t/logt)$
|
| Subset Sum |
Faaland (Subset Sum The Subset-Sum Problem) |
1973 |
$O(n' t)$ |
$O(t)$
|
| Subset Sum |
Pferschy (Subset Sum The Subset-Sum Problem) |
1999 |
$O(n' t)$ |
$O(t)$
|
| Subset Sum |
Klinz (Subset Sum The Subset-Sum Problem) |
1999 |
$O(σ^{({3}/{2})})$ |
$O(t)$
|
| Subset Sum |
Eppstein (Subset Sum The Subset-Sum Problem) |
1997 |
$\tilde{O}(n max(S))$ |
$O(t logt)$
|
| Subset Sum |
Serang (Subset Sum The Subset-Sum Problem) |
2014 |
$\tilde{O}(n max(S))$ |
$O(t logt)$
|
| Subset Sum |
Serang (Subset Sum The Subset-Sum Problem) |
2015 |
$\tilde{O}(n max(S))$ |
$O(t logt)$
|
| Subset Sum |
Lokshtanov (Subset Sum The Subset-Sum Problem) |
2010 |
$\tilde{O}(n^{3} t)$ |
$O(n^{2})$
|
| Almost Stable Marriage Problem |
Valentin Polishchuk, and Jukka Suomela (Almost Stable Marriage Problem Stable Matching Problem) |
2008 |
$O({1})$ |
$O({1})$
|
| Motif Search |
Lawrence, Reilly (Motif Search Motif Search) |
1990 |
$O(nm)$ |
$O(nm)$
|
| Motif Search |
Lawrence Gibbs Sampling (Motif Search Motif Search) |
1993 |
$O(nm)$ |
$O(n + m)$
|
| Motif Search |
MotifSampler (Motif Search Motif Search) |
2001 |
$O(nm)$ |
$O(n + m)$
|
| Texture Synthesis |
tree-structured vector quantization Wei-Levoy (Texture Synthesis Texture Synthesis) |
2000 |
$O(n^{2} log n)$ |
$O(nd)$
|
| Texture Synthesis |
Spatial GAN-Based; Urs Bergmann, Nikolay Jetchev, Roland Vollgraf (Texture Synthesis Texture Synthesis) |
2017 |
$O(N)$ |
$O(N)$
|
| n-Queens Completion |
Grigoryan (n-Queens Completion n-Queens Problem) |
2018 |
$O(n)$ |
$O(n)$
|
| Cycle Detection |
Sedgewick; Szymanski; and Yao (Cycle Detection Cycle Detection) |
1982 |
$(\mu + \lambda)({1}+\Theta({1}/sqrt(M)))$ |
M
|
| Cycle Detection |
Nivasch (Cycle Detection Cycle Detection) |
2004 |
$O(\mu + \lambda)$ |
$O(\log\mu)$
|
| Comparison Sorting |
Naive sorting (Comparison Sorting Sorting) |
1940 |
$O(n^{2})$ |
$O({1})$ (in-situ)
|
| Comparison Sorting |
Selection Sort (Comparison Sorting Sorting) |
1962 |
$O(n^{2})$ |
$O({1})$ (in-situ)
|
| Comparison Sorting |
Merge Sort (Comparison Sorting Sorting) |
1945 |
$O(n \log n)$ |
$O(n)$
|
| Comparison Sorting |
Bubble Sort (Comparison Sorting Sorting) |
1956 |
$O(n^{2})$ |
$O({1})$ (in-situ)
|
| Comparison Sorting |
Intro Sort (Comparison Sorting Sorting) |
1997 |
$O(n \log n)$ |
$O(logn)$
|
| Comparison Sorting |
Heap Sort (Comparison Sorting Sorting) |
1964 |
$O(n \log n)$ |
$O({1})$ (in-situ)
|
| Non-Comparison Sorting |
Counting Sort (Non-Comparison Sorting Sorting) |
1954 |
$O(n+k)$ |
$O(n+k)$
|
| Non-Comparison Sorting |
Bucket Sort (Non-Comparison Sorting Sorting) |
1940 |
$O( n² )$ |
$O(n)$
|
| Non-Comparison Sorting |
Radix Sort (Non-Comparison Sorting Sorting) |
1940 |
$O(wn)$ |
$O(w+n)$
|
| kth Order Statistic |
Naive Selection (kth Order Statistic kth Order Statistic) |
1940 |
$O(n \log n)$ |
$O({1})$ (in-situ)
|
| kth Order Statistic |
Hoare's Selection Algorithm (QuickSelect) (kth Order Statistic kth Order Statistic) |
1961 |
$O(n^{2})$ |
$O({1})$ (in-situ)
|
| Matrix Chain Ordering Problem |
Brute Force (Matrix Chain Ordering Problem Matrix Chain Multiplication) |
1940 |
$O({4}^n)$ |
$O(n)$
|
| Matrix Chain Ordering Problem |
Dynamic Programming Algorithm (S. S. Godbole) (Matrix Chain Ordering Problem Matrix Chain Multiplication) |
1953 |
$O(n^{3})$ |
$O(n^{2})$
|
| LCS |
Wagner and Fischer (LCS Longest Common Subsequence) |
1974 |
$O(mn)$ |
$O(mn)$
|
| Maximum Flow |
Ford & Fulkerson ( Maximum Flow) |
1955 |
$O(E^{2}U)$ |
$O(E)$
|
| Maximum Flow |
Dinitz ( Maximum Flow) |
1970 |
$O(V^{2}E)$ |
$O(E)$
|
| Maximum Flow |
Edmonds & Karp ( Maximum Flow) |
1972 |
$O(E^{2} \log U)$ |
$O(E)$
|
| Maximum Flow |
Karzanov ( Maximum Flow) |
1974 |
$O(V^{3})$ |
$O(V^{2})$
|
| Maximum Flow |
Galil & Naamad ( Maximum Flow) |
1980 |
$O(VE \log^{2} V)$ |
$O(E)$
|
| Matrix Multiplication |
Naive algorithm (Matrix Multiplication Matrix Product) |
1940 |
$O(n^{3})$ |
$O({1})$ auxiliary
|
| Matrix Multiplication |
Strassen's algorithm (Matrix Multiplication Matrix Product) |
1969 |
$O(n^{(log7/log2)}) ~ O(n^{2.{80}7})$ |
$O(n^{2})$
|
| Matrix Multiplication |
Pan's algorithm (Matrix Multiplication Matrix Product) |
1978 |
$O(n^{(log({143640})/log({70}))}) ~ O(n^{2.{79}5})$ |
$O(n^{2})$
|
| Matrix Multiplication |
Romani's algorithm (Matrix Multiplication Matrix Product) |
1981 |
$O(n^{2.{5166}5})$ |
$O(n^{2})$
|
| Matrix Multiplication |
Coppersmith–Winograd algorithm (Matrix Multiplication Matrix Product) |
1981 |
$O(n^{2.{49554}8})$ |
$O(n^{2})$
|
| Matrix Multiplication |
Strassen's algorithm (Matrix Multiplication Matrix Product) |
1986 |
$O(n^{(log54/log5)}) ~ O(n^{({2.4785})})$ |
$O(n^{2})$
|
| Matrix Multiplication |
Coppersmith–Winograd algorithm (Matrix Multiplication Matrix Product) |
1990 |
$O(n^{2.{375}5})$ |
$O(n^{2})$
|
| Matrix Multiplication |
Vassilevska Williams (Matrix Multiplication Matrix Product) |
2014 |
$O(n^{2.{37287}3})$ |
$O(n^{2})$
|
| Matrix Multiplication |
François Le Gall (Matrix Multiplication Matrix Product) |
2014 |
$O(n^{2.{372863}9})$ |
$O(n^{2})$
|
| 3-Graph Coloring |
Brute-force search (3-Graph Coloring Graph Coloring) |
1852 |
$O((m+n)*{3}^n)$ |
$O(n)$ auxiliary
|
| 4-Graph Coloring |
Brute force (4-Graph Coloring Graph Coloring) |
1852 |
$O((m+n)*{4}^n)$ |
$O(n)$ auxiliary
|
| General Linear System; Positive Definite, Hermitian Matrix; Non-Definite, Symmetric Matrix; Toeplitz Matrix; Vandermonde Matrix |
Gaussian-Jordan Elimination (General Linear System; Positive Definite, Hermitian Matrix; Non-Definite, Symmetric Matrix; Toeplitz Matrix; Vandermonde Matrix Linear System) |
-150 |
$O(n^{3})$ |
$O(n^{2})$
|
| Positive Definite, Hermitian Matrix |
Cholesky (Positive Definite, Hermitian Matrix Linear System) |
1940 |
$O(n^{3})$ |
$O(n^{2})$
|
| Non-Definite, Symmetric Matrix |
Aasen's method (Non-Definite, Symmetric Matrix Linear System) |
1971 |
$O(n^{3})$ |
$O(n^{2})$ total
|
| Toeplitz Matrix |
Levinson–Durbin recursion (Toeplitz Matrix Linear System) |
1947 |
$O(n^{2})$ |
$O(n^{2})$ total
|
| Toeplitz Matrix |
Bareiss Algorithm (Toeplitz Matrix Linear System) |
1969 |
$O(n^{2})$ |
$O(n^{2})$ total
|
| Vandermonde Matrix |
Bjorck-Pereyra (Vandermonde Matrix Linear System) |
1970 |
$O(n^{2})$ |
$O(n^{2})$ total
|
| Linear Programming |
Fourier–Motzkin elimination ( Linear Programming) |
1940 |
$O((m/{4})$^{({2}^n)}) |
$O((m/{4})$^{({2}^n)})
|
| Linear Programming |
Khachiyan Ellipsoid algorithm ( Linear Programming) |
1979 |
$O(n^{6} * L^{2} \log L \log\log L)$ |
$O(nmL)$
|
| Reporting all intersection points, line segments |
Naive (Reporting all intersection points, line segments Line segment intersection) |
1940 |
$O(n^{2})$ |
$O({1})$
|
| Reporting all intersection points, line segments |
Bentley–Ottmann algorithm (Reporting all intersection points, line segments Line segment intersection) |
1979 |
$O( n \log n + k \log n)$ |
$O(n)$
|
| 2-dimensional |
Brute Force (2-dimensional Convex Hull) |
1935 |
$O(n^{3})$ |
$O(n)$
|
| 2-dimensional |
Jarvis (2-dimensional Convex Hull) |
1973 |
$O(nh)$ |
$O({1})$
|
| Undirected, General MST |
Kruskal’s algorithm with demand-sorting (Undirected, General MST Minimum Spanning Tree (MST)) |
1991 |
$O(E \log V)$ |
$O(E)$
|
| Undirected, General MST |
Quick Kruskal algorithm (Undirected, General MST Minimum Spanning Tree (MST)) |
2006 |
$O(E \log V)$ |
$O(E)$
|
| Undirected, General MST |
Karger; Klein & Tarjan (Undirected, General MST Minimum Spanning Tree (MST)) |
1995 |
$O(min(V^{2}, ElogV)$) |
$O(E)$
|
| k-dimensional space, l_m (or l_infty) norm |
Naive Implementation (k-dimensional space, l_m (or l_infty) norm Closest Pair Problem) |
1975 |
$O(kn^{2})$ |
$O({1})$
|
| Square Matrix LU Decomposition |
Doolittle Algorithm (Square Matrix LU Decomposition LU Decomposition) |
1878 |
$O(n^{3})$ |
$\tilde{O}({1})$
|
| Square Matrix LU Decomposition |
Crout and LUP algorithms (Square Matrix LU Decomposition LU Decomposition) |
2007 |
$O(n^{3})$ |
$\tilde{O}({1})$
|
| Square Matrix LU Decomposition |
Okunev; Johnson (Square Matrix LU Decomposition LU Decomposition) |
1997 |
$O(n^{3})$ |
$O({1})$
|
| Informed Search |
A* Algorithm (Informed Search Informed Search) |
1968 |
$O(b^d)$ |
$O(b^d)$
|
| Informed Search |
Bidirectional A* Algorithm (Informed Search Informed Search) |
2007 |
$O(b^{(d/{2})})$ |
$O(b^{(d/{2})$})
|
| Informed Search |
Fringe Saving A* (FSA*) (Informed Search Informed Search) |
2008 |
$O(b^d)$ |
$O(b^d)$
|
| Informed Search |
Generalized Adaptive A* (GAA*) (Informed Search Informed Search) |
2008 |
$O(b^d)$ |
$O(b^d)$
|
| Informed Search |
Iterative Deepening A* (IDA*) (Informed Search Informed Search) |
1985 |
$O(b^d)$ |
$O(b^d)$
|
| Informed Search |
Jump Point Search (JPS) (Informed Search Informed Search) |
2011 |
$O(b^d)$ |
$O(b^d)$
|
| Informed Search |
Lifelong Planning A* (LPA*) (Informed Search Informed Search) |
2001 |
$O(b^d)$ |
$O(b^d)$
|
| Informed Search |
Simplified Memory-Bounded A* (SMA*) (Informed Search Informed Search) |
1992 |
$O(b^d)$ |
$O(b^d)$
|
| Informed Search |
Theta* (Informed Search Informed Search) |
2010 |
$O(b^d)$ |
$O(b^d)$
|
| Informed Search |
Anytime Repairing A* (ARA*) (Informed Search Informed Search) |
2005 |
$O(b^d)$ |
$O(b^d)$
|
| Informed Search |
Time-Bounded A* (TBA*) (Informed Search Informed Search) |
2009 |
$O(b^d)$ |
$O(b^d)$
|
| Single String Search |
Naïve string-search algorithm (Single String Search String Search) |
1940 |
$O(m(n-m+{1}))$ |
$O({1})$
|
| Single String Search |
Knuth-Morris-Pratt (KMP) algorithm (Single String Search String Search) |
1977 |
$O(m+n)$ |
$O(m)$
|
| Single String Search |
Boyer-Moore (BM) algorithm (Single String Search String Search) |
1977 |
$O(mn + s)$ |
$O(s)$
|
| Single String Search |
Rabin-Karp (RK) algorithm (Single String Search String Search) |
1987 |
$O(mn)$ |
$O({1})$
|
| Edit sequence, global alignment |
Needleman–Wunsch algorithm (Edit sequence, global alignment Sequence Alignment) |
1970 |
$O(mn)$ |
$O(mn)$
|
| Edit sequence, local alignment |
Smith–Waterman algorithm (Edit sequence, local alignment Sequence Alignment) |
1981 |
$O(mn^{2})$ |
$O(mn)$
|
| Edit distance |
Masek; Patterson (Edit distance Sequence Alignment) |
1980 |
$O(mn / log(n))$ |
$O(n)$
|
| Edit sequence |
Hirschberg's algorithm (Edit sequence Sequence Alignment) |
1975 |
$O(mn)$ |
$O(n)$
|
| Edit sequence, local alignment |
FASTA (Edit sequence, local alignment Sequence Alignment) |
1985 |
$O(mn)$ |
$O(mn)$
|
| Edit sequence, local alignment |
Gotoh (Edit sequence, local alignment Sequence Alignment) |
1982 |
$O(mn)$ |
$O(mn)$
|
| Edit sequence, local alignment |
Altschul and Erickson (Edit sequence, local alignment Sequence Alignment) |
1986 |
$O(mn)$ |
$O(mn)$
|
| Edit sequence, local alignment |
Myers and Miller (Edit sequence, local alignment Sequence Alignment) |
1988 |
$O(mn)$ |
$O(n+log(m)$)
|
| Edit sequence, global alignment |
David Sankoff (Edit sequence, global alignment Sequence Alignment) |
1972 |
$O(mn)$ |
$O(mn)$
|
| Rectangular Window |
Cohen–Sutherland (Rectangular Window Line Clipping) |
1967 |
$O(n)$ |
$O({1})$
|
| Rectangular Window |
Liang–Barsky (Rectangular Window Line Clipping) |
1984 |
$O(n)$ |
$O({1})$
|
| Convex Polygonal Window; Convex Polyhedral window |
Cyrus–Beck (Convex Polygonal Window; Convex Polyhedral window Line Clipping) |
1978 |
$O(np)$ |
$O({1})$
|
| Rectangular Window |
Nicholl–Lee–Nicholl (Rectangular Window Line Clipping) |
1987 |
$O(n)$ |
$O({1})$
|
| Rectangular Window |
Fast clipping (Rectangular Window Line Clipping) |
1987 |
$O(n)$ |
$O({1})$
|
| NFA to DFA conversion |
Rabin–Scott powerset construction ( NFA to DFA conversion) |
1959 |
$O({2}^n)$ |
$O({1})$
|
| Multiplication |
Karatsuba Algorithm ( Multiplication) |
1962 |
$O(n^{1.{5}8})$ |
$O(n)$
|
| Multiplication |
Toom-3 ( Multiplication) |
1969 |
$O(n^{1.{4}6})$ |
$O(n)$
|
| Multiplication |
Long Multiplication ( Multiplication) |
1940 |
$O(n^{2})$ |
$O(n)$
|
| Line Simplification |
Ramer–Douglas–Peucker algorithm ( Line Simplification) |
1972 |
$O(n^{2})$ |
$O(n)$
|
| Line Simplification |
Visvalingam–Whyatt ( Line Simplification) |
1993 |
$O(n^{2})$ |
$O(n)$
|
| Line Simplification |
Reumann–Witkam ( Line Simplification) |
1974 |
$O(n)$ |
$O({1})$
|
| Line Simplification |
Opheim simplification ( Line Simplification) |
1981 |
$O(n)$ |
$O({1})$
|
| Line Simplification |
Lang simplification ( Line Simplification) |
1969 |
$O(n)$ |
$O({1})$
|
| Line Simplification |
Zhao-Saalfeld ( Line Simplification) |
1997 |
$O(n)$ |
$O(n)$
|
| Nearest Neighbor Search (NNS) |
Linear search (Nearest Neighbor Search (NNS) Nearest Neighbor Search) |
1940 |
$O(n)$ |
$O({1})$
|
| Nearest Neighbor Search (NNS) |
k-d Tree (Nearest Neighbor Search (NNS) Nearest Neighbor Search) |
1975 |
k-d Tree construction: $O(n \log n)$
NNS: $O(n)$ || $O(n)$
|
| Nearest Neighbor Search (NNS) |
R-tree (Nearest Neighbor Search (NNS) Nearest Neighbor Search) |
1984 |
R-Tree construction: $O(n \log n)$
NNS: $O(n)$ || $O(log n)$
|
| Subset Sum |
Horowitz and Sahni (Subset Sum The Subset-Sum Problem) |
1974 |
$O({2}^{(n/{2})})$ |
$O({2}^{(n/{2})$})
|
| Subset Sum |
Bellman dynamic programming algorithm (Subset Sum The Subset-Sum Problem) |
1956 |
$O(n t)$ |
$O(t)$
|
| Subset Sum |
Psinger (Subset Sum The Subset-Sum Problem) |
1999 |
$O(n max(S))$ |
$O(t)$
|
| Subset Sum |
Koiliaris and Xu (Subset Sum The Subset-Sum Problem) |
2019 |
$\tilde{O}(min{\sqrt{n'}t, t^{5/4}, σ})$ |
$O(t)$
|
| Subset Sum |
Bringman (Subset Sum The Subset-Sum Problem) |
2017 |
$\tilde{O}(nt^{1+\epsilon})$ |
\tilde{O}(nt^\epsilon)
|
| 1D Maximum Subarray |
Brute Force (1D Maximum Subarray Maximum Subarray Problem) |
1977 |
$O(n^{3})$ |
$O({1})$
|
| 1D Maximum Subarray |
Grenander (1D Maximum Subarray Maximum Subarray Problem) |
1977 |
$O(n^{2})$ |
$O(n)$
|
| 1D Maximum Subarray |
Faster Brute Force (via x(L:U) = x(L:U-1)+x(U)) (1D Maximum Subarray Maximum Subarray Problem) |
1977 |
$O(n^{2})$ |
$O({1})$
|
| 1D Maximum Subarray |
Shamos (1D Maximum Subarray Maximum Subarray Problem) |
1978 |
$O(n \log n)$ |
$O(\log n)$
|
| 1D Maximum Subarray |
Kadane's Algorithm (1D Maximum Subarray Maximum Subarray Problem) |
1982 |
$O(n)$ |
$O({1})$ auxiliary
|
| 1D Maximum Subarray |
Perumalla and Deo (1D Maximum Subarray Maximum Subarray Problem) |
1995 |
$O(\log n)$ |
$O(n)$ auxiliary
|
| Motif Search |
Speller (Motif Search Motif Search) |
1998 |
$O(mn^{2} \sigma)$ |
$O(mn^{2}/w)$
|
| Motif Search |
Mitra (Motif Search Motif Search) |
2002 |
$O(k nm \sigma)$ |
$O(mnk)$
|
| Motif Search |
Census (Motif Search Motif Search) |
2003 |
$O(k nm \sigma)$ |
$O(mnk)$
|
| Motif Search |
Risotto (Motif Search Motif Search) |
2006 |
$O(mn^{2} \sigma)$ |
$O(mn^{2})$
|
| Motif Search |
PMS (Motif Search Motif Search) |
2007 |
$O(nm^{2} \sigma)$ |
$O(m^{2} n)$
|
| Rod-Cutting Problem |
Brute Force (Rod-Cutting Problem Rod-Cutting Problem) |
1940 |
$O(n*{2}^n)$ |
$O(n)$
|
| Rod-Cutting Problem |
Dynamic Programming (Rod-Cutting Problem Rod-Cutting Problem) |
1953 |
$O(n^{2})$ |
$O(n)$
|
| Change-Making Problem |
Brute Force (Change-Making Problem Change-Making Problem) |
1940 |
$O(S^n)$ |
$O(n)$
|
| Change-Making Problem |
Dynamic Programming (Change-Making Problem Change-Making Problem) |
1953 |
$O(Sn)$ |
$O(Sn)$
|
| Approximate MCOP |
Czumaj (Approximate MCOP Matrix Chain Multiplication) |
1996 |
$O(\log n)$ |
$O(n)$
|
| Approximate MCOP |
Czumaj (Approximate MCOP Matrix Chain Multiplication) |
1996 |
$O(\log \log n)$ |
$O(n)$
|
| Approximate MCOP |
Chandra (Approximate MCOP Matrix Chain Multiplication) |
1975 |
$O(n)$ |
$O(n)$?
|
| Approximate MCOP |
Chin (Approximate MCOP Matrix Chain Multiplication) |
1978 |
$O(n)$ |
$O(n)$
|
| Matrix Multiplication |
Bini's algorithm (Matrix Multiplication Matrix Product) |
1979 |
$O(n^{2.{779}9})$ |
$O(n^{2})$
|
| Matrix Multiplication |
Schonhage's algorithm (Matrix Multiplication Matrix Product) |
1980 |
$O(n^{({3}*\log {52}/l \og {110})}) ~ O(n^{2.{521}8})$ |
$O(n^{2})$
|
| [[O(n^{3/14}) coloring a 3-colorable graph|O(n^{3/14}) coloring a 3-colorable graph]] |
[[Karger, Blum (O(n^{3/14}) coloring a 3-colorable graph Graph Coloring)]] |
1997 |
$O(poly(n))$ |
-
|
| 3-Graph Coloring |
Brélaz (DSatur) (3-Graph Coloring Graph Coloring) |
1979 |
$O(n^{2})$ |
$O(m+n)$
|
| Maximum Cardinality Matching |
Micali and Vazirani ( Maximum Cardinality Matching) |
1980 |
$O(V^{0.5} E)$ |
$O(V)$
|
| Minimum TSP |
Miller-Tucker-Zemlin (MTZ) formulation (Minimum TSP The Traveling-Salesman Problem) |
1960 |
$exp(V)$ |
$O(V^{4})$
|
| Minimum TSP |
Dantzig-Fulkerson-Johnson (DFJ) formulation (Minimum TSP The Traveling-Salesman Problem) |
1954 |
$O({1.674}^V E^{2})$ |
$O({2}^V)$
|
| Geometric Maximum TSP |
Barvinok (Geometric Maximum TSP The Traveling-Salesman Problem) |
2003 |
$O(V^{2} \log\log E)$ |
$O(V)$?
|
| Corner Detection |
Harris and Stephens algorithm (Corner Detection Feature Detection) |
1988 |
$O(n^{2})$ |
-
|
| Corner Detection |
L. Kitchen and A. Rosenfeld (Corner Detection Feature Detection) |
1982 |
$O(n^{3})$ |
-
|
| Corner Detection |
The SUSAN corner detector (Corner Detection Feature Detection) |
1997 |
$O(n^{3})$ |
-
|
| Weighted Set-Covering |
Chvatal greedy heuristic (Weighted Set-Covering The Set-Covering Problem) |
1979 |
$O(dn^{2})$ |
$O(dm)$
|
| Unweighted Set-Covering |
Alon; Moshkovitz & Safra (Unweighted Set-Covering The Set-Covering Problem) |
2006 |
$O(nlogn)$ |
-
|
| Motif Search |
Roth AlignACE (Motif Search Motif Search) |
1998 |
$O(nm)$ |
$O(n + m)$
|
| Image Compositing |
Petro Vlahos Algorithm (Image Compositing Image Compositing) |
1985 |
$O(n^{2} k/r)$ |
$O(nk)$??
|
| Texture Synthesis |
non-parametric sampling Efros and Leung (Texture Synthesis Texture Synthesis) |
1999 |
$O(n^{3})$ |
-
|
| Texture Synthesis |
image analogies Hertzmann (Texture Synthesis Texture Synthesis) |
2001 |
$O(N \log n)$ |
-
|
| Texture Synthesis |
R. Paget ; I.D. Longstaff (Texture Synthesis Texture Synthesis) |
1998 |
$O(n^{3})$ |
-
|
| Texture Synthesis |
Image quilting Efros-Freeman (Texture Synthesis Texture Synthesis) |
2001 |
$O(n^{3})$ |
-
|
| SLAM Algorithms |
EKF SLAM (SLAM Algorithms SLAM Algorithms) |
1998 |
$O(n^{3})$ |
$O(n^{2})$?
|
| SLAM Algorithms |
UKF (SLAM Algorithms SLAM Algorithms) |
2000 |
$O(n^{3})$ |
$O(n^{2})$?
|
| SLAM Algorithms |
Compressed Extended KF (SLAM Algorithms SLAM Algorithms) |
2002 |
$O(n^{3})$ |
$O(n^{2})$?
|
| SLAM Algorithms |
Rao-Blackwellized Particle Filtering SLAM (SLAM Algorithms SLAM Algorithms) |
2001 |
$O(n^{2})$ |
$O(n)$?
|
| 3-Graph Coloring |
Petford and Welsh (3-Graph Coloring Graph Coloring) |
1989 |
$O(n \log n)$ |
$O(n)$
|
| 4-Graph Coloring |
Fomin; Gaspers & Saurabh (4-Graph Coloring Graph Coloring) |
2007 |
$O({1.7272}^n)$ |
$O(n)$
|
| Closest Pair Problem |
Khuller; Matias ( Closest Pair Problem) |
1995 |
$O(n)$ |
$O(n)$, not sure if this is auxiliary
|
| Square Matrix LU Decomposition |
Bunch; Hopcroft (Square Matrix LU Decomposition LU Decomposition) |
1974 |
$O(n^{2.{37}6})$ |
$\tilde{O}(n^{2})$
|
| Single String Search |
Bitap algorithm (Single String Search String Search) |
1964 |
$O(mn)$ |
$O(m)$
|
| Comparison Sorting |
Tree sort (Comparison Sorting Sorting) |
1986 |
$O(n \log n)$ |
$O(n)$
|
| Comparison Sorting |
Quick Sort (Comparison Sorting Sorting) |
1961 |
$O(n^{2})$ |
$O(\log n)$
|
| Comparison Sorting |
Tim Sort (Comparison Sorting Sorting) |
2002 |
$O(n logn)$ |
$O(n)$
|
| Comparison Sorting |
Cube Sort Parallel Implementation (Comparison Sorting Sorting) |
1992 |
$O(n logn)$ |
$O(n)$
|
| Comparison Sorting |
Shell Sort (Shell) (Comparison Sorting Sorting) |
1959 |
$O(n^{2})$ |
$O({1})$
|
| Comparison Sorting |
Shell Sort (Frank & Lazarus) (Comparison Sorting Sorting) |
1960 |
$O(n^{1.5})$ |
$O({1})$
|
| Comparison Sorting |
Shell Sort (Pratt) (Comparison Sorting Sorting) |
1971 |
$O(n \log^{2} n)$ |
$O({1})$
|
| Comparison Sorting |
Shell Sort (Sedgewick) (Comparison Sorting Sorting) |
1986 |
$O(n^{1.{3}3})$ |
$O({1})$
|
| Comparison Sorting |
Bitonic Merge Sort Parallel Implementation (Comparison Sorting Sorting) |
1968 |
$O(\log^{2} n)$ |
$O({1})$
|
| Comparison Sorting |
Thorup's Sorting Algorithm (Comparison Sorting Sorting) |
2002 |
$O(n \log \log n)$ |
$O(n)$
|
| Non-Comparison Sorting |
Naive sorting (Non-Comparison Sorting Sorting) |
1940 |
$O(n^{2})$ |
$O({1})$
|
| Non-Comparison Sorting |
Flash Sort (Non-Comparison Sorting Sorting) |
1998 |
$O(n^{2})$ |
$O(n)$
|
| Non-Comparison Sorting |
Bead Sort (Non-Comparison Sorting Sorting) |
2002 |
$O(n)$ |
$O(n^{2})$
|
| Non-Comparison Sorting |
Burst Sort (Non-Comparison Sorting Sorting) |
2004 |
$O(wn)$ |
$O(wn)$
|
| Non-Comparison Sorting |
Spreadsort (Non-Comparison Sorting Sorting) |
2002 |
$O(n \log n)$ |
$O(n)$?
|
| kth Order Statistic |
Hashing (kth Order Statistic kth Order Statistic) |
1940 |
$O(n)$ |
$O(n)$
|
| Matrix Chain Ordering Problem |
T. C. Hu ; M. T. Shing (Matrix Chain Ordering Problem Matrix Chain Multiplication) |
1982 |
$O(n \log n)$ |
$O(n)$
|
| LCS |
Hunt and Szymanski (LCS Longest Common Subsequence) |
1977 |
$O((n + p) \log n)$ |
$O(p + n)$
|
| LCS |
Mukhopadhyay (LCS Longest Common Subsequence) |
1980 |
$O((n + p) \log n)$ |
$O(p + n)$
|
| Maximum Flow |
Dantzig ( Maximum Flow) |
1951 |
$O(V^{2}EU)$ |
$O(VE)$?
|
| Maximum Flow |
Dinitz (with dynamic trees) ( Maximum Flow) |
1973 |
$O(VE \log U)$ |
$O(E)$
|
| Maximum Flow |
Cherkassky ( Maximum Flow) |
1977 |
$O(V^{2}E^{0.5})$ |
$O(E)$
|
| Maximum Flow |
Sleator & Tarjan ( Maximum Flow) |
1983 |
$O(VE \log V)$ |
$O(E)$
|
| Maximum Flow |
Goldberg & Tarjan ( Maximum Flow) |
1986 |
$O(VE \log (V^{2}/E))$ |
$O(E)$
|
| Maximum Flow |
Ahuja & Orlin ( Maximum Flow) |
1987 |
$O(VE + V^{2} \log U)$ |
$O(ELogU)$
|
| st-Maximum Flow |
Cheriyan & Hagerup (st-Maximum Flow Maximum Flow) |
1989 |
$O(VE \log V)$ |
$O(V + E)$
|
| st-Maximum Flow |
Cheriyan et al. (st-Maximum Flow Maximum Flow) |
1990 |
$O(V^{3} / \log V)$ |
$O(V + E)$
|
| st-Maximum Flow |
Alon (st-Maximum Flow Maximum Flow) |
1990 |
$O(VE + V^{2.{6}6} \log V)$ |
$O(V + E)$
|
| st-Maximum Flow |
King et al. (KRT) (st-Maximum Flow Maximum Flow) |
1992 |
$O(VE + V^{2+\epsilon})$ |
$O(V + E)$
|
| st-Maximum Flow |
Phillips & Westbrook (st-Maximum Flow Maximum Flow) |
1993 |
$O(VE(\log(V;V/E)) + V^{2}(\log V)^{2} )$ |
$O(V + E)$
|
| Integer Maximum Flow |
Goldberg & Rao (Integer Maximum Flow Maximum Flow) |
1997 |
$O(E^{1.5} \log(V^{2}/E) \log U)$ |
$O(V + E)$
|
| Integer Maximum Flow |
Goldberg & Rao (Integer Maximum Flow Maximum Flow) |
1997 |
$O(V^{0.{6}6}E \log(V^{2}/E) \log U)$ |
$O(V + E)$
|
| st-Maximum Flow |
James B Orlin's + KRT (King; Rao; Tarjan)'s algorithm (st-Maximum Flow Maximum Flow) |
2013 |
$O(VE)$ |
$O(V + E)$
|
| 3-Graph Coloring |
Lawler (3-Graph Coloring Graph Coloring) |
1976 |
$O(m*n*{3}^{(n/{3})}) ~ O(mn({1.445})^n)$ |
$O(n+m)$
|
| 3-Graph Coloring |
Schiermeyer (3-Graph Coloring Graph Coloring) |
1994 |
$O({1.415}^n)$ |
$O(nm+n^{2})$ loose bound, possibly $O(n+m)$?
|
| 3-Graph Coloring |
Beigel & Eppstein (3-Graph Coloring Graph Coloring) |
1995 |
$O({1.3446}^n)$ |
$O(n^{2})$?
|
| 3-Graph Coloring |
Beigel & Eppstein (3-Graph Coloring Graph Coloring) |
2000 |
$O({1.3289}^n)$ |
$O(n^{2})$?
|
| 4-Graph Coloring |
Lawler (4-Graph Coloring Graph Coloring) |
1976 |
$O((m + n)*{2}^n)$ |
$O(n+m)$
|
| 4-Graph Coloring |
Byskov (4-Graph Coloring Graph Coloring) |
2004 |
$O({1.7504}^n)$ |
$O(n^{2})$?
|
| Positive Definite Matrix |
Conjugate Gradient (Positive Definite Matrix Linear System) |
1952 |
$O(m k^{0.5})$ |
$O(m)$
|
| Sparse Linear System |
Harrow (Quantum) (Sparse Linear System Linear System) |
2009 |
$O(k^{2}*\log n)$ |
$O(\log n)$
|
| Linear Programming |
Karmarkar's algorithm ( Linear Programming) |
1984 |
$O(n^{3.5} L^{2} logL loglogL)$ |
$O(nmL)$
|
| Linear Programming |
Simplex Algorithm ( Linear Programming) |
1947 |
$O({2}^n*poly(n, m))$ |
$O(nm)$
|
| Linear Programming |
Terlaky's Criss-cross algorithm ( Linear Programming) |
1985 |
$O({2}^n*poly(n, m))$ |
$O(nm)$
|
| Linear Programming |
Affine scaling ( Linear Programming) |
1967 |
? (originally $O(n^{3.5} L)$ but seems unclear) |
$O(nm+m^{2})$?
|
| Linear Programming |
Cohen; Lee and Song ( Linear Programming) |
2018 |
$O(n^{max(omega, {2.5}-alpha/{2}, {13}/{6})}*polylog(n, m, L))$, where omega is the exponent on matrix multiplication, alpha is the dual exponent of matrix multiplication;
currently $O(n^{2.37285956})$ || $O(nm+n^{2})$?
|
| Linear Programming |
Lee and Sidford ( Linear Programming) |
2015 |
$O((nnz(A) + n^{2}) n^{0.5})$ |
$O(nm+n^{2})$??
|
| Reporting all intersection points, line segments |
Chazelle & Edelsbrunner (Reporting all intersection points, line segments Line segment intersection) |
1992 |
$O( n \log n + k )$ |
$O(n+k)$ total?
|
| Reporting all intersection points, line segments |
CHAZELLE (Reporting all intersection points, line segments Line segment intersection) |
1986 |
$O( n*log^{2}(n)/(log log n) + k)$ |
$O(n+k)$ total (and possibly auxiliary as well?)
|
| Reporting all intersection points, convex polygons |
NIEVERGELT. J.. AND PREPARATA (Section 3) (Reporting all intersection points, convex polygons Line segment intersection) |
1982 |
$O( n \log n + k )$ |
$O(n)$
|
| Reporting all intersection points, generalized segments |
Jean-Daniel Boissonnat and Franco P. Preparata. (Reporting all intersection points, generalized segments Line segment intersection) |
1997 |
$O(n \log n + k \log n)$ |
$O(n)$
|
| Reporting all intersection points, generalized segments |
Balaban. (Reporting all intersection points, generalized segments Line segment intersection) |
1995 |
$O(n \log n + k )$ |
$O(n)$
|
| Reporting all intersection points, generalized segments |
Boissonnat; Snoeyink (Reporting all intersection points, generalized segments Line segment intersection) |
1999 |
$O(n \log n + k )$ |
$O(n)$
|
| Reporting all intersection points, line segments |
Goodrich (Reporting all intersection points, line segments Line segment intersection) |
1989 |
$O(\log^{2}(n))$ |
$O(n+k)$ total?
|
| 2-dimensional |
Graham (2-dimensional Convex Hull) |
1972 |
$O(n \log n)$ |
$O(n)$
|
| 2-dimensional |
W. Eddy Quickhull (2-dimensional Convex Hull) |
1977 |
$O(nh)$ |
$O(h)$?
|
| 2-dimensional; 3-dimensional |
Preparata and Hong (2-dimensional; 3-dimensional Convex Hull) |
1977 |
$O(nlogn)$ |
$O(n)$?
|
| 2-dimensional |
Andrew's algorithm (2-dimensional Convex Hull) |
1979 |
$O(nlogn)$ |
$O(n)$
|
| 2-dimensional |
The ultimate planar convex hull algorithm (2-dimensional Convex Hull) |
1986 |
$O(n log h)$ |
$O(n)$
|
| 2-dimensional; 3-dimensional |
Chan's algorithm (2-dimensional; 3-dimensional Convex Hull) |
1996 |
$O(n log h)$ |
$O(n)$
|
| 2-dimensional |
Miller; Stout (2-dimensional Convex Hull) |
1988 |
$O(logn)$ time using
$O(n)$ processors || $O(n)$ total?
|
| SCCs |
Kosaraju's algorithm (SCCs Strongly Connected Components) |
1978 |
$O(V+E)$ |
$O(V+E)$
|
| SCCs |
Tarjan's strongly connected components algorithm (SCCs Strongly Connected Components) |
1972 |
$O(V+E)$ |
$O(V)$
|
| SCCs |
Path-based strong components algorithm; Dijkstra (SCCs Strongly Connected Components) |
1976 |
$O(V+E)$ |
$O(V)$
|
| SCCs |
Fleischer forward-backward (FB) algorithm (SCCs Strongly Connected Components) |
2003 |
$O(E\log V+V)$ |
$O(V+E)$
|
| SCCs |
Pearce (SCCs Strongly Connected Components) |
2016 |
$O(V+E)$ |
$O(V)$
|
| SCCs |
Path-based depth-first search Gabow (SCCs Strongly Connected Components) |
2000 |
$O(V+E)$ |
$O(V+E)$ total, $O(V)$ auxiliary?
|
| Transitive Closure |
Paul Purdom (Transitive Closure Strongly Connected Components) |
1970 |
$O(V^{2}+VE)$ |
$O(V^{2})$
|
| SCCs |
Lowe’s Algorithm (SCCs Strongly Connected Components) |
2014 |
$O(V^{2})$ |
$O(V)$ per processor
|
| SCCs |
Renault’s Algorithm (SCCs Strongly Connected Components) |
2009 |
$O(p*(V+E)*\alpha(V, E))$ |
$O(V)$ per processor
|
| SCCs |
Couvreur (SCCs Strongly Connected Components) |
1999 |
$O(V+E)$ |
$O(V)$?
|
| SCCs |
Munro’s algorithm (SCCs Strongly Connected Components) |
1971 |
$O(E + V \log V)$ |
$O(V)$?
|
| SCCs |
OBF Algorithm (SCCs Strongly Connected Components) |
2011 |
$O(V(V+E))$ |
$O(E+V^{2})$ total
|
| SCCs |
CH Algorithm (SCCs Strongly Connected Components) |
2004 |
$O(VE)$ |
$O(V+E)$?
|
| SCCs |
Hong’s algorithm (SCCs Strongly Connected Components) |
2013 |
$O(V(V+E))$ |
$O(V+E)$?
|
| Undirected, General MST |
Borůvka's algorithm (Undirected, General MST Minimum Spanning Tree (MST)) |
1926 |
$O(E \log V)$ |
$O(V)$ auxiliary
|
| Undirected, General MST |
Prim's algorithm + adjacency matrix searching (Undirected, General MST Minimum Spanning Tree (MST)) |
1957 |
$O(V^{2})$ |
$O(V)$ auxiliary
|
| Undirected, General MST |
Prim's algorithm + Fibonacci heaps; Fredman & Tarjan (Undirected, General MST Minimum Spanning Tree (MST)) |
1987 |
$O(E + V \log V)$ |
$O(V)$ auxiliary?
|
| Undirected, General MST |
Kruskal's algorithm (Undirected, General MST Minimum Spanning Tree (MST)) |
1956 |
$O(E \log E)$ |
$O(E)$ auxiliary
|
| Undirected, General MST |
Yao's algorithm (Undirected, General MST Minimum Spanning Tree (MST)) |
1975 |
$O(E \log \log V)$ |
$O(E)$ auxiliary?
|
| Undirected, General MST |
Cheriton-Tarjan Algorithm (Undirected, General MST Minimum Spanning Tree (MST)) |
1976 |
$O(E \log \log V)$ |
$O(E)$ auxiliary?
|
| Undirected, General MST |
Filter Kruskal algorithm (Undirected, General MST Minimum Spanning Tree (MST)) |
2009 |
$O(E \log V)$ |
$O(E)$ auxiliary?
|
| Undirected, General MST |
Chazelle's algorithm (Undirected, General MST Minimum Spanning Tree (MST)) |
2000 |
$O(E*\alpha(E, V))$ |
$O(E)$ auxiliary??
|
| Undirected, General MST |
Thorup (reverse-delete) (Undirected, General MST Minimum Spanning Tree (MST)) |
2000 |
$O(E \log V (\log \log V)^{3})$ |
$O(E)$ auxiliary?
|
| k-dimensional space, l_m (or l_infty) norm |
Fortune and Hopcroft (k-dimensional space, l_m (or l_infty) norm Closest Pair Problem) |
1979 |
$O(kn \log\log n+n*{3}^k)$ |
$O(n)$
|
| k-dimensional space, l_m (or l_infty) norm |
F. Preparata and M. Shamos (k-dimensional space, l_m (or l_infty) norm Closest Pair Problem) |
1986 |
$O(kn \log n)$ |
$O(kn)$?
|
| k-dimensional space, l_m (or l_infty) norm |
Rabin' Algorithm (k-dimensional space, l_m (or l_infty) norm Closest Pair Problem) |
1976 |
$O({3}^k*n^{2})$ |
$O(n)$
|
| k-dimensional space, l_m (or l_infty) norm |
Bentley (k-dimensional space, l_m (or l_infty) norm Closest Pair Problem) |
1980 |
$O(kn \log n)$ |
$O(kn)$?
|
| k-dimensional space, l_m (or l_infty) norm |
Bentley; Shamos (k-dimensional space, l_m (or l_infty) norm Closest Pair Problem) |
1976 |
$O(kn \log n)$ |
$O(kn)$?
|
| 2-dimensional space, l_m (or l_infty) norm |
Hinrichs; Nievergelt; Schorn (2-dimensional space, l_m (or l_infty) norm Closest Pair Problem) |
1988 |
$O(n \log n)$ |
$O(n)$
|
| 2-dimensional space, Euclidean metric |
Shamos; Hoey (2-dimensional space, Euclidean metric Closest Pair Problem) |
1975 |
$O(n \log n)$ |
$O(n)$
|
| 2-dimensional array representation |
Dyer (2-dimensional array representation Closest Pair Problem) |
1980 |
$O(n)$ using $O(n^{2})$ processors |
$O(n^{2})$
|
| general weights |
Bellman–Ford algorithm (Ford 1956) (general weights Shortest Path (Directed Graphs)) |
1956 |
$O(V^{2} EL)$ |
$O(E)$
|
| general weights |
Bellman–Ford algorithm (Shimbel 1955; Bellman 1958; Moore 1959) (general weights Shortest Path (Directed Graphs)) |
1959 |
$O(VE)$ |
$O(V)$
|
| Nonnegative Weights |
Bellman–Ford algorithm (Dantzig 1960) (Nonnegative Weights Shortest Path (Directed Graphs)) |
1960 |
$O(V^{2} \log V)$ |
$O(E)$ (total)
|
| Nonnegative Weights |
Dijkstra's algorithm with list (Whiting & Hillier 1960) (Nonnegative Weights Shortest Path (Directed Graphs)) |
1960 |
$O(V^{2})$ |
$O(V)$
|
| Nonnegative Weights |
Dijkstra's algorithm with binary heap (Johnson 1977) (Nonnegative Weights Shortest Path (Directed Graphs)) |
1977 |
$O((E + V) \log V)$ |
$O(V)$
|
| Nonnegative Weights |
Dijkstra's algorithm with Fibonacci heap (Fredman & Tarjan 1984; Fredman & Tarjan 1987) (Nonnegative Weights Shortest Path (Directed Graphs)) |
1984 |
$O(E + V \log V)$ |
$O(V)$
|
| Nonnegative Integer Weights |
Dijkstra's algorithm with Fibonacci heap (Johnson 1981; Karlsson & Poblete 1983) (Nonnegative Integer Weights Shortest Path (Directed Graphs)) |
1981 |
$O(E \log \log L)$ |
$O(V+L)$
|
| Nonnegative Weights |
Gabow's algorithm (Nonnegative Weights Shortest Path (Directed Graphs)) |
1983 |
$O(E \log L/\log({2}+(E/V)))$ |
$O(V+E)$?
|
| Nonnegative Integer Weights |
Gabow Ahuja Algorithm (Nonnegative Integer Weights Shortest Path (Directed Graphs)) |
1990 |
$O(E + V*((\log(L))^{0.5}) )$ |
$O(E + \log C)$
|
| Nonnegative Integer Weights |
Thorup's algorithm (Nonnegative Integer Weights Shortest Path (Directed Graphs)) |
2004 |
$O(E + V min(log log V, log log L))$ |
$O(V)$? ("linear-space queue")
|
| APSP on Dense Directed Graphs with Arbitrary Weights |
Shimbel Algorithm (APSP on Dense Directed Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP)) |
1953 |
$O(n^{4})$ |
$O(n^{2})$
|
| APSP |
Floyd–Warshall algorithm (APSP All-Pairs Shortest Paths (APSP)) |
1962 |
$O(n^{3})$ |
$O(n^{2})$
|
| APSP on Dense Undirected Unweighted Graphs; APSP on Sparse Undirected Unweighted Graphs |
Seidel's algorithm (APSP on Dense Undirected Unweighted Graphs; APSP on Sparse Undirected Unweighted Graphs All-Pairs Shortest Paths (APSP)) |
1995 |
$O (n^{2.{37}3} \log n)$ |
$O(n^{2})$
|
| APSP on Dense Directed Graphs with Arbitrary Weights |
Williams (APSP on Dense Directed Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP)) |
2014 |
$O(n^{3} /{2}^{(\log n)^{0.5}})$ |
$O(n^{2})$
|
| APSP on Dense Undirected Graphs with Arbitrary Weights; APSP on Sparse Undirected Graphs with Arbitrary Weights |
Pettie & Ramachandran (APSP on Dense Undirected Graphs with Arbitrary Weights; APSP on Sparse Undirected Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP)) |
2002 |
$O(mn \log \alpha(m,n))$ |
-
|
| APSP on Dense Undirected Graphs with Positive Integer Weights; APSP on Sparse Undirected Graphs with Positive Integer Weights |
Thorup (APSP on Dense Undirected Graphs with Positive Integer Weights; APSP on Sparse Undirected Graphs with Positive Integer Weights All-Pairs Shortest Paths (APSP)) |
1999 |
$O(mn)$ |
$O(mn)$
|
| APSP on Geometrically Weighted Graphs |
Chan (Geometrically Weighted) (APSP on Geometrically Weighted Graphs All-Pairs Shortest Paths (APSP)) |
2009 |
$O(n^{2.{84}4})$ |
$O(l n^{2})$
|
| APSP on Dense Directed Graphs with Arbitrary Weights; APSP on Dense Undirected Graphs with Arbitrary Weights |
Chan (APSP on Dense Directed Graphs with Arbitrary Weights; APSP on Dense Undirected Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP)) |
2009 |
$O(n^{3} \log^{3} \log n / \log^{2} n)$ |
$O(n^{2})$
|
| First Category Integer Factoring |
Trial division (First Category Integer Factoring Integer Factoring) |
1202 |
$O({2}^{n/2})$ |
$O(n)$
|
| First Category Integer Factoring |
Wheel factorization (First Category Integer Factoring Integer Factoring) |
1940 |
$O({2}^{n/2})$ |
$O(n)$
|
| First Category Integer Factoring |
Pollard's rho algorithm (First Category Integer Factoring Integer Factoring) |
1975 |
- |
$O(n)$
|
| First Category Integer Factoring |
Pollard's p − 1 algorithm (First Category Integer Factoring Integer Factoring) |
1974 |
$O(B*log B*log^{2}(n)$)? |
$O(n+B)$
|
| First Category Integer Factoring |
Williams' p + 1 algorithm (First Category Integer Factoring Integer Factoring) |
1982 |
$O({2}^n)$ |
$O(n)$?
|
| First Category Integer Factoring |
Lenstra elliptic curve factorization (First Category Integer Factoring Integer Factoring) |
1987 |
$O(e^{(\sqrt(({1}+o({1}))n*log n))})$ |
$O(n)$?
|
| First Category Integer Factoring |
Fermat's factorization method (First Category Integer Factoring Integer Factoring) |
1894 |
$O({2}^n)$ |
$O(n)$?
|
| First Category Integer Factoring |
Euler's factorization method (First Category Integer Factoring Integer Factoring) |
1940 |
$O({2}^{(n/{2})})$ |
$O(n)$
|
| Second Category Integer Factoring |
Dixon's algorithm (Second Category Integer Factoring Integer Factoring) |
1981 |
$O(e^{({2} \sqrt({2}) \sqrt(n*logn))}){4} |
$O(n+(B/logB)$^{2})?
|
| Second Category Integer Factoring |
Continued fraction factorization (CFRAC) (Second Category Integer Factoring Integer Factoring) |
1931 |
$O(e^{\sqrt({2}n*logn)})$ |
$O(n+(B/logB)$^{2})?
|
| Second Category Integer Factoring |
Quadratic sieve (Second Category Integer Factoring Integer Factoring) |
1981 |
- |
$O(n+(B/logB)$^{2})?
|
| Second Category Integer Factoring |
Rational sieve (Second Category Integer Factoring Integer Factoring) |
1993 |
$O(e^{sqrt(({2}+o({1})$)n*logn)}) |
$O(n+(B/logB)$^{2})?
|
| Second Category Integer Factoring |
Shanks's square forms factorization (SQUFOF) (Second Category Integer Factoring Integer Factoring) |
2007 |
$O({2}^{n/4})$ |
$O(n)$?
|
| Square Matrix LU Decomposition |
Closed formula (Square Matrix LU Decomposition LU Decomposition) |
1975 |
$O(n \log n)$ |
-
|
| Rectangular Matrix LU Decomposition |
Randomized LU Decomposition (Rectangular Matrix LU Decomposition LU Decomposition) |
2016 |
$O(n^{3})$ |
$\tilde{O}(nl + ml)$
|
| Square Matrix LU Decomposition |
David (Square Matrix LU Decomposition LU Decomposition) |
2006 |
$O(n \log n)$ |
-
|
| Square Matrix LU Decomposition |
Press, Teukolsky, Flannery (Square Matrix LU Decomposition LU Decomposition) |
2007 |
$O(n^{3})$ |
$\tilde{O}(n)$
|
| Informed Search |
Greedy Best-First Search (Informed Search Informed Search) |
1959 |
$O(b^d)$ |
$O(b^d)$
|
| Informed Search |
Incremental Heuristic Search ( Informed Search) |
1968 |
$O(b^d)$ |
-
|
| Informed Search |
Block A* (Informed Search Informed Search) |
2011 |
$O(b^d)$ |
$O(b^d)$
|
| Informed Search |
D* (Informed Search Informed Search) |
1994 |
$O(b^d)$ |
$O(b^d)$
|
| Informed Search |
Field D* (Informed Search Informed Search) |
2006 |
$O(b^d)$ |
$O(b^d)$
|
| Informed Search |
Fringe (Informed Search Informed Search) |
2005 |
$O(b^d)$ |
$O(b^d)$
|
| Single String Search |
Tuned Boyer-Moore algorithm (Single String Search String Search) |
1991 |
$O(mn)$ |
$O(m + s)$
|
| Edit sequence, global alignment |
FOGSAA (Edit sequence, global alignment Sequence Alignment) |
2013 |
$O(mn)$ |
$O(mn)$?
|
| convex polygonal window |
O(lg N) algorithm (convex polygonal window Line Clipping) |
1994 |
$O(n*\log p)$ |
$O({1})$ auxiliary??
|
| convex and non-convex polyhedral window |
Skala (convex and non-convex polyhedral window Line Clipping) |
1996 |
$O(np)$? |
$O({1})$ auxiliary?
|
| Multiplication |
Schönhage–Strassen algorithm ( Multiplication) |
1971 |
$O(n \log n \log\log n)$ |
$O(n)$ auxiliary?
|
| Multiplication |
Furer's algorithm ( Multiplication) |
2007 |
$O(n \log n {2}^{O(\log*n)})$ |
$O(n)$ auxiliary?
|
| Multiplication |
De ( Multiplication) |
2008 |
$O(n \log n {2}^{O(\log*n)})$ |
$O(n)$ auxiliary?
|
| Multiplication |
Harvey; Hoeven ( Multiplication) |
2019 |
$O(n \log n)$ |
$O(n)$ auxiliary??
|
| Multiplication |
Harvey; Hoeven; Lecerf ( Multiplication) |
2015 |
$O(n \log n {2}^{({3} \log*n)})$ |
$O(n)$ auxiliary??
|
| Multiplication |
Covanov and Thomé ( Multiplication) |
2015 |
$O(n \log n {2}^{O(\log*n)})$ |
$O(n)$ auxiliary??
|
| Multiplication |
Covanov and Thomé ( Multiplication) |
2016 |
$O(n \log n {2}^{({3} \log*n)})$ |
$O(n)$ auxiliary??
|
| Multiplication |
Harvey; Hoeven; Lecerf ( Multiplication) |
2018 |
$O(n \log n {2}^{({2} \log*n)})$ |
$O(n)$ auxiliary??
|
| Mutual Exclusion |
Lamport's bakery algorithm ( Mutual Exclusion) |
1974 |
$O(n)$ |
$O({1})$ per process, $O(n)$ total?
|
| Mutual Exclusion |
Szymanski's algorithm ( Mutual Exclusion) |
1988 |
$O(n)$ |
$O({1})$ per process, $O(n)$ total?
|
| Mutual Exclusion |
Taubenfeld's black-white bakery algorithm ( Mutual Exclusion) |
2004 |
$O(n)$ |
$O({1})$ per process, $O(n)$ total?
|
| Mutual Exclusion |
Maekawa's algorithm ( Mutual Exclusion) |
1985 |
$O(n^{0.5})$ |
$O({1})$ per process, $O(n)$ total?
|
| Mutual Exclusion |
Raymond's algorithm ( Mutual Exclusion) |
1997 |
$O(\log n)$? (originally this had $O(n)$) |
$O({1})$ per process, $O(n)$ total?
|
| Mutual Exclusion |
Suzuki-Kasami's algorithm ( Mutual Exclusion) |
1985 |
$O(n)$? (originally this had $O(logn)$) |
$O({1})$ per process, $O(n)$ total?
|
| Shown Surface Determination |
Painter's algorithm/Newell's algorithm ( Shown Surface Determination) |
1972 |
$O(n*log(n)$+np) |
$O(p+n)$
|
| Shown Surface Determination |
Warnock's algorithm ( Shown Surface Determination) |
1969 |
$O(np)$ |
$O(p+n)$?
|
| Shown Surface Determination |
Ray tracing ( Shown Surface Determination) |
1982 |
$O(np)$ |
$O(p+n)$?
|
| Shown Surface Determination |
Binary space partitioning (BSP) ( Shown Surface Determination) |
1969 |
$O(n^{2}+p)$? (previously said $O(n^{2}logn)$ |
$O(n^{2}+p)$?
|
| Shown Surface Determination |
Z-buffering ( Shown Surface Determination) |
1974 |
$O(np)$ |
$O(p+n)$
|
| Shown Surface Determination |
S-buffer/Scanline Rendering ( Shown Surface Determination) |
1980 |
$O(E+p)$? |
$O(p+n)$?
|
| Eigenpair with the Largest Eigenvalue |
Power Iteration (Eigenpair with the Largest Eigenvalue Eigenvalues (Iterative Methods)) |
1929 |
$O(n^{2})$ |
$O(n)$
|
| Delaunay Triangulation |
Fortune ( Delaunay Triangulation) |
1987 |
$O(n \log n)$ |
$O(n)$
|
| 1D Maximum Subarray |
Gries (1D Maximum Subarray Maximum Subarray Problem) |
1982 |
$O(n)$ |
$O({1})$ auxiliary
|
| 1D Maximum Subarray |
Bird (1D Maximum Subarray Maximum Subarray Problem) |
1989 |
$O(n)$ |
$O({1})$ auxiliary
|
| 1D Maximum Subarray |
Ferreira, Camargo, Song (1D Maximum Subarray Maximum Subarray Problem) |
2014 |
$O(\log n)$ |
$O(n)$ auxiliary
|
| Integer Relation |
HJLS algorithm ( Integer Relation) |
1986 |
$O(n^{3}(n+k))$ |
$O(n^{2})$ -- but requires infinite precision with large n or else it becomes unstable
|
| Dining Philosophers Problem |
Resource hierarchy solution (Dining Philosophers Problem Deadlock Avoidance) |
1965 |
$O({2}^n)$ |
$O(n)$
|
| Dining Philosophers Problem |
Arbitrator solution (Dining Philosophers Problem Deadlock Avoidance) |
1965 |
$O({2}^n)$ |
$O({1})$
|
| Approximate TSP |
Applegate et al. (Approximate TSP The Traveling-Salesman Problem) |
2006 |
$O(V^{2} E)$ |
-
|
| The Traveling-Salesman Problem |
Johnson; D. S.; McGeoch; L. A. ( The Traveling-Salesman Problem) |
1997 |
$O({2}^{(p(n)$}) |
-
|
| The Traveling-Salesman Problem |
Gutina; Gregory; Yeob; Anders; Zverovich; Alexey ( The Traveling-Salesman Problem) |
2002 |
- |
-
|
| Approximate TSP |
Rosenkrantz; D. J.; Stearns; R. E.; Lewis; P. M. (Approximate TSP The Traveling-Salesman Problem) |
1974 |
$O(V^{2})$ |
$O({1})$
|
| Approximate TSP |
Lin–Kernighan (Approximate TSP The Traveling-Salesman Problem) |
1981 |
$O(V^{2})$ |
$O(V)$
|
| De Novo Genome Assembly |
Overlap Layout Consensus (De Novo Genome Assembly De Novo Genome Assembly) |
1987 |
$O(n^{2})$ |
$O(n^{2})$?
|
| De Novo Genome Assembly |
Greedy SEQAID (De Novo Genome Assembly De Novo Genome Assembly) |
1984 |
$O(n^{2})$? |
$O(n^{2})$?
|
| Ray Tracing |
Dürer rendering algorithm ( Ray Tracing) |
1956 |
$O(n^{2})$ |
-
|
| Ray Tracing |
Appel's algorithm 1968 ( Ray Tracing) |
1968 |
$O(n^{2})$ |
-
|
| Ray Tracing |
Whitted's algorithm 1979 ( Ray Tracing) |
1979 |
$O(n^{2})$ |
-
|
| Ray Tracing |
J.-C. Nebel 1998 ( Ray Tracing) |
1998 |
$O(n^{2})$ |
-
|
| Ray Tracing |
A. Chalmers; T. Davis; and E. Reinhard 2002 ( Ray Tracing) |
2002 |
$O(n^{2})$ |
-
|
| Corner Detection |
Moravec's algorithm 1980 (Corner Detection Feature Detection) |
1980 |
$O(n^{3})$ |
-
|
| Corner Detection |
Förstner algorithm 1987 (Corner Detection Feature Detection) |
1987 |
$O(n^{2} \log^{2} n)$ |
-
|
| Corner Detection |
J. J. Koenderink and W. Richards 1988 (Corner Detection Feature Detection) |
1988 |
$O(n^{3})$ |
-
|
| Corner Detection |
Lindeberg (1994) (Corner Detection Feature Detection) |
1994 |
$O(n^{2})$ |
-
|
| Corner Detection |
Lindeberg (1998) (Corner Detection Feature Detection) |
1998 |
$O(n^{2})$ |
-
|
| Corner Detection |
K. Mikolajczyk; K. and C. Schmid LoG 2004 (Corner Detection Feature Detection) |
2004 |
$O(n^{2})$ |
-
|
| Corner Detection |
Lowe (2004) (Corner Detection Feature Detection) |
2004 |
$O(n^{2})$ |
-
|
| Corner Detection |
T. Lindeberg and J. Garding (1997) (Corner Detection Feature Detection) |
1997 |
$O(n^{2})$ |
-
|
| Corner Detection |
Lindeberg 2005 (Corner Detection Feature Detection) |
2005 |
$O(n^{2})$ |
-
|
| Corner Detection |
The Wang and Brady corner detection algorithm 1995 (Corner Detection Feature Detection) |
1995 |
$O(n^{2})$ |
-
|
| Corner Detection |
The Trajkovic and Hedley corner detector 1998 (Corner Detection Feature Detection) |
1998 |
$O(n^{2} log^{2} n)$ |
-
|
| Corner Detection |
FAST E. Rosten and T. Drummond 2006 (Corner Detection Feature Detection) |
2006 |
$O(n^{3})$ |
-
|
| Corner Detection |
Trujillo and Olague 2008 (Corner Detection Feature Detection) |
2008 |
$O(n^{2})$ |
-
|
| Corner Detection |
Geert Willems; Tinne Tuytelaars and Luc van Gool (2008) (Corner Detection Feature Detection) |
2008 |
$O(n^{2})$ |
-
|
| Corner Detection |
Tao Luo, Zaifeng Shi and Pumeng Wang (Corner Detection Feature Detection) |
2019 |
$O(n^{2})$ |
-
|
| Blob Detection |
T. Lindeberg DoG 2012 (Blob Detection Feature Detection) |
2012 |
$O(n^{2})$ |
-
|
| Blob Detection |
T. Lindeberg DoG 2015 (Blob Detection Feature Detection) |
2015 |
$O(n \log n)$ |
-
|
| Blob Detection |
SIFT Algorithm Lowe 2004 (Blob Detection Feature Detection) |
2004 |
$O(n^{3})$ |
-
|
| Blob Detection |
Hessain Determinant Lindeberg 1994 (Blob Detection Feature Detection) |
1994 |
$O(n^{3})$ |
-
|
| Blob Detection |
Hessain Determinant Lindeberg 1998 (Blob Detection Feature Detection) |
1998 |
$O(n^{3})$ |
-
|
| Blob Detection |
SURF Descriptor 2006 (Blob Detection Feature Detection) |
2006 |
$O(n^{2})$ |
-
|
| Blob Detection |
Hessian-Laplace Mikolajczyk and Schmid 2004 (Blob Detection Feature Detection) |
2004 |
$O(n^{3})$ |
-
|
| Blob Detection |
Spatio-temporal Geert Willems; Tinne Tuytelaars and Luc van Gool (2008) (Blob Detection Feature Detection) |
2008 |
$O(n^{2})$ |
-
|
| Blob Detection |
Lindeberg's watershed-based grey-level blob detection algorithm 1991 (Blob Detection Feature Detection) |
1991 |
$O(n^{3})$ |
-
|
| Blob Detection |
Maximally stable extremal regions Matas 2002 (Blob Detection Feature Detection) |
2002 |
$O(n^{2} log^{3} n)$ |
-
|
| Blob Detection |
A. Baumberg. 2000 (Blob Detection Feature Detection) |
2000 |
$O(n^{3})$ |
-
|
| Blob Detection |
Y. Dufournaud; C. Schmid; and R. Horaud 2000 (Blob Detection Feature Detection) |
2000 |
$O(n^{2} \log\log n)$ |
-
|
| Blob Detection |
local scale-invariant Lowe 1999 (Blob Detection Feature Detection) |
1999 |
$O(n^{3})$ |
-
|
| Blob Detection |
T. Tuytelaars and L. Van Gool 2000 (Blob Detection Feature Detection) |
2000 |
$O(n^{3})$ |
-
|
| Culling |
view frustum culling (Culling Culling) |
2008 |
$O(n^{2})$ |
-
|
| Culling |
Sector-Based Culling (Culling Culling) |
1991 |
$O(n^{2})$ |
-
|
| Culling |
Occlusion Culling (Culling Culling) |
1986 |
$O(n^{2})$ |
-
|
| Culling |
Contribution Culling (Culling Culling) |
1987 |
$O(n^{2})$ |
-
|
| Texture Synthesis |
Kwatra 2003 (Texture Synthesis Texture Synthesis) |
2003 |
$O(n^{3})$ |
-
|
| Texture Synthesis |
CNN Based Gatys; Leon A 2001 (Texture Synthesis Texture Synthesis) |
2001 |
$O(n^{3})$ |
-
|
| Diffuse Reflection |
P.Hanrahan and W.Krueger 1993 (Diffuse Reflection Texture Mapping) |
1993 |
$O(k n^{2})$ |
-
|
| Diffuse Reflection |
H.W.Jensen 2001 (Diffuse Reflection Texture Mapping) |
2001 |
$O(k^{3} n)$ |
-
|
| Diffuse Reflection |
He; X. D.; Torrance; K. E.; Sillion; 1991 (Diffuse Reflection Texture Mapping) |
1991 |
$O(k n^{2})$ |
-
|
| Diffuse Reflection |
Kajiya; J. Anisotropic Reflection Models 1985 (Diffuse Reflection Texture Mapping) |
1985 |
$O(k n^{2})$ |
-
|
| Diffuse Reflection |
Nakamae; E.; Kaneda; K.; Okamoto; T.; and Nishita 1990 (Diffuse Reflection Texture Mapping) |
1990 |
$O(k^{3} n^{2})$ |
-
|
| Diffuse Reflection |
Cabral; B.; Max; N.; and Springmeyer; R 1990 (Diffuse Reflection Texture Mapping) |
1990 |
$O(k n^{2})$ |
-
|
| Diffuse Reflection |
Westin; S. H.; Arvo; J. R.; and Torrance; K. E 1992 (Diffuse Reflection Texture Mapping) |
1992 |
$O(k n^{2})$ |
-
|
| Specular Reflection |
Phong (Specular Reflection Texture Mapping) |
1971 |
$O(n^{3})$ |
-
|
| Specular Reflection |
Blinn–Phong (Specular Reflection Texture Mapping) |
1977 |
$O(n^{3})$ |
-
|
| Specular Reflection |
Cook–Torrance (microfacets) (Specular Reflection Texture Mapping) |
1973 |
$O(n^{2})$ |
-
|
| Specular Reflection |
Ward anisotropic (Specular Reflection Texture Mapping) |
1989 |
$O(n^{1.{6}7} \log^{2} n)$ |
-
|
| Specular Reflection |
Hanrahan–Krueger (Specular Reflection Texture Mapping) |
1995 |
$O(n^{2} \log n)$ |
-
|
| Image Segmentation |
Linda G. Shapiro and George C. Stockman (2001) ( Image Segmentation) |
2001 |
$O(n^{2})$ |
-
|
| Image Segmentation |
Recursive Region Splitting ( Image Segmentation) |
1978 |
$O(n^{2})$ |
-
|
| Image Segmentation |
Barghout; Lauren Visual Taxometric approach ( Image Segmentation) |
2014 |
$O(n \log n)$ |
-
|
| Image Segmentation |
Dual clustering - Guberman ( Image Segmentation) |
2012 |
$O(n \log n)$ |
-
|
| Image Segmentation |
R. Nock and F. Nielsen Statistical Region Merging ( Image Segmentation) |
2004 |
$O(n^{2})$ |
-
|
| Image Segmentation |
Kass; Witkin and Terzopoulos ( Image Segmentation) |
1987 |
$O(n^{2})$ |
-
|
| Image Segmentation |
Chen's lambda-connected segmentation ( Image Segmentation) |
1991 |
$O(n \log n)$ |
-
|
| Image Segmentation |
S.L. Horowitz and T. Pavlidis - directed split and merge ( Image Segmentation) |
1974 |
$O(n^{2})$ |
-
|
| Image Segmentation |
David Mumford and Jayant Shah (1989) ( Image Segmentation) |
1989 |
$O(n^{2})$ |
-
|
| Image Segmentation |
Geman and Geman Markov random fields ( Image Segmentation) |
1984 |
$O(n^{2})$ |
-
|
| Image Segmentation |
Iterated conditional modes algorithm ( Image Segmentation) |
1986 |
$O(n^{2})$ |
-
|
| Image Segmentation |
watershed transformation 1979 ( Image Segmentation) |
1979 |
$O(n^{2})$ |
-
|
| Image Segmentation |
topological watershed ( Image Segmentation) |
1997 |
$O(n^{2})$ |
-
|
| Image Segmentation |
Florack and Kuijper ( Image Segmentation) |
2000 |
$O(n^{2})$ |
-
|
| Image Segmentation |
Bijaoui and Rué ( Image Segmentation) |
1995 |
$O(n^{2})$ |
-
|
| Image Segmentation |
Multi-scale MAP estimation - A. Bouman and M. Shapiro (2002) ( Image Segmentation) |
2002 |
$O(n^{2})$ |
-
|
| Image Segmentation |
Multiple Resolution segmentation - J. Liu and Y. H. Yang (1994) ( Image Segmentation) |
1994 |
$O(n^{2})$ |
-
|
| Image Segmentation |
Quasi-linear Topological watershed ( Image Segmentation) |
2005 |
$O(n \log n)$ |
-
|
| Image Segmentation |
Isometric graph partitioning - Leo Grady and Eric L. Schwartz (2006) ( Image Segmentation) |
2006 |
$O(n^{2})$ |
-
|
| Mesh Simplification |
Coplanar facets merging - M.J. De Haemer and M.J. Zyda 1991 (Mesh Simplification Mesh Simplification) |
1991 |
- |
-
|
| Mesh Simplification |
Coplanar facets merging - Hinker; P. and Hansen; C. 1993 (Mesh Simplification Mesh Simplification) |
1993 |
- |
-
|
| Mesh Simplification |
Coplanar facets merging - Kalvin; A. D.; Cutting; C. B.; Haddad; B. and Noz; M. E. 1991 (Mesh Simplification Mesh Simplification) |
1991 |
- |
-
|
| Mesh Simplification |
Coplanar facets merging - A.D. Kalvin and R.H. Taylor 1996 (Mesh Simplification Mesh Simplification) |
1996 |
- |
-
|
| Mesh Simplification |
Controlled vertex/edge/face decimation - M.E. Algorri and F. Schmitt 1996 (Mesh Simplification Mesh Simplification) |
1996 |
- |
-
|
| Mesh Simplification |
Controlled vertex/edge/face decimation - Guéziec 1996 (Mesh Simplification Mesh Simplification) |
1996 |
- |
-
|
| Mesh Simplification |
Controlled vertex/edge/face decimation - R. Ronfard and J. Rossignac 1996 (Mesh Simplification Mesh Simplification) |
1996 |
- |
-
|
| Mesh Simplification |
Controlled vertex/edge/face decimation - Hamann 1994 (Mesh Simplification Mesh Simplification) |
1994 |
- |
-
|
| Mesh Simplification |
Controlled vertex/edge/face decimation - Cohen; J.; Varshney; A 1996 (Mesh Simplification Mesh Simplification) |
1996 |
- |
-
|
| Mesh Simplification |
Re-tiling - Turk; G 1992 (Mesh Simplification Mesh Simplification) |
1992 |
- |
-
|
| Mesh Simplification |
Vertex clustering - Rossignac; J. and Borrel; P. 1993 (Mesh Simplification Mesh Simplification) |
1993 |
- |
-
|
| Mesh Simplification |
Vertex clustering - Low; K. L. and Tan; T. S 1997 (Mesh Simplification Mesh Simplification) |
1997 |
- |
-
|
| Mesh Simplification |
Vertex clustering - Reddy 1996 (Mesh Simplification Mesh Simplification) |
1996 |
- |
-
|
| Mesh Simplification |
Vertex clustering - Hoppe; H.; DeRose; T.; 1993 (Mesh Simplification Mesh Simplification) |
1993 |
- |
-
|
| Mesh Simplification |
Vertex clustering - Rossignac; J. and Borrel; P. 1997 (Mesh Simplification Mesh Simplification) |
1997 |
- |
-
|
| Mesh Simplification |
Wavelet-based - M.H. Gross; O.G. Staadt and R. Gatti 1996 (Mesh Simplification Mesh Simplification) |
1996 |
- |
-
|
| Mesh Simplification |
Wavelet-based - D.J. Hebert and H-J. Kim 1995 (Mesh Simplification Mesh Simplification) |
1995 |
- |
-
|
| Mesh Simplification |
Wavelet-based - Certain; A.; Popovic; J.; 1996 (Mesh Simplification Mesh Simplification) |
1996 |
- |
-
|
| Mesh Simplification |
Wavelet-based - Eck; M.; DeRose; T.; 1995 (Mesh Simplification Mesh Simplification) |
1995 |
- |
-
|
| Mesh Simplification |
Simplification via intermediate hierarchical rep-resentation - Andujar 1996 (Mesh Simplification Mesh Simplification) |
1996 |
- |
-
|
| Mesh Simplification |
Simplification via intermediate hierarchical rep-resentation - He; T.; Hong; L.; Kaufman 1995 (Mesh Simplification Mesh Simplification) |
1995 |
- |
-
|
| Mesh Simplification |
Simplification via intermediate hierarchical rep-resentation - He; T.; Hong; 1996 (Mesh Simplification Mesh Simplification) |
1996 |
- |
-
|
| POMDPs |
Hauskrecht; 2000; (POMDPs POMDPs) |
2000 |
- |
-
|
| POMDPs |
Pineau; Gordon; & Thrun; 2003; (POMDPs POMDPs) |
2003 |
- |
-
|
| POMDPs |
Braziunas & Boutilier; 2004; (POMDPs POMDPs) |
2004 |
- |
-
|
| POMDPs |
Poupart; 2005; (POMDPs POMDPs) |
2005 |
- |
-
|
| POMDPs |
Smith & Simmons; 2005; (POMDPs POMDPs) |
2005 |
- |
-
|
| POMDPs |
Spaan & Vlassis; 2005 (POMDPs POMDPs) |
2005 |
- |
-
|
| POMDPs |
Satia & Lave; 1973; (POMDPs POMDPs) |
1973 |
- |
-
|
| POMDPs |
Washington; 1997; (POMDPs POMDPs) |
1997 |
- |
-
|
| POMDPs |
Barto;Bradtke; & Singhe; 1995; (POMDPs POMDPs) |
1995 |
- |
-
|
| POMDPs |
Paquet; Tobin; & Chaib-draa; 2005; (POMDPs POMDPs) |
2005 |
- |
-
|
| POMDPs |
McAllester & Singh; 1999; (POMDPs POMDPs) |
1999 |
- |
-
|
| POMDPs |
Bertsekas & Castanon; 1999; (POMDPs POMDPs) |
1999 |
- |
-
|
| POMDPs |
Shani; Brafman; & Shimony; 2005 (POMDPs POMDPs) |
2005 |
- |
-
|
| Rasterization |
Digital Differential Analyzer (DDA) (Rasterization Rasterization) |
1983 |
$O(n)$ |
$O({1})$
|
| Rasterization |
Bresenham Algorithm (Rasterization Rasterization) |
1962 |
$O(n)$ |
$O({1})$
|
| Environment Mapping |
Blinn and Newell (Environment Mapping Texture Mapping) |
1976 |
- |
-
|
| Environment Mapping |
Nate Green (Environment Mapping Texture Mapping) |
1986 |
$O(n^{4})$ |
-
|
| Environment Mapping |
Sphere mapping (Environment Mapping Texture Mapping) |
1984 |
- |
-
|
| Environment Mapping |
Heidrich; W.; and H.-P. Seidel (Environment Mapping Texture Mapping) |
1998 |
$O(n^{3})$ |
-
|
| Environment Mapping |
Emil Praun (Environment Mapping Texture Mapping) |
2003 |
$O(n^{3})$ |
-
|
| Environment Mapping |
Mauro Steigleder (Environment Mapping Texture Mapping) |
2005 |
- |
-
|
| Environment Mapping |
HEALPix mapping Wong (Environment Mapping Texture Mapping) |
2008 |
$O(n^{2})$ |
-
|
| Occupancy Grid Mapping |
Maximum a Posteriori Occupancy Mapping (Occupancy Grid Mapping Occupancy Grid Mapping) |
2004 |
$O(n^{3})$ |
-
|
| SLAM Algorithms |
FastSlam (SLAM Algorithms SLAM Algorithms) |
2003 |
$O(m*\log n)$ per iteration |
$O(mn)$?
|
| SLAM Algorithms |
srba (SLAM Algorithms SLAM Algorithms) |
2002 |
$O(n^{2})$ |
$O(n^{2})$?
|
| Change-Making Problem |
Probabilistic Convolution Tree (Change-Making Problem Change-Making Problem) |
2014 |
$O(n \log n)$ |
$O(n log n)$
|
| Comparison Sorting |
Odd Even Sort Parallel Implementation (Comparison Sorting Sorting) |
1972 |
$O(n^{2})$ |
$O({1})$
|
| Non-Comparison Sorting |
Spaghetti Sort Parallel Implementation (Non-Comparison Sorting Sorting) |
1984 |
$O(n)$ |
$O({1})$ auxiliary? per processor?
|
| Approximate MCSP |
Heejo Lee; Jong Kim; Sungje Hong; and Sunggu Lee (Approximate MCSP Matrix Chain Multiplication) |
1997 |
$O(n^{2})$ |
$O(n^{2})$?
|
| Approximate MCOP |
Prakesh Ramanan (Approximate MCOP Matrix Chain Multiplication) |
1996 |
$O(log^{4} n)$ |
$O(n)$?
|
| Matrix Chain Scheduling Problem |
Czumaj (Matrix Chain Scheduling Problem Matrix Chain Multiplication) |
1993 |
$O(log^{3} n)$ |
$O(n^{2})$?
|
| LCS |
Hsu and Du (Scheme 2) (LCS Longest Common Subsequence) |
1984 |
$O(rm \log(n/r)$ + rm) |
$O(rm)$
|
| LCS |
Apostolico and Guerra (HS1 Algorithm) (LCS Longest Common Subsequence) |
1987 |
$O(m \log n +p \log({2}mn/p)$) |
$O(p + n)$
|
| LCS |
Kuo and Cross (LCS Longest Common Subsequence) |
1989 |
$O(p + n(r+\log n)$) |
$O(p + n)$
|
| LCS |
Rick (LCS Longest Common Subsequence) |
1995 |
$O(sn + \min\{r(n - r )$, rm\}) |
$O(sn + p)$
|
| LCS |
Rick (LCS Longest Common Subsequence) |
1995 |
$O(sn + \min\{rm, sd\})$ |
$O(sn + p)$
|
| LCS |
Hirschberg (LCS Longest Common Subsequence) |
1977 |
$O(rn + n \log n)$ |
$O(n + p)$
|
| LCS |
Hsu and Du (Scheme 1) (LCS Longest Common Subsequence) |
1984 |
$O(rm \log(n/m)$ + rm) |
$O(rm)$
|
| LCS |
Apostolico and Guerra (Algorithm 2) (LCS Longest Common Subsequence) |
1987 |
$O(rm + sn + n \log s)$ |
$O(p + sn)$
|
| LCS |
Chin and Poon (LCS Longest Common Subsequence) |
1991 |
$O(sn + \min\{sp, rm\})$ |
$O(p + n)$
|
| LCS |
Nakatsu et al. (LCS Longest Common Subsequence) |
1982 |
$O(n(m-r)$) |
$O(m^{2})$
|
| LCS |
Miller and Myers (LCS Longest Common Subsequence) |
1985 |
$O(n(m-r)$) |
$O(m^{2})$
|
| LCS |
Wu et al. (LCS Longest Common Subsequence) |
1990 |
$O(n(m-r)$) |
$O(m^{2})$?
|
| Maximum Flow |
Ahuja et al. ( Maximum Flow) |
1987 |
$O(VELog(V(LogU)$^{0.5} / E)) |
-
|
| 3-Graph Coloring |
Robson (3-Graph Coloring Graph Coloring) |
1986 |
$O({1.2108}^n)$ |
-
|
| 3-Graph Coloring |
Schöning (3-Graph Coloring Graph Coloring) |
1999 |
$O({1.333}^n)$ |
-
|
| 3-Graph Coloring |
Hirsch (3-Graph Coloring Graph Coloring) |
1998 |
$O({1.239}^n)$ |
-
|
| 3-Graph Coloring |
Johnson (3-Graph Coloring Graph Coloring) |
1988 |
$O({1.4422}^n)$ |
-
|
| 3-Graph Coloring |
Alon and Kahale (3-Graph Coloring Graph Coloring) |
1997 |
$O({1.24}^n)$ |
-
|
| Convex Hull |
Incremental convex hull algorithm; Michael Kallay ( Convex Hull) |
1984 |
$O(n \log n)$ |
-
|
| Undirected, General MST |
Bader & Cong Parallel Implementation (Undirected, General MST Minimum Spanning Tree (MST)) |
2006 |
$O(E \log(V)$/p) |
$O(V)$ total
|
| First Category Integer Factoring |
Special number field sieve (First Category Integer Factoring Integer Factoring) |
1940 |
$O(exp(({1}+o({1})$)({32}n/{9})^{({1}/{3})}(log n)^{({2}/{3})}) heuristically? |
$O(n^{2/3})$
|
| Second Category Integer Factoring |
General number field sieve (Second Category Integer Factoring Integer Factoring) |
1996 |
$O(exp(({1}+o({1})$)({64}n/{9})^{({1}/{3})}(log n)^{({2}/{3})}) heuristically? |
$O(n^{2/3})$
|
| Second Category Integer Factoring |
Shor's algorithm Quantum Implementation (Second Category Integer Factoring Integer Factoring) |
1994 |
$O(n)$ |
$O(n)$
|
| Single String Search |
Two-way String-Matching Algorithm (Single String Search String Search) |
1991 |
$O(n + m)$ |
$O({1})$
|
| Single String Search |
String-Matching with Finite Automata (Single String Search String Search) |
1940 |
$O(mn)$ |
$O(m)$
|
| Single String Search |
Quick-Skip Searching (Single String Search String Search) |
2012 |
$O(mn)$ |
$O(m)$
|
| Single String Search |
Fast Hybrid Algorithm (Single String Search String Search) |
2017 |
$O(n+m)$+ $O(m+s)$ |
$O(m)$
|
| Single String Search |
Backward Non-Deterministic DAWG Matching (BNDM) (Single String Search String Search) |
1998 |
$O(n+m)$ |
$O(sm)$
|
| Multiple String Search |
Commentz-Walter Algorithm (Multiple String Search String Search) |
1979 |
$O(mn)$ |
$O(km)$
|
| Multiple String Search |
Aho–Corasick (AC) Algorithm (Multiple String Search String Search) |
1975 |
$O(n + m + z)$ |
$O(km)$
|
| Single String Search |
Boyer-Moore-Horspool (BMH) (Single String Search String Search) |
1980 |
$O(mn + s)$ |
$O(s)$
|
| Single String Search |
Raita Algorithm (Single String Search String Search) |
1991 |
$O(mn + s)$ |
$O(s)$
|
| Single String Search |
BOM (Backward Oracle Matching) (Single String Search String Search) |
1999 |
$O(m)$ + $O(mn)$ |
$O(m)$
|
| Single String Search |
Apostolico–Giancarlo Algorithm (Single String Search String Search) |
1986 |
$O(m + s)$ + $O(n)$ |
$O(m)$
|
| Edit Sequence, constant-size alphabet |
Gapped BLAST (Edit Sequence, constant-size alphabet Sequence Alignment) |
1997 |
$O(mn)$ |
$O(mn)$?
|
| Edit Sequence, constant-size alphabet |
Basic Local Alignment Search Tool (BLAST) (Edit Sequence, constant-size alphabet Sequence Alignment) |
1990 |
$O(mn)$ |
$O(mn)$?
|
| Joins |
Nested loop join ( Joins) |
1960 |
$O(nm)$ |
$O({1})$
|
| Joins |
Sort merge join ( Joins) |
1960 |
$O(nlogn + mlogm)$ |
$O(n+m)$?
|
| Joins |
Hash join ( Joins) |
1960 |
$O(n+m)$ |
$O(n+m)$?
|
| Bipartite Graph MCM |
Ford–Fulkerson algorithm (Bipartite Graph MCM Maximum Cardinality Matching) |
1956 |
$O(VE)$ |
$O(E)$
|
| Bipartite Graph MCM |
Hopcroft–Karp algorithm (Bipartite Graph MCM Maximum Cardinality Matching) |
1973 |
$O((V^{0.5})$E) |
$O(V)$
|
| Bipartite Graph MCM |
Mucha; Sankowski (planar) (Bipartite Graph MCM Maximum Cardinality Matching) |
2006 |
$O(V^{(\omega/{2})$}) where omega is the exponent on matrix multiplication |
$O(V \log V)$???
|
| Bipartite Graph MCM |
Madry's algorithm (Bipartite Graph MCM Maximum Cardinality Matching) |
2013 |
$O(E^{10/7}*polylog(V)$) |
$O(E + V)$
|
| Bipartite Graph MCM |
Chandran and Hochbaum (Bipartite Graph MCM Maximum Cardinality Matching) |
2011 |
$O(min(V*k, E)$+sqrt(k)*min(k^{2}, E)) |
$O(E)$??
|
| General Graph MCM |
Blum (General Graph MCM Maximum Cardinality Matching) |
1990 |
$O((V^{0.5})$E) |
$O(E)$??
|
| General Graph MCM |
Gabow; Tarjan (General Graph MCM Maximum Cardinality Matching) |
1991 |
$O((V^{0.5})$E) |
$O(E)$?
|
| General Graph MCM |
Mucha, Sankowski (general) (General Graph MCM Maximum Cardinality Matching) |
2004 |
$O(V^{2.{37}6})$ |
$O(V^{2})$??
|
| Planar Bipartite Graph Perfect Matching |
Klein (section 5) (Planar Bipartite Graph Perfect Matching Maximum Cardinality Matching) |
1997 |
$O(V^{({4}/{3})$} logV) |
$O(V^{({4}/{3})$})?
|
| Key Exchange |
Diffie–Hellman key exchange (Key Exchange Key Exchange) |
1978 |
$O(mult(n)$*n) where mult(n) is running time on n-bit multiplication |
$O(n)$
|
| Key Exchange |
Elliptic-curve Diffie-Hellman (ECDH) (Key Exchange Key Exchange) |
2006 |
$O(mult(n)$*n^{2})? where mult(n) is running time on n-bit multiplication |
$O(n)$
|
| 2-thread Mutual Exclusion |
Dekker's algorithm (2-thread Mutual Exclusion Mutual Exclusion) |
1963 |
$O(n)$ |
-
|
| Mutual Exclusion |
Peterson's algorithm ( Mutual Exclusion) |
1981 |
$O(n)$ |
$O(n)$ total
|
| Mutual Exclusion |
Naimi-Trehel's algorithm ( Mutual Exclusion) |
1996 |
$O(\log n)$ |
$O({1})$ per process, $O(n)$ total?
|
| Mutual Exclusion |
Chan-Singhal-Liu ( Mutual Exclusion) |
1990 |
$O(\log n)$ |
$O({1})$ per process, $O(n)$ total?
|
| Inexact Laplacian Solver |
Spielman, Teng (Inexact Laplacian Solver SDD Systems Solvers) |
2004 |
$O(m \log^c n)$ |
$O(n)$
|
| Inexact Laplacian Solver |
Vaidya (Inexact Laplacian Solver SDD Systems Solvers) |
1990 |
$O(mn^{({3}/{4})$}) |
$O(n)$
|
| Inexact Laplacian Solver |
Gremban; Miller; Zagha (Inexact Laplacian Solver SDD Systems Solvers) |
1995 |
$O(n^{2})$ |
$O(n^{2})$
|
| Inexact Laplacian Solver |
Bern; Gilbert; Hendrickson (Inexact Laplacian Solver SDD Systems Solvers) |
2006 |
$O(n \log \log n)$ |
-
|
| Inexact Laplacian Solver |
Boman; Hendrickson (Inexact Laplacian Solver SDD Systems Solvers) |
2003 |
$\tilde{O}(mn^{({1}/{2})})$ |
-
|
| Inexact Laplacian Solver |
Boman; Chen; Hendrickson; Toledo (Inexact Laplacian Solver SDD Systems Solvers) |
2004 |
$O(n \log({1}/ϵ)$ ) |
$O(n)$
|
| Inexact Laplacian Solver |
Koutis; Miller and Peng (Inexact Laplacian Solver SDD Systems Solvers) |
2010 |
$\tilde{O}(m \log n)$ |
$O(n)$
|
| Inexact Laplacian Solver |
Koutis; Miller and Peng (Inexact Laplacian Solver SDD Systems Solvers) |
2011 |
$\tilde{O}(m \log n)$ |
$O(n)$
|
| Inexact Laplacian Solver |
Blelloch; Koutis; Miller; Tangwongsan (Inexact Laplacian Solver SDD Systems Solvers) |
2010 |
$O(n \log n)$ |
m + $O(n/\log n)$
|
| SDD Systems Solvers |
Briggs; Henson; McCormick ( SDD Systems Solvers) |
2000 |
$O(n^{1.{2}5} \log \log n)$ |
-
|
| Inexact Laplacian Solver |
Kelner; Orecchia; Sidford; Zhu (Inexact Laplacian Solver SDD Systems Solvers) |
2013 |
$O(m \log^{2} (n)$ \log \log n) |
$O(n)$
|
| Inexact Laplacian Solver |
Lee; Peng; Spielman (Inexact Laplacian Solver SDD Systems Solvers) |
2015 |
$O(n)$ |
$O(n)$
|
| Inexact Laplacian Solver |
Daitch; Spielman (Inexact Laplacian Solver SDD Systems Solvers) |
2007 |
$O(n^{5/4} (\log^{2} (n)$ \log\log n)^{3/4} \log({1}/ϵ)) |
$O(n)$
|
| Exact Laplacian Solver |
Gaussian Elimination (Exact Laplacian Solver SDD Systems Solvers) |
-150 |
$O(n^{3})$ |
$O(n^{2})$
|
| Exact Laplacian Solver |
Naive Implementation (Exact Laplacian Solver SDD Systems Solvers) |
1940 |
$O(n!)$ |
$O(n^{2})$
|
| Cycle Detection |
Floyd's tortoise and hare algorithm ( Cycle Detection) |
1967 |
$O((\lambda + \mu)$ t_f) |
$O({1})$
|
| Cycle Detection |
Brent's algorithm ( Cycle Detection) |
1973 |
$O((\lambda + \mu)$ t_f) |
$O({1})$
|
| Cycle Detection |
Gosper's algorithm ( Cycle Detection) |
1978 |
$O((\lambda + \mu)$ log(\lambda + \mu) t_f) |
\Theta(log(\mu + \lambda))
|
| General Permutations |
Fisher–Yates/Knuth shuffle (General Permutations Generating Random Permutations) |
1938 |
$O(n^{2})$ |
$O(n)$
|
| General Permutations |
Durstenfeld's Algorithm 235 (General Permutations Generating Random Permutations) |
1964 |
$O(n)$ |
$O({1})$
|
| General Permutations |
Radix sorting method (General Permutations Generating Random Permutations) |
1887 |
$O(n)$ |
$O(n)$
|
| Cyclic Permutations |
Sattolo's algorithm (Cyclic Permutations Generating Random Permutations) |
1986 |
$O(n)$ |
$O({1})$
|
| ILP;MILPs |
Gomory's cutting method (ILP;MILPs Convex Optimization (Non-linear)) |
1953 |
$O({2}^n*poly(n, m)$)? (previously $O(n^{3})$) |
$O(nm+m^{2})$
|
| General, Constrained optimization |
Wolfe; Lemaréchal; Kiwiel (General, Constrained optimization Convex Optimization (Non-linear)) |
1964 |
$O(n^{4})$ |
$O(n+L)$??
|
| General, Constrained optimization |
Ellipsoid method (General, Constrained optimization Convex Optimization (Non-linear)) |
1971 |
$O(n^{2} \log n)$ |
$O(nmL)$
|
| General, Constrained optimization |
Subgradient method (General, Constrained optimization Convex Optimization (Non-linear)) |
1981 |
$O(n^{2} )$ |
$O(n+L)$?
|
| Stochastic optimization |
Dual subgradients and the drift-plus-penalty method (Stochastic optimization Convex Optimization (Non-linear)) |
1993 |
$O(n^{2})$ |
$O(Vmn)$????
|
| Gröbner Bases |
Buchberger's algorithm (Gröbner Bases Gröbner Bases) |
1976 |
d^{({2}^{(n+o({1})})}) |
d^{({2}^{(n+o({1}))})}??
|
| Gröbner Bases |
Faugère F4 algorithm (Gröbner Bases Gröbner Bases) |
1999 |
$O(C(n+D_{reg}, D_{reg})$^{\omega}) where omega is the exponent on matrix multiplication |
$O(C(n+D_{reg}, D_{reg})$^{2})?
|
| Gröbner Bases |
Faugère F5 algorithm (Gröbner Bases Gröbner Bases) |
2002 |
$O(C(n+D_{reg}, D_{reg})$^{\omega}) where omega is the exponent on matrix multiplication |
$O(C(n+D_{reg}, D_{reg})$^{2})?
|
| Minimum value in each row of an implicitly-defined totally monotone matrix |
Naive algorithm ( Minimum value in each row of an implicitly-defined totally monotone matrix) |
1940 |
$O(mn)$ |
$O({1})$
|
| Minimum value in each row of an implicitly-defined totally monotone matrix |
SMAWK algorithm ( Minimum value in each row of an implicitly-defined totally monotone matrix) |
1987 |
$O(n({1}+\log(n/m)$)) |
$O(n)$?
|
| All Permutations |
Steinhaus–Johnson–Trotter algorithm (All Permutations All Permutations) |
1963 |
$O(n)$ on specific permutations |
$O({1})$
|
| All Permutations |
Tompkins–Paige algorithm (All Permutations All Permutations) |
1956 |
$O(n)$ on specific permutations |
$O(n)$
|
| All Permutations |
Heap's algorithm (All Permutations All Permutations) |
1963 |
$O(n)$ per permutation |
$O(n)$
|
| Alphabetic Tree Problem |
Garsia–Wachs algorithm (Alphabetic Tree Problem Optimal Binary Search Trees) |
1977 |
$O(n \log n)$ |
$O(n)$
|
| Alphabetic Tree Problem |
Hu–Tucker algorithm (Alphabetic Tree Problem Optimal Binary Search Trees) |
1971 |
$O(n \log n)$ |
$O(n)$
|
| OBST |
Modified Knuth's DP algorithm (OBST Optimal Binary Search Trees) |
1970 |
$O(n^{2})$ |
$O(n^{2})$
|
| OBST |
Knuth's DP algorithm (OBST Optimal Binary Search Trees) |
1970 |
$O(n^{3})$ |
$O(n^{2})$
|
| OBST |
Naive algorithm (OBST Optimal Binary Search Trees) |
1940 |
$O({4}^n /n \sqrt{n})$ |
$O({1})$
|
| OBST |
Yao (OBST Optimal Binary Search Trees) |
1982 |
$O(n^{2})$ |
$O(n^{2})$
|
| Approximate OBST |
Levcopoulos; Lingas; Sack (Approximate OBST Optimal Binary Search Trees) |
1989 |
$O(n)$ |
$O(n)$
|
| Approximate OBST |
de Prisco (Approximate OBST Optimal Binary Search Trees) |
1993 |
$O(n)$ |
$O(n)$
|
| 2-player |
Lemke–Howson algorithm (2-player Nash Equilibria) |
1964 |
{2}^{($O(n+m)$)} (previously $O(n^{4})$????) |
$O(mn)$?
|
| 2-player |
Lipton; Mehta (2-player Nash Equilibria) |
2003 |
$O(n^{(O(log n)$)} (previously $O(n^{2} logn)$????) |
(see sheet {2})
|
| Bipartite Maximum-Weight Matching |
Hungarian algorithm (Bipartite Maximum-Weight Matching Maximum-Weight Matching) |
1955 |
$O(n^{4})$ |
$O(n^{2})$
|
| Maximum-Weight Matching |
Edmonds (Maximum-Weight Matching Maximum-Weight Matching) |
1965 |
$O(mn^{2})$ |
$O(mn^{2})$??
|
| Maximum-Weight Matching |
Micali; Vazirani ( Maximum-Weight Matching) |
1980 |
$O(n^{3} \log n)$ |
-
|
| Maximum-Weight Matching |
Mucha and Sankowski ( Maximum-Weight Matching) |
2004 |
$O(n^{3})$ |
-
|
| Constructing Eulerian Trails in a Graph |
Fleury's algorithm + Tarjan (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) |
1974 |
$O(E^{2})$ |
$O(E)$
|
| Constructing Eulerian Trails in a Graph |
Hierholzer's algorithm (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) |
1873 |
$O(E)$ |
$O(E)$
|
| Constructing Eulerian Trails in a Graph |
Fleury's algorithm + Thorup (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) |
2000 |
$O(E \log^{3}(E)$ \log\log E) |
$O(E)$
|
| Discrete Fourier Transform |
Naive algorithm (Discrete Fourier Transform Discrete Fourier Transform) |
1965 |
$O(n^{2})$ |
$O({1})$
|
| Discrete Fourier Transform |
Cooley–Tukey algorithm (Discrete Fourier Transform Discrete Fourier Transform) |
1965 |
$O(n \log n)$ |
$O(n)$?
|
| Discrete Fourier Transform |
Rader–Brenner algorithm (Discrete Fourier Transform Discrete Fourier Transform) |
1976 |
$O(n \log n)$ |
$O(n)$?
|
| Discrete Fourier Transform |
Bruun's FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform) |
1978 |
$O(n \log n)$ |
$O(n)$?
|
| Discrete Fourier Transform |
Yavne Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform) |
1968 |
$O(n \log n)$ |
$O(n)$?
|
| Discrete Fourier Transform |
Gentleman; Morven and Gordon Sande radix-4 algorithm (Discrete Fourier Transform Discrete Fourier Transform) |
1966 |
$O(n \log n)$ |
$O(n)$?
|
| Discrete Fourier Transform |
Bergland; Glenn radix-8 algorithm (Discrete Fourier Transform Discrete Fourier Transform) |
1969 |
$O(n \log n)$ |
$O(n)$
|
| Discrete Fourier Transform |
Extended Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform) |
2001 |
$O(n \log n)$ |
$O(n)$?
|
| Discrete Fourier Transform |
Von zur Gathen-Gerhard additive FFT (Discrete Fourier Transform Discrete Fourier Transform) |
1996 |
$O(n (\log n)$^{2}) |
$O(n)$
|
| Discrete Fourier Transform |
Wang-Zhu-Cantor additive FFT (Discrete Fourier Transform Discrete Fourier Transform) |
1988 |
$O(n(\log n)$^{1.{58}5}) |
$O(n)$?
|
| Discrete Fourier Transform |
Gao’s additive FFT (Discrete Fourier Transform Discrete Fourier Transform) |
2010 |
$O(n logn loglogn)$ |
$O(n)$
|
| Line Drawing |
Naive algorithm (Line Drawing Line Drawing) |
1940 |
$O(n)$ |
$O({1})$
|
| Line Drawing |
Digital Differential Analyzer (Line Drawing Line Drawing) |
1940 |
$O(n)$ |
$O({1})$
|
| Line Drawing |
Bresenham's line algorithm (Line Drawing Line Drawing) |
1965 |
$O(n)$ |
$O({1})$
|
| Line Drawing |
Xiaolin Wu's line algorithm (Line Drawing Line Drawing) |
1991 |
$O(n)$ |
$O({1})$
|
| Line Drawing |
Gupta-Sproull algorithm (Line Drawing Line Drawing) |
1981 |
$O(n)$ |
$O({1})$
|
| Polygon Clipping with Arbitrary Clipping Polygon |
Greiner–Hormann clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) |
1998 |
$O(n^{2})$ ? |
$O(n^{2})$?
|
| Polygon Clipping with Convex Clipping Polygon |
Sutherland–Hodgman algorithm (Polygon Clipping with Convex Clipping Polygon Polygon Clipping) |
1974 |
$O(n^{2})$ |
$O(n)$
|
| Polygon Clipping with Arbitrary Clipping Polygon |
Vatti clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) |
1992 |
$O(n^{2})$ ? |
$O(n^{2})$?
|
| Polygon Clipping with Arbitrary Clipping Polygon |
Weiler–Atherton clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) |
1977 |
$O(n^{2})$ |
$O(n^{2})$?
|
| Eigenpair closest to mu; Any eigenpair; Any eigenvalue |
Inverse iteration (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) |
1921 |
$O(n^{2})$ |
$O(n^{2})$
|
| Any eigenpair; Any eigenvalue |
Rayleigh quotient iteration (Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) |
1940 |
$O(n^{2})$ |
$O(n^{2})$
|
| Eigenpair closest to mu; Any eigenpair; Any eigenvalue |
LOBPCG algorithm (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) |
1948 |
$O(n^{2})$ |
$O(n)$?
|
| Any eigenvalue |
Bisection method (Any eigenvalue Eigenvalues (Iterative Methods)) |
1985 |
$O(n^{2})$ |
$O(n^{2})$?
|
| Any eigenvalue |
Laguerre iteration (Any eigenvalue Eigenvalues (Iterative Methods)) |
1940 |
$O(n^{2})$ |
$O(n^{2})$?
|
| All eigenvalues; Any eigenvalue |
QR algorithm (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) |
1962 |
$O(n^{2})$ |
$O(n^{2})$
|
| All eigenvalues; Any eigenvalue |
Jacobi eigenvalue algorithm (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) |
1846 |
$O(n^{2})$ |
$O(n^{2})$?
|
| All eigenvalues; Any eigenvalue |
Divide-and-conquer (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) |
1986 |
$O(n \log n)$ |
$O(n^{2})$
|
| All eigenpairs; Eigenpair closest to mu; Any eigenpair; Any eigenvalue; All eigenvalues |
Homotopy method (All eigenpairs; Eigenpair closest to mu; Any eigenpair; Any eigenvalue; All eigenvalues Eigenvalues (Iterative Methods)) |
1992 |
$O(n^{2})$ |
$O(n^{2})$??
|
| Eigenpair closest to mu; Any eigenpair; Any eigenvalue |
Folded spectrum method (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) |
1934 |
$O(n^{2})$ |
$O(n)$?
|
| Any eigenpair; Any eigenvalue |
MRRR algorithm (Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) |
1999 |
$O(n)$ |
$O(n^{2})$
|
| General Root Computation |
Bisection method (General Root Computation Root Computation) |
1820 |
$O(n_{max})$ |
$O({1})$
|
| General Root Computation |
False position method (General Root Computation Root Computation) |
1690 |
$O(n_{max})$ |
$O({1})$
|
| Root Computation with continuous first derivative |
Newton's method (Root Computation with continuous first derivative Root Computation) |
1940 |
$O(n_{max})$ |
$O({1})$
|
| Root Computation with continuous second derivative |
Halley's method (Root Computation with continuous second derivative Root Computation) |
1940 |
$O(n_{max})$ |
$O({1})$
|
| General Root Computation |
Secant method (General Root Computation Root Computation) |
1940 |
$O(n_{max})$ |
$O({1})$
|
| General Root Computation |
Ridder's method (General Root Computation Root Computation) |
1979 |
$O(n_{max})$ |
$O({1})$
|
| General Root Computation |
Muller's method (General Root Computation Root Computation) |
1956 |
$O(n_{max})$ |
$O({1})$
|
| Coset Enumeration |
Todd–Coxeter algorithm (Coset Enumeration Coset Enumeration) |
1936 |
$O({2}^n)$ |
$O(gkc)$
|
| Coset Enumeration |
Haselgrove-Leech-Trotter (HLT) algorithm (Coset Enumeration Coset Enumeration) |
1940 |
$O({2}^n)$ |
$O(ng)$?
|
| Coset Enumeration |
Knuth–Bendix algorithm (Coset Enumeration Coset Enumeration) |
1970 |
$O({1.5}^n n^{2} logn)$ |
$O(ng)$???
|
| Maximum Likelihood Parameters |
Expectation–maximization (EM) algorithm ( Maximum Likelihood Parameters) |
1977 |
$O(n^{3})$ |
$O(n+r)$?
|
| Maximum Likelihood Parameters |
Newton–Raphson algorithm ( Maximum Likelihood Parameters) |
1685 |
$O(n^{3})$ |
$O(n+r^{2})$?
|
| Maximum Likelihood Parameters |
Parameter-expanded expectation maximization (PX-EM) algorithm ( Maximum Likelihood Parameters) |
1998 |
$O(n^{3})$ |
$O(n+r)$?
|
| Maximum Likelihood Parameters |
Expectation conditional maximization (ECM) ( Maximum Likelihood Parameters) |
2017 |
$O(n^{2} \log n)$ |
$O(n+r)$?
|
| Maximum Likelihood Parameters |
Generalized expectation maximization (GEM) algorithm ( Maximum Likelihood Parameters) |
1994 |
$O(n^{4} \log^{0.1}(.{5}n)$) |
$O(n+r)$?
|
| Maximum Likelihood Parameters |
α-EM algorithm ( Maximum Likelihood Parameters) |
2003 |
$O(n^{3})$ |
$O(n+r)$?
|
| Cardinality Estimation |
Naive solution ( Cardinality Estimation) |
1940 |
$O(N)$ |
$O(n)$
|
| Cardinality Estimation |
Flajolet–Martin algorithm ( Cardinality Estimation) |
1984 |
$O(N)$ |
$O(log n)$
|
| Cardinality Estimation |
LogLog algorithm ( Cardinality Estimation) |
2003 |
$O(N)$ |
$O(log(log(n)$))
|
| Cardinality Estimation |
HyperLogLog algorithm ( Cardinality Estimation) |
2007 |
$O(N)$ |
$O(eps^{-2}*log(log(n)$))+log(n))
|
| Cardinality Estimation |
HyperLogLog++ ( Cardinality Estimation) |
2014 |
$O(N)$ |
$O(eps^{-2}*log(log(n)$))+log(n))
|
| streaming |
Min/max sketches streaming algorithm (streaming Cardinality Estimation) |
1980 |
$O(N)$ |
$O({1})$
|
| streaming |
Bottom-m sketches streaming algorithm (streaming Cardinality Estimation) |
1980 |
$O(N)$ |
$O(m)$
|
| Global Register Allocation |
Chaitin's Algorithm (Global Register Allocation Register Allocation) |
1981 |
$O(n^{2})$ |
$O(n^{2})$
|
| Global Register Allocation |
Chow's Algorithm (Global Register Allocation Register Allocation) |
1984 |
$O(n^{2})$ |
$O(n^{2})$
|
| Global Register Allocation |
Linear Scan, Poletto & Sarkar (Global Register Allocation Register Allocation) |
1999 |
$O(n)$ |
$O(r)$
|
| Register Allocation |
Cooper and Dasgupta algorithm ( Register Allocation) |
1983 |
$O(n^{2})$ |
-
|
| Global Register Allocation |
Optimal Register Allocation (ORA), Goodwin & Wilken Algorithm (Global Register Allocation Register Allocation) |
1996 |
$O(n^{3})$ |
Depends on the choice of {0}-{1} ILP solver
|
| Global Register Allocation |
Kong and Wilken Algorithm (Global Register Allocation Register Allocation) |
1998 |
$O(n^{3})$ |
? Probably also dependent on the ILP solver
|
| Voronoi Diagrams |
Fortune's algorithm (Voronoi Diagrams Voronoi Diagrams) |
1986 |
$O(n \log n)$ |
$O(n)$
|
| Voronoi Diagrams |
Linde–Buzo–Gray algorithm ( Voronoi Diagrams) |
1980 |
$O(n \log n)$ |
-
|
| Voronoi Diagrams |
Bowyer–Watson algorithm (Voronoi Diagrams Voronoi Diagrams) |
1981 |
$O(n \log n)$ |
$O(n)$
|
| Variance Calculations |
Naïve algorithm ( Variance Calculations) |
1940 |
$O(n)$ |
$O({1})$
|
| Variance Calculations |
Two-pass algorithm ( Variance Calculations) |
1940 |
$O(n)$ |
$O({1})$
|
| Variance Calculations |
Welford's Online algorithm ( Variance Calculations) |
1962 |
$O(n)$ |
$O({1})$
|
| Variance Calculations |
Weighted incremental algorithm ( Variance Calculations) |
1979 |
$O(n)$ |
$O({1})$
|
| Variance Calculations |
Chan's algorithm Parallel Implementation ( Variance Calculations) |
1979 |
$O(\log n)$ |
$O({1})$ per processor
|
| Topological Sorting |
Kahn's algorithm (Topological Sorting Topological Sorting) |
1962 |
$O(V+E)$ |
$O(V)$
|
| Topological Sorting |
Tarjan's DFS based algorithm (Topological Sorting Topological Sorting) |
1976 |
$O(V+E)$ |
$O(V)$?
|
| Topological Sorting |
Dekel; Nassimi & Sahni Parallel Implementation (Topological Sorting Topological Sorting) |
1981 |
$O(\log^{2} V)$ |
$O(V^{2})$??
|
| DFA Minimization |
Hopcroft's algorithm (DFA Minimization DFA Minimization) |
1971 |
$O(kn \log n)$ |
$O(kn)$
|
| DFA Minimization |
Moore's algorithm (DFA Minimization DFA Minimization) |
1956 |
$O(n^{2} k)$ |
$O(n)$
|
| DFA Minimization |
Brzozowski's algorithm (DFA Minimization DFA Minimization) |
1963 |
$O({2}^n)$ |
$O({2}^n)$
|
| Acyclic DFA Minimization |
Revuz's algorithm (Acyclic DFA Minimization DFA Minimization) |
1992 |
$O(n)$ |
$O(n)$
|
| Cyclic Nontrivial SCCs DFA Minimization |
Almeida & Zeitoun (Cyclic Nontrivial SCCs DFA Minimization DFA Minimization) |
2008 |
$O(n)$ |
$O(n)$
|
| Off-Line Lowest Common Ancestor |
Tarjan's off-line lowest common ancestors algorithm (Off-Line Lowest Common Ancestor Lowest Common Ancestor) |
1984 |
$O(n+m)$ |
$O(n)$
|
| Lowest Common Ancestor with Static Trees |
Schieber; Vishkin (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) |
1988 |
$O(n+m)$ |
$O(n)$
|
| Lowest Common Ancestor with Static Trees |
Berkman; Vishkin (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) |
1993 |
$O(n+m)$ ? |
$O(n)$
|
| Lowest Common Ancestor with Static Trees |
[[Bender; Colton (LCA <=> RMQ) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor)]] |
2000 |
$O(n+m)$ |
$O(n)$
|
| Lowest Common Ancestor with Static Trees |
Stephen Alstrup, Cyril Gavoille, Haim Kaplan & Theis Rauhe (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) |
2004 |
$O(n+m)$ |
$O(n)$
|
| Exact GED |
X Chen (Exact GED Graph Edit Distance Computation) |
2019 |
$O(VS)$ |
$O(wV^{2})$
|
| Inexact GED |
Y Bai (Inexact GED Graph Edit Distance Computation) |
2018 |
$O(V^{2})$ |
$O(V^{2})$
|
| Inexact GED |
L Chang (Inexact GED Graph Edit Distance Computation) |
2017 |
$O(V E^{2} logV)$ |
$O(V)$
|
| Inexact GED |
K Riesen (Inexact GED Graph Edit Distance Computation) |
2013 |
$O(V^{2})$ |
$O(V)$
|
| Graph Edit Distance Computation |
Alberto Sanfeliu and King-Sun Fu ( Graph Edit Distance Computation) |
1983 |
$O(V^{3} E^{2})$ |
-
|
| Inexact GED |
Neuhaus, Riesen, Bunke (Inexact GED Graph Edit Distance Computation) |
2006 |
$O(V^{2})$ |
$O(wV)$
|
| Graph Edit Distance Computation |
Wang Y-K; Fan K-C; Horng J-T ( Graph Edit Distance Computation) |
1997 |
$O(V E^{2} \log \log E)$ |
-
|
| Graph Edit Distance Computation |
Tao D; Tang X; Li X et al ( Graph Edit Distance Computation) |
2006 |
$O(V^{2})$ |
-
|
| Inexact GED |
Finch (Inexact GED Graph Edit Distance Computation) |
1998 |
$O(V^{2} E)$ |
$O(V^{2})$?
|
| Enumerating Maximal Cliques, arbitrary graph |
Bron–Kerbosch algorithm (Enumerating Maximal Cliques, arbitrary graph Clique Problems) |
1973 |
$O({3}^{(n/{3})})$ |
$O(n^{2})$?
|
| Enumerating Maximal Cliques, arbitrary graph |
Akkoyunlu; E. A. (Enumerating Maximal Cliques, arbitrary graph Clique Problems) |
1973 |
$O({3}^{(n/{3})$}) |
$O(n^{2})$?
|
| Enumerating Maximal Cliques, arbitrary graph |
Tomita; Tanaka & Takahashi (Enumerating Maximal Cliques, arbitrary graph Clique Problems) |
2006 |
$O({3}^{(n/{3})$}) |
$O(n^{2})$?
|
| Enumerating Maximal Cliques, arbitrary graph |
Segundo; Artieda; Strash Parallel (Enumerating Maximal Cliques, arbitrary graph Clique Problems) |
2011 |
$O({3}^{(n/{3})})$ total work? (previously this cell said $O(n^{4})$) |
$O(n^{2})$ auxiliary??
|
| Enumerating Maximal Cliques, arbitrary graph |
David Eppstein, Maarten Löffler, Darren Strash (Enumerating Maximal Cliques, arbitrary graph Clique Problems) |
2010 |
$O(dn {3}^{(d/{3})})$ |
$O(n^{2})$?
|
| Enumerating Maximal Cliques, arbitrary graph |
Chiba and Nishizeki (Enumerating Maximal Cliques, arbitrary graph Clique Problems) |
1985 |
$O(a(G)*m)$ per clique |
$O(m)$
|
| Enumerating Maximal Cliques, arbitrary graph |
M. Chrobak and D. Eppstein (Enumerating Maximal Cliques, arbitrary graph Clique Problems) |
1989 |
$O(n d^{2} {2}^d)$ |
$O(n)$?
|
| Enumerating Maximal Cliques, arbitrary graph |
Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa (Enumerating Maximal Cliques, arbitrary graph Clique Problems) |
1977 |
$O(nm)$ per clique |
$O(m)$
|
| Enumerating Maximal Cliques, arbitrary graph |
Kazuhisa Makino, Takeaki Uno; Section 5 (Enumerating Maximal Cliques, arbitrary graph Clique Problems) |
2004 |
$O(n^{\omega})$ per clique where omega is the exponent on matrix multiplication |
$O(n^{2})$
|
| Minimum TSP |
Held–Karp algorithm (Minimum TSP The Traveling-Salesman Problem) |
1962 |
$O(V^{2} {2}^V)$ |
$O(V*{2}^V)$
|
| Approximate TSP |
Christofides algorithm (Approximate TSP The Traveling-Salesman Problem) |
1976 |
$O(V^{3})$ |
$O(V^{2})$???
|
| Minimum TSP |
Lawler; E. L. (Minimum TSP The Traveling-Salesman Problem) |
1985 |
$O({1.674}^V E^{2})$ |
-
|
| Minimum TSP |
TSPLIB (Minimum TSP The Traveling-Salesman Problem) |
1991 |
$O({2}^V \log E)$ |
-
|
| 2-Dimensional Poisson Problem |
5-point star Cramer's rule (2-Dimensional Poisson Problem Poisson Problem) |
1945 |
$O({4}^{(n^{2})})$ |
$O({4}^{(n^{2})})$ for sure, $O(n^{2})$ possibly??? (if super conservative)
|
| 2-Dimensional Poisson Problem |
5-point Gauss elimination (2-Dimensional Poisson Problem Poisson Problem) |
1945 |
$O(n^{4})$ |
$O(n^{4})$
|
| 2-Dimensional Poisson Problem |
5-point Gauss Seidel iteration (2-Dimensional Poisson Problem Poisson Problem) |
1945 |
$O(n^{4} \log n)$ |
$O(n^{2})$?
|
| 2-Dimensional Poisson Problem |
5-point SOR iteration (2-Dimensional Poisson Problem Poisson Problem) |
1954 |
$O(n^{3} \log n)$ |
$O(n^{2})$?
|
| 2-Dimensional Poisson Problem |
5-point ADI iteration (2-Dimensional Poisson Problem Poisson Problem) |
1955 |
$O(n^{2} \log^{2} n)$ |
$O(n^{2})$?
|
| 2-Dimensional Poisson Problem |
9-point SOR iteration (2-Dimensional Poisson Problem Poisson Problem) |
1956 |
$O(n^{3})$ |
$O(n^{2})$?
|
| 2-Dimensional Poisson Problem |
9-point Tensor product (2-Dimensional Poisson Problem Poisson Problem) |
1964 |
$O(n^{3})$ |
$O(n^{2})$?
|
| 2-Dimensional Poisson Problem |
9-point ADI iteration (2-Dimensional Poisson Problem Poisson Problem) |
1965 |
$O(n^{2} \log n)$ |
$O(n^{2})$?
|
| 2-Dimensional Poisson Problem |
5-point FFT (2-Dimensional Poisson Problem Poisson Problem) |
1965 |
$O(n^{2} \log n)$ |
$O(n^{2})$?
|
| 2-Dimensional Poisson Problem |
9-point ADI iteration + smooth guess (2-Dimensional Poisson Problem Poisson Problem) |
1969 |
$O(n^{2} \log n)$ |
$O(n^{2})$?
|
| 2-Dimensional Poisson Problem |
5-point cyclic reduction (2-Dimensional Poisson Problem Poisson Problem) |
1970 |
$O(n^{2} \log n)$ |
$O(n^{2})$?
|
| 2-Dimensional Poisson Problem |
9-point FFT (2-Dimensional Poisson Problem Poisson Problem) |
1978 |
$O(n^{2} \log n)$ |
$O(n^{2})$?
|
| 3-Dimensional Poisson Problem |
5-point star Cramer's rule (3-Dimensional Poisson Problem Poisson Problem) |
1945 |
$O({5}^{(n^{3})$}) |
$O({5}^{(n^{3})})$ for sure, $O(n^{3})$ possibly??? (if super conservative)
|
| 3-Dimensional Poisson Problem |
5-point Gauss elimination (3-Dimensional Poisson Problem Poisson Problem) |
1945 |
$O(n^{7})$ |
$O(n^{6})$
|
| 3-Dimensional Poisson Problem |
5-point Gauss Seidel iteration (3-Dimensional Poisson Problem Poisson Problem) |
1945 |
$O(n^{5} \log n)$ |
$O(n^{3})$?
|
| 3-Dimensional Poisson Problem |
5-point SOR iteration (3-Dimensional Poisson Problem Poisson Problem) |
1954 |
$O(n^{4} \log n)$ |
$O(n^{3})$?
|
| 3-Dimensional Poisson Problem |
5-point ADI iteration (3-Dimensional Poisson Problem Poisson Problem) |
1955 |
$O(n^{3} \log^{2} n)$ |
$O(n^{3})$?
|
| 3-Dimensional Poisson Problem |
9-point SOR iteration (3-Dimensional Poisson Problem Poisson Problem) |
1956 |
$O(n^{4})$ |
$O(n^{3})$?
|
| 3-Dimensional Poisson Problem |
9-point Tensor product (3-Dimensional Poisson Problem Poisson Problem) |
1964 |
$O(n^{4})$ |
$O(n^{3})$?
|
| 3-Dimensional Poisson Problem |
9-point ADI iteration (3-Dimensional Poisson Problem Poisson Problem) |
1965 |
$O(n^{3} \log n)$ |
$O(n^{3})$?
|
| 3-Dimensional Poisson Problem |
5-point FFT (3-Dimensional Poisson Problem Poisson Problem) |
1965 |
$O(n^{3} \log n)$ |
$O(n^{3})$?
|
| 3-Dimensional Poisson Problem |
9-point ADI iteration + smooth guess (3-Dimensional Poisson Problem Poisson Problem) |
1969 |
$O(n^{3} \log n)$ |
$O(n^{3})$?
|
| 3-Dimensional Poisson Problem |
5-point cyclic reduction (3-Dimensional Poisson Problem Poisson Problem) |
1970 |
$O(n^{3} \log n)$ |
$O(n^{3})$?
|
| 3-Dimensional Poisson Problem |
9-point FFT (3-Dimensional Poisson Problem Poisson Problem) |
1978 |
$O(n^{3} \log n)$ |
$O(n^{3})$?
|
| 2-Dimensional Delaunay Triangulation |
Naive algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation) |
1934 |
$O(n^{4})$? (previously $O(n^{2})$) |
$O(n)$
|
| 2-Dimensional Delaunay Triangulation |
Flipping algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation) |
1999 |
$O(n^{2})$ |
$O(n)$
|
| 2-Dimensional Delaunay Triangulation |
de Berg; Cheong (2-Dimensional Delaunay Triangulation Delaunay Triangulation) |
2008 |
$O(n \log n)$ |
$O(n)$
|
| 2-Dimensional Delaunay Triangulation |
Bowyer–Watson algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation) |
1981 |
$O(n \log n)$ |
$O(n)$
|
| 2-Dimensional Delaunay Triangulation |
Belloch (2-Dimensional Delaunay Triangulation Delaunay Triangulation) |
2006 |
$O(n \log n)$ |
$O(n)$
|
| 2-Dimensional Delaunay Triangulation |
Guibas; Stofli (2-Dimensional Delaunay Triangulation Delaunay Triangulation) |
1985 |
$O(n \log n)$ |
$O(n)$
|
| 2-Dimensional Delaunay Triangulation |
Fortune (2-Dimensional Delaunay Triangulation Delaunay Triangulation) |
1992 |
$O(n^{2})$ |
$O(n)$
|
| 2-Dimensional Delaunay Triangulation |
S-hull (Sinclair) (2-Dimensional Delaunay Triangulation Delaunay Triangulation) |
2010 |
$O(n \log n)$ |
$O(n)$
|
| 2-Dimensional Delaunay Triangulation |
Dwyer (2-Dimensional Delaunay Triangulation Delaunay Triangulation) |
1987 |
$O(n \log n)$ |
$O(n)$?
|
| Delaunay Triangulation |
Katajainen and M. Koppinen ( Delaunay Triangulation) |
1988 |
$O(n \log n)$ |
-
|
| 2-Dimensional Delaunay Triangulation |
Drysdale; Su (2-Dimensional Delaunay Triangulation Delaunay Triangulation) |
1996 |
$O(n)$ |
$O(n)$?
|
| General Delaunay Triangulation (d-dimensions) |
Dwyer (higher dimensions) (General Delaunay Triangulation (d-dimensions) Delaunay Triangulation) |
1987 |
$O(n \log \log n)$ |
$O(n)$?
|
| De Novo Genome Assembly |
de Bruijn Graph (Idury, Waterman) (De Novo Genome Assembly De Novo Genome Assembly) |
1994 |
$O(n^{2})$ |
$O(n)$?
|
| De Novo Genome Assembly |
String Graph (Myers) (De Novo Genome Assembly De Novo Genome Assembly) |
1994 |
$O(n \log n)$ |
$O(n)$?
|
| De Novo Genome Assembly |
String Graph with Ferragina–Manzini Index (Simpson, Durbin) (De Novo Genome Assembly De Novo Genome Assembly) |
2010 |
$O(n)$ |
$O(n)$?
|
| De Novo Genome Assembly |
Hybrid Algorithm (De Novo Genome Assembly De Novo Genome Assembly) |
1999 |
$O(n^{2})$ |
-
|
| Subset Sum |
Naive algorithm (Subset Sum The Subset-Sum Problem) |
1940 |
$O({2}^n * n)$ |
$O(n)$
|
| Subset Sum |
Random Split Exponential algorithm (Subset Sum The Subset-Sum Problem) |
1940 |
$O({2}^{(n/{2})} * n)$ |
$O({2}^{(n/{2})})$
|
| Functional Dependency Inference Problem |
Brute force algorithm (Functional Dependency Inference Problem Dependency Inference Problem) |
1967 |
$O(n^{2} {2}^n p \log p)$ |
$O(n2^n)$?
|
| Functional Dependency Inference Problem |
Schlimmer (Functional Dependency Inference Problem Dependency Inference Problem) |
1993 |
$O(n {2}^n p)$ |
$O({2}^n)$
|
| Decisional BCNF |
Liu (Decisional BCNF BCNF Decomposition) |
1992 |
$O(kn^{2})$ |
$O(n)$
|
| 4NF Decomposition |
Tradu; Mirc ( 4NF Decomposition) |
1967 |
$O({2}^n)$ |
-
|
| 4NF Decomposition |
Xu; Renio ( 4NF Decomposition) |
1972 |
$O({2}^n)$ |
-
|
| 4NF Decomposition |
Derek's Algorithm ( 4NF Decomposition) |
1983 |
$O({2}^n)$ |
-
|
| 4NF Decomposition |
Russell et. al. ( 4NF Decomposition) |
1989 |
$O({2}^n)$ |
-
|
| 4NF Decomposition |
Maxwell ( 4NF Decomposition) |
2000 |
$O({2}^n)$ |
-
|
| 4NF Decomposition |
Derek's + Maxwell ( 4NF Decomposition) |
2001 |
$O({2}^n)$ |
-
|
| 4NF Decomposition |
Naive ( 4NF Decomposition) |
1956 |
$O({2}^n)$ |
-
|
| 4NF Decomposition |
Trino ( 4NF Decomposition) |
2004 |
$O({2}^n)$ |
-
|
| Multivalued Dependency Inference Problem |
Räihä; Manilla (Multivalued Dependency Inference Problem Dependency Inference Problem) |
1992 |
$O(n^{2} {2}^n p log p)$ |
$O(n2^n)$?
|
| Multivalued Dependency Inference Problem |
Catriel Beeri Ronald Fagin John H. Howard (Multivalued Dependency Inference Problem Dependency Inference Problem) |
1977 |
$O({4}^n)$ |
-
|
| Disk Scheduling |
FCFS (Disk Scheduling Disk Scheduling) |
1979 |
$O(n)$ |
$O({1})$
|
| Disk Scheduling |
SSTF (Disk Scheduling Disk Scheduling) |
1979 |
$O(n \log n)$ with binary tree |
$O(n)$
|
| Disk Scheduling |
SCAN (Disk Scheduling Disk Scheduling) |
1979 |
$O(n \log n)$ |
$O(n)$
|
| Disk Scheduling |
LOOK (Disk Scheduling Disk Scheduling) |
1979 |
$O(n \log n)$ |
$O(n)$
|
| Disk Scheduling |
C-SCAN (Disk Scheduling Disk Scheduling) |
1979 |
$O(n \log n)$ |
$O(n)$
|
| Disk Scheduling |
C-LOOK (Disk Scheduling Disk Scheduling) |
1979 |
$O(n \log n)$ |
$O(n)$
|
| The Vertex Cover Problem |
Brute force (backtracking search) (The Vertex Cover Problem The Vertex Cover Problem) |
1940 |
$O({2}^k n^O({1})$) |
$O(k)$
|
| The Vertex Cover Problem |
Sam Buss (The Vertex Cover Problem The Vertex Cover Problem) |
1993 |
$O(kn + {2}^k k^{({2}k + {2})})$ |
$O(k^{2})$?
|
| The Vertex Cover Problem |
Chen; I. Kanj; and W. Jia. (The Vertex Cover Problem The Vertex Cover Problem) |
2001 |
$O(kn + {1.2852}^k)$ |
$O(k^{3})$ auxiliary? (potentially $O(k^{2})$??)
|
| The Vertex Cover Problem |
Chandran and F. Grandoni (The Vertex Cover Problem The Vertex Cover Problem) |
2004 |
$O(min({1.2759}^k k^{1.5}, {1.2745}^k k^{4}) + kn)$ |
$O(min({1.2759}^k k^{1.5}, {1.2745}^k k^{4}) + kn)$ but exponential
|
| The Vertex Cover Problem |
Chen; I. Kanj; and W. Jia. (The Vertex Cover Problem The Vertex Cover Problem) |
2006 |
$O({1.2738}^k+ kn)$ |
$O(poly(n))$
|
| The Vertex Cover Problem, Degrees Bounded By 3 |
J. Chen; L. Liu; and W. Jia. (The Vertex Cover Problem, Degrees Bounded By 3 The Vertex Cover Problem) |
2000 |
$O(k*{1.2192}^k)$ |
$O(k^{3})$ auxiliary? (potentially $O(k^{2})$??)
|
| The Vertex Cover Problem |
Balasubramanian; Fellows (The Vertex Cover Problem The Vertex Cover Problem) |
1996 |
$O(kn + ({1.324718})$^k * k^{2}) |
$O(k^{3})$ auxiliary? (potentially $O(k^{2})$??)
|
| The Vertex Cover Problem |
Papadimitriou and M Yannakakis (The Vertex Cover Problem The Vertex Cover Problem) |
1996 |
$O({3}^k n)$ |
$O(k)$ auxiliary?
|
| The Vertex Cover Problem |
Niedermeier, Rossmanith (The Vertex Cover Problem The Vertex Cover Problem) |
1999 |
$O(kn + {1.29175}^k k^{2})$. |
$O(k^{3})$ auxiliary? (potentially $O(k^{2})$??)
|
| The Vertex Cover Problem |
Downey (The Vertex Cover Problem The Vertex Cover Problem) |
1998 |
$O(kn + {1.31951}^k k^{2})$ |
$O(k^{3})$ auxiliary? (potentially $O(k^{2})$??)
|
| CFG Recognition |
Cocke–Younger–Kasami algorithm (CFG Recognition CFG Problems) |
1968 |
G|)$ |
$O(n^{2})$
|
| CFG Recognition |
Valiant (CFG Recognition CFG Problems) |
1975 |
G|)$ where omega is the exponent for matrix multiplication |
$O(n^{2})$?
|
| CFG Parsing |
Earley parser (CFG Parsing CFG Problems) |
1968 |
$O(n^{3})$ |
$O(n^{2})$
|
| CFG Parsing |
GLR parser (CFG Parsing CFG Problems) |
1974 |
$O(n^{3})$ |
$O(n^{3})$
|
| Finding Frequent Itemsets |
A-Priori algorithm (Finding Frequent Itemsets Finding Frequent Itemsets) |
1994 |
$O(n^{2})$ |
$O(n^{2})$
|
| Finding Frequent Itemsets |
The Algorithm of Park; Chen; and Yu (PCY) (Finding Frequent Itemsets Finding Frequent Itemsets) |
1995 |
$O(n^{2})$ |
$O(n^{2})$
|
| Finding Frequent Itemsets |
The Multistage Algorithm (Finding Frequent Itemsets Finding Frequent Itemsets) |
1999 |
$O(n^{2})$ |
$O(n^{2})$
|
| Finding Frequent Itemsets |
The Multihash Algorithm (Finding Frequent Itemsets Finding Frequent Itemsets) |
1999 |
$O(n^{2})$ |
$O(n^{2})$
|
| Lossy Compression |
Gupta; Verdu (Lossy Compression Data Compression) |
2009 |
$O(n^{2} log^{3} n)$ |
$O(n)$
|
| Lossy Compression |
Discrete Cosine Transform (Lossy Compression Data Compression) |
1974 |
$O(n^{2})$ |
$O(n)$
|
| Lossy Compression |
Maneva and M. J. Wainwright (Lossy Compression Data Compression) |
2005 |
$O(n^{2})$ |
$O(n^{2})$
|
| Lossy Compression |
Ciliberti; Mézard (Lossy Compression Data Compression) |
2005 |
$O(n^{2})$ |
$O(n^{2})$?
|
| Lossy Compression |
Brute force (Lossy Compression Data Compression) |
1940 |
$O(n*{2}^n)$ |
$O(n*{2}^n)$?
|
| Lossy Compression |
Matsunaga; Yamamoto (Lossy Compression Data Compression) |
2003 |
$O(n*{2}^n)$ |
exp(n)
|
| Lossy Compression |
Sun; M. Shao; J. Chen; K. Wong; and X. Wu (Lossy Compression Data Compression) |
2010 |
$O(kmn)$? |
$O(kmn)$?
|
| Lossy Compression |
Miyake 2006 (Lossy Compression Data Compression) |
2006 |
$O(n*{2}^n)$ |
$O({2}^n)$
|
| Lossy Compression |
Martinian and M. J. Wainwright (Lossy Compression Data Compression) |
2006 |
$O(n*{2}^n)$ |
$O(mn+mk)$?
|
| Lossy Compression |
Jalali and T. Weissman (Lossy Compression Data Compression) |
2008 |
$O(n)$ |
$O(n)$?
|
| Lossy Compression |
Jalali; A. Montanari; and T. Weissman (Lossy Compression Data Compression) |
2010 |
$O(n)$ |
$O(n)$?
|
| Lossy Compression |
Korada and R. Urbanke; (Lossy Compression Data Compression) |
2010 |
$O(n*{2}^n)$ |
$O(N)$
|
| Distinct-degree; Equal-degree |
Berlekamp's algorithm (Distinct-degree; Equal-degree Factorization of Polynomials Over Finite Fields) |
1967 |
$O(n^{3} \log n)$ |
$O(n)$
|
| Factorization of Polynomials Over Finite Fields |
Schubert's algorithm ( Factorization of Polynomials Over Finite Fields) |
1940 |
$O(n^{3})$ |
$O(n)$
|
| Square-free |
Square-free factorization (Square-free Factorization of Polynomials Over Finite Fields) |
1975 |
$O(n^{3})$ |
$O(n)$
|
| Distinct-degree |
Distinct-degree factorization (Distinct-degree Factorization of Polynomials Over Finite Fields) |
1944 |
$O(n^{3} + n \log n)$ |
$O(n)$
|
| Equal-degree |
Cantor–Zassenhaus algorithm (Equal-degree Factorization of Polynomials Over Finite Fields) |
1981 |
$O(n^{3} \log n)$ |
$O(n)$
|
| Equal-degree |
Victor Shoup's algorithm (Equal-degree Factorization of Polynomials Over Finite Fields) |
1990 |
$O(n^{2})$ |
$O(n)$
|
| Cryptanalysis of Linear Feedback Shift Registers |
Berlekamp–Massey algorithm (Cryptanalysis of Linear Feedback Shift Registers Cryptanalysis of Linear Feedback Shift Registers) |
1969 |
$O(n^{2})$ |
$O(n)$?
|
| Stable Marriage Problem |
Gale–Shapley algorithm (Stable Marriage Problem Stable Matching Problem) |
1962 |
$O(n^{2})$ |
$O(n)$
|
| Stable Roommates Problem |
Irving's Algorithm (Stable Roommates Problem Stable Matching Problem) |
1985 |
$O(n^{2})$ |
$O(n^{2})$?
|
| Stable Marriage Problem |
Manlove; Malley (Stable Marriage Problem Stable Matching Problem) |
2005 |
$O(n^{2})$ |
$O(n^{2})$?
|
| Stable Marriage Problem |
Unsworth; C.; Prosser; P (Stable Marriage Problem Stable Matching Problem) |
2005 |
$O(n^{2})$ |
$O(n^{2})$?
|
| Arc Consistency? |
Hentenryck et. al. (Arc Consistency? Stable Matching Problem) |
1992 |
$O(n^{3})$ |
$O(n^{3})$?
|
| Stable Marriage Problem |
Gent; I.P.; Irving; R.W.; Manlove; D.F.; Prosser; P.; Smith; B.M. (Stable Marriage Problem Stable Matching Problem) |
2001 |
$O(n^{2})$ |
$O(n^{2})$?
|
| Stable Roommates Problem |
Patrick Posser (Stable Roommates Problem Stable Matching Problem) |
2014 |
$O(n^{3})$ |
$O(n)$
|
| Stable Marriage Problem |
S. S. TSENG and R. C. T. LEE (Stable Marriage Problem Stable Matching Problem) |
1984 |
$O(n^{2})$ |
$O(n)$ per processor?
|
| Stable Marriage Problem |
[[Tomas Feder, Nimrod Megiddoy, Serge A� Plotki (Stable Marriage Problem Stable Matching Problem)]] |
1994 |
$O(n^{0.5})$ |
$O(n^{0.5})$ auxiliary per processor?
|
| Longest Path on Interval Graphs |
Ioannidou; Kyriaki; Mertzios; George B.; Nikolopoulos; Stavros D. (Longest Path on Interval Graphs Longest Path Problem) |
2011 |
$O(n^{4})$ |
$O(n^{3})$
|
| Constructing Suffix Trees |
Naive (Constructing Suffix Trees Constructing Suffix Trees) |
1973 |
$O(n^{2})$ |
$O(n)$
|
| Constructing Suffix Trees |
Weiner's algorithm (Constructing Suffix Trees Constructing Suffix Trees) |
1973 |
$O(n)$ |
$O(n)$
|
| Constructing Suffix Trees |
Pratt (Constructing Suffix Trees Constructing Suffix Trees) |
1973 |
$O(n)$ |
-
|
| Constructing Suffix Trees |
Ukkonen (Constructing Suffix Trees Constructing Suffix Trees) |
1995 |
$O(n)$ |
$O(n)$
|
| Constructing Suffix Trees |
Ukkonen and D. Wood (Constructing Suffix Trees Constructing Suffix Trees) |
1993 |
$O(n^{2})$ |
$O(n^{2})$
|
| Constructing Suffix Trees |
Hariharan (Constructing Suffix Trees Constructing Suffix Trees) |
1997 |
$O(log^{4}(n)$) |
$O(n)$
|
| Constructing Suffix Trees |
Süleyman Cenk Sahinalp ; Uzi Vishkin (Constructing Suffix Trees Constructing Suffix Trees) |
1994 |
$O(log^{2}(n)$) |
$O(n^{({1}+\eps)})$ for any fixed eps>{0}
|
| Constructing Suffix Trees |
Farach (Constructing Suffix Trees Constructing Suffix Trees) |
1997 |
$O(\log n)$ |
$O(n)$
|
| Constructing Suffix Trees |
Rytter (Constructing Suffix Trees Constructing Suffix Trees) |
2004 |
$O(\log n)$ |
$O(n)$
|
| Constructing Suffix Trees |
McCreight (Constructing Suffix Trees Constructing Suffix Trees) |
1976 |
$O(n)$ |
$O(n)$
|
| Entity Resolution |
Fellegi & Sunter Model (Entity Resolution Entity Resolution) |
1969 |
$O(n^{3}k)$ |
$O(k)$
|
| Entity Resolution |
Gupta & Sarawagi CRF (Entity Resolution Entity Resolution) |
2009 |
$O(n^{3}k)$ |
$O(nk)$?
|
| Entity Resolution |
Chen Ensembles of classifiers (Entity Resolution Entity Resolution) |
1989 |
$O(n^{2} \log n)$ |
-
|
| Entity Resolution |
EM Based Winkler (Entity Resolution Entity Resolution) |
2000 |
$O(n^{3}k)$ |
$O(k)$
|
| Entity Resolution |
Ravikumar & Cohen Generative Models (Entity Resolution Entity Resolution) |
2004 |
$O(n^{2} k)$ |
$O(k)$
|
| Entity Resolution |
Bellare Active Learning (Entity Resolution Entity Resolution) |
2012 |
$O(n^{2} \log n c \log c)$ |
-
|
| Entity Resolution |
Ananthakrishna (Entity Resolution Entity Resolution) |
2002 |
$O(n^{2} k)$ |
$O(n)$
|
| Entity Resolution |
BOYS algorithm (Entity Resolution Entity Resolution) |
1993 |
$O(n^{2} k)$ |
$O(n^{2})$
|
| Longest Palindromic Substring |
Naive (Longest Palindromic Substring Longest Palindromic Substring) |
1940 |
$O(n^{3})$ |
$O({1})$
|
| Longest Palindromic Substring |
Dynamic Programming (Longest Palindromic Substring Longest Palindromic Substring) |
1953 |
$O(n^{2})$ |
$O(n^{2})$
|
| Longest Palindromic Substring |
Manacher (Longest Palindromic Substring Longest Palindromic Substring) |
1975 |
$O(n)$ |
$O(n)$
|
| Longest Palindromic Substring |
Jeuring (Longest Palindromic Substring Longest Palindromic Substring) |
1994 |
$O(n)$ |
$O(n)$?
|
| Longest Palindromic Substring |
Gusfield (Longest Palindromic Substring Longest Palindromic Substring) |
1997 |
$O(n)$ |
$O(n)$
|
| Global Register Allocation |
Demand-Driven Register Allocation (Global Register Allocation Register Allocation) |
1996 |
$O(n^{2})$ |
$O(n^{2})$
|
| Arithmetic Expression Binary Tree |
Sethi–Ullman Algorithm (Arithmetic Expression Binary Tree AST to Code Translation) |
1970 |
$O(n)$ |
$O({1})$
|
| Graph Isomorphism, General Graphs |
Babai and Luks (Graph Isomorphism, General Graphs Graph Isomorphism Problem) |
1983 |
\exp(n^{\frac{1}{2} + o({1})}) |
-
|
| Graph Isomorphism, Bounded Number of Vertices of Each Color |
Babai (Graph Isomorphism, Bounded Number of Vertices of Each Color Graph Isomorphism Problem) |
1980 |
o(\exp({2}n^{1/2}\log^{2}n)) |
$O(n^{2})$
|
| Isomorphism of strongly regular graphs |
Spielman (Isomorphism of strongly regular graphs Graph Isomorphism Problem) |
1996 |
$n^{O(n^{({1}/{3})} log n)}$ |
check
|
| Graph Isomorphism Problem |
McKay ( Graph Isomorphism Problem) |
1981 |
$O((m1 + m2)n^{3} + m2 n^{2} L)$ |
${2}mn+{10}n+m+(m+{4})K+{2}mL$
|
| Graph Isomorphism Problem |
Schmidt & Druffel ( Graph Isomorphism Problem) |
1976 |
$O(n*n!)$ |
$O(n^{2})$
|
| Subgraph Isomorphism |
Ullman (Subgraph Isomorphism Graph Isomorphism Problem) |
1976 |
- |
$O(mn)$?
|
| Graph Isomorphism Problem |
Babai ( Graph Isomorphism Problem) |
2017 |
{2}^{$O(\log n)$^3} |
-
|
| Circulant graphs |
Muzychuk (Circulant graphs Graph Isomorphism Problem) |
2004 |
$O(n^{2})$ |
$O(n^{2})$
|
| Partial k-trees |
Bodlaender (Partial k-trees Graph Isomorphism Problem) |
1990 |
$O(n^{(k+{4.5})})$ |
check
|
| Hypergraphs isomorphism |
Babai & Codenotti (Hypergraphs isomorphism Graph Isomorphism Problem) |
2008 |
$exp(O(k^{2} \sqrt{n})$ |
check
|
| Digraph Realization Problem |
Kleitman–Wang Algorithm (Digraph Realization Problem Graph Realization Problems) |
1973 |
$O(n)$ |
$O(n)$
|
| Digraph Realization Problem |
Fulkerson–Chen–Anstee (Digraph Realization Problem Graph Realization Problems) |
1982 |
$O(n)$ |
$O({1})$
|
| DAG Realization Problem |
Berger & Müller-Hannemann (DAG Realization Problem Graph Realization Problems) |
2011 |
$O(\exp(n)$) |
?
|
| Duplicate Elimination |
Sorting based (Merge Sort) (Duplicate Elimination Duplicate Elimination) |
1964 |
$O(n \log n)$ |
$O(n)$
|
| Duplicate Elimination |
Sorting based (Merge Sort) + real-time elimination (Duplicate Elimination Duplicate Elimination) |
1964 |
$O(n \log n)$ |
-
|
| Duplicate Elimination |
BST Algorithm (Duplicate Elimination Duplicate Elimination) |
1999 |
$O(n \log n)$ |
$O(\log n)$
|
| Duplicate Elimination |
Priority Queue Algorithm (Duplicate Elimination Duplicate Elimination) |
1976 |
$O(n^{2})$ |
$O(n)$
|
| Duplicate Elimination |
Sorted Neighborhood Algorithm (SNA) (Duplicate Elimination Duplicate Elimination) |
1998 |
$O(n^{2})$ |
$O(n)$
|
| Duplicate Elimination |
Duplicate Elimination Sorted Neighborhood Algorithm (DE-SNA) (Duplicate Elimination Duplicate Elimination) |
2002 |
$O(n \log n)$ |
-
|
| Duplicate Elimination |
Adaptive Duplicate Detection Algorithm (ADD) (Duplicate Elimination Duplicate Elimination) |
2003 |
$O(n^{3})$ |
$O({1})$
|
| Hyperbolic Spline Interpolation |
B.I. Kvasov (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) |
2008 |
$O(n^{3} \log^{2}K)$ |
$O(n)$?
|
| Hyperbolic Spline Interpolation |
V. A. Lyul’ka and A. V. Romanenko (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) |
1994 |
$O(n^{5})$ |
-
|
| Hyperbolic Spline Interpolation |
V. A. Lyul’ka and I. E. Mikhailov (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) |
2003 |
$O(n^{4})$ |
-
|
| Hyperbolic Spline Interpolation |
V. I. Paasonen (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) |
1968 |
$O(n^{5} \log K)$ |
-
|
| Hyperbolic Spline Interpolation |
P. Costantini, B. I. Kvasov, and C. Manni (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) |
1999 |
$O(n^{5} \log K)$ |
$O(n)$?
|
| Hyperbolic Spline Interpolation |
B. I. Kvasov (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) |
2000 |
$O(n^{4})$ |
$O(n)$??
|
| Mesh Parameterization |
ECK M.; DEROSE T.; DUCHAMP T.; 1995 (Mesh Parameterization Mesh Parameterization) |
1995 |
$O(n^{2})$ |
-
|
| Mesh Parameterization |
FLOATER 1997 (Mesh Parameterization Mesh Parameterization) |
1997 |
$O(n^{2})$ |
-
|
| Mesh Parameterization |
PINKALL U.; POLTHIER K 1993 (Mesh Parameterization Mesh Parameterization) |
1993 |
$O(n^{2})$ |
-
|
| Mesh Parameterization |
FLOATER 2003 (Mesh Parameterization Mesh Parameterization) |
2003 |
$O(n^{2})$ |
-
|
| Mesh Parameterization |
LEE Y.; KIM H. S.; LEE S 2002 (Mesh Parameterization Mesh Parameterization) |
2002 |
$O(n \log^{3}n)$ |
-
|
| Mesh Parameterization |
DESBRUN M.; MEYER M.; ALLIEZ P. 2002 (Mesh Parameterization Mesh Parameterization) |
2002 |
$O(n^{2})$ |
-
|
| Mesh Parameterization |
LÉVY B.; PETITJEAN S.; RAY N.; MAILLOT J 2002 (Mesh Parameterization Mesh Parameterization) |
2002 |
$O(n \log^{2.5} n)$ |
-
|
| Mesh Parameterization |
KARNI Z.; GOTSMAN C.; GORTLER S. J. 2005 (Mesh Parameterization Mesh Parameterization) |
2005 |
$O(n^{2})$ |
-
|
| Mesh Parameterization |
HORMANN K.; GREINER G 1999 (Mesh Parameterization Mesh Parameterization) |
1999 |
$O(n^{2})$ |
-
|
| Mesh Parameterization |
SHEFFER A.; DE STURLER E. 2000 (Mesh Parameterization Mesh Parameterization) |
2000 |
$O(n^{2})$ |
-
|
| Mesh Parameterization |
SHEFFER A.; LÉVY B.; MOGILNITSKY M.; BOGOMYAKOV A. 2005 (Mesh Parameterization Mesh Parameterization) |
2005 |
$O(n^{2})$ |
-
|
| Mesh Parameterization |
ZAYER R.; LÉVY B.; SEIDEL H.-P. 2007 (Mesh Parameterization Mesh Parameterization) |
2007 |
$O(n)$ |
-
|
| Mesh Parameterization |
SANDER P. V.; SNYDER J.; GORTER S. J.; HOPPE 2001 (Mesh Parameterization Mesh Parameterization) |
2001 |
$O(n^{2})$ |
-
|
| Mesh Parameterization |
YAN J. Q.; YANG X.; SHI P. F 2006 (Mesh Parameterization Mesh Parameterization) |
2006 |
$O(n^{2})$ |
-
|
| Mesh Parameterization |
ZAYER R.; ROESSL C.; SEIDEL H.-P 2005 (Mesh Parameterization Mesh Parameterization) |
2005 |
$O(n \log n)$ |
-
|
| Mesh Parameterization |
YOSHIZAWA S.; BELYAEV A. G.; SEIDEL H.-P 2004 (Mesh Parameterization Mesh Parameterization) |
2004 |
$O(n^{2})$ |
-
|
| Mesh Parameterization |
CHEN Z. G.; LIU L. G.; ZHANG Z. Y.; WANG G. J. 2007 (Mesh Parameterization Mesh Parameterization) |
2007 |
$O(n^{2})$ |
-
|
| Mesh Parameterization |
YANG Y.; KIM J.; LUO F.; HU S.; GU X. 2008 (Mesh Parameterization Mesh Parameterization) |
2008 |
$O(n \log\log n)$ |
-
|
| Mesh Parameterization |
BEN-CHEN M.; GOTSMAN C.; BUNIN G. 2008 (Mesh Parameterization Mesh Parameterization) |
2008 |
$O(n \log^{2}n)$ |
-
|
| Mesh Parameterization |
SPRINGBORN B.; SCHROEDER P.; PINKALL U. 2008 (Mesh Parameterization Mesh Parameterization) |
2008 |
$O(n \log^{2}n)$ |
-
|
| Maximum Likelihood Methods in Unknown Latent Variables |
Expectation-Maximization (EM) algorithm (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) |
1977 |
$O(n^{3})$ |
$O(n+r)$?
|
| Maximum Likelihood Methods in Unknown Latent Variables |
EM with Quasi-Newton Methods (Jamshidian; Mortaza; Jennrich; Robert I.) (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) |
1997 |
$O(n^{2} \log^{3} n)$ |
$O(n+r^{2})$?
|
| Maximum Likelihood Methods in Unknown Latent Variables |
Parameter-expanded expectation maximization (PX-EM) (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) |
1998 |
$O(n^{3})$ |
$O(n+r)$?
|
| Maximum Likelihood Methods in Unknown Latent Variables |
Expectation conditional maximization (ECM) (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) |
1993 |
$O(n^{3})$ |
$O(n+r)$?
|
| Maximum Likelihood Methods in Unknown Latent Variables |
Expectation conditional maximization either (ECME) (Liu; Chuanhai; Rubin; Donald B) (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) |
1994 |
$O(n^{3})$ |
$O(n+r)$?
|
| Maximum Likelihood Methods in Unknown Latent Variables |
α-EM Algorithm (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) |
2003 |
$O(n^{3})$ |
$O(n+r)$?
|
| Maximum Likelihood Methods in Unknown Latent Variables; multi-view model, discrete observations |
Shaban; Amirreza; Mehrdad; Farajtabar (Maximum Likelihood Methods in Unknown Latent Variables; multi-view model, discrete observations Maximum Likelihood Methods in Unknown Latent Variables) |
2015 |
$O(n^{2} \log^{2} n)$ |
$O(kd+d^{3})$??
|
| Maximum Likelihood Methods in Unknown Latent Variables, Hidden Markov Models |
alpha-HMM (Matsuyama, Yasuo) (Maximum Likelihood Methods in Unknown Latent Variables, Hidden Markov Models Maximum Likelihood Methods in Unknown Latent Variables) |
2011 |
$O(n^{2} \log^{2} n)$ |
-
|
| Matrix Factorization |
LU Matrix Decomposition (Matrix Factorization Collaborative Filtering) |
1945 |
$O(n^{3})$ |
$O(n^{2})$
|
| Matrix Factorization |
QR Matrix Decomposition (Matrix Factorization Collaborative Filtering) |
1955 |
$O(n^{2})$ |
$O(n^{2})$
|
| Matrix Factorization |
Cholesky Decomposition (Matrix Factorization Collaborative Filtering) |
1983 |
$O(n^{2})$ |
$O(n^{2})$
|
| Filtering Problem (Stochastic Processes) |
Kalman Filter (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) |
1960 |
$O(n^{3})$ |
$O(n^{2})$?
|
| Filtering Problem (Stochastic Processes) |
Particle filter Del Moral (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) |
1996 |
$O(n^{3})$ |
$O(nN)$?
|
| Filtering Problem (Stochastic Processes) |
Stratonovich (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) |
1959 |
$O(n^{3})$ |
-
|
| Filtering Problem (Stochastic Processes) |
Stratonovich (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) |
1960 |
$O(n^{3})$ |
-
|
| Filtering Problem (Stochastic Processes) |
Kushner non-linear filter (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) |
1967 |
$O(n^{3})$ |
$O(n^{2})$??
|
| Filtering Problem (Stochastic Processes) |
Zakai (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) |
1969 |
$O(n^{3})$ |
-
|
| Filtering Problem (Stochastic Processes) |
Maybeck; Peter S Extended Kalman Filter (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) |
1979 |
$O(n^{2} \log^{2} n)$ |
$O(n^{2})$?
|
| Filtering Problem (Stochastic Processes) |
Damiano Brigo; Bernard Hanzon and François LeGland (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) |
1998 |
$O(n^{2.{4}5} \log n)$ |
-
|
| Filtering Problem (Stochastic Processes) |
Del Moral; Pierre (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) |
1998 |
$O(n^{2})$ |
-
|
| Filtering Problem (Stochastic Processes) |
Ocone (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) |
1999 |
$O(n^{2})$ |
-
|
| Optimal Policies for MDPs |
Bellman Value Iteration (VI) (Optimal Policies for MDPs Optimal Policies for MDPs) |
1957 |
$O({2}^n)$ |
$O(n)$
|
| Optimal Policies for MDPs |
Howard Policy Iteration (PI) (Optimal Policies for MDPs Optimal Policies for MDPs) |
1960 |
$O(n^{3})$ |
$O(n)$
|
| Optimal Policies for MDPs |
Puterman Modified Policy Iteration (MPI) (Optimal Policies for MDPs Optimal Policies for MDPs) |
1974 |
$O(n^{3})$ |
$O(n)$
|
| Unweighted Set-Covering; Weighted Set-Covering |
Integer linear program Vazirani (Unweighted Set-Covering; Weighted Set-Covering The Set-Covering Problem) |
2001 |
$O(n^{2})$ |
$O(U)$
|
| The Set-Covering Problem |
Greedy Algorithm ( The Set-Covering Problem) |
1996 |
$O(n^{3} \log n)$ |
$O(U)$
|
| The Set-Covering Problem |
Lund & Yannakakis ( The Set-Covering Problem) |
1994 |
$O({2}^n)$ |
-
|
| The Set-Covering Problem |
Feige ( The Set-Covering Problem) |
1998 |
$O({2}^n)$ |
-
|
| The Set-Covering Problem |
Raz & Safra ( The Set-Covering Problem) |
1997 |
$O(n^{3} \log^{3} n)$ |
-
|
| The Set-Covering Problem |
Dinur & Steurer ( The Set-Covering Problem) |
2013 |
$O(n^{2} \log n)$ |
-
|
| The Set-Covering Problem |
Cardoso; Nuno; Abreu; Rui ( The Set-Covering Problem) |
2014 |
$O(n^{2})$ |
-
|
| The Set-Covering Problem |
Brute force ( The Set-Covering Problem) |
1972 |
$O(U {2}^n)$ |
$O(U)$
|
| Motif Search |
Helden Oligo-Analysis (Motif Search Motif Search) |
1998 |
$O(mn)$ |
$O(m)$
|
| Motif Search |
van Helden J; Rios AF; Collado-Vides J (Motif Search Motif Search) |
2000 |
$O(mn)$ |
$O(m)$
|
| Motif Search |
Tompa M (Motif Search Motif Search) |
1999 |
$O(mn)$ |
$O(m^{2})$
|
| Motif Search |
Sinha S; Tompa M YMF (Yeast Motif Finder) (Motif Search Motif Search) |
2000 |
$O(n^{0.{6}6} m)$ |
$O(m)$
|
| Motif Search |
Bailey TL; Elkan C MEME (Motif Search Motif Search) |
1995 |
$O(n^{2}m^{2})$ |
$O(mn)$
|
| Motif Search |
Sagot M (Motif Search Motif Search) |
1988 |
$O(n \log(n)$ m^{1.{4}5}) |
$O(mn^{2}/w)$
|
| Motif Search |
Liang Cwinnower (Motif Search Motif Search) |
2003 |
$O(nm^{0.5})$ |
$O(m^{2})$
|
| Motif Search |
Kingsford (Motif Search Motif Search) |
2006 |
$O(mn)$ |
$O(m^{2}n^{2})$
|
| All Maximal Non-Branching Paths in a Graph |
Naive (All Maximal Non-Branching Paths in a Graph All Maximal Non-Branching Paths in a Graph) |
1940 |
$O(m)$ |
$O(n)$?
|
| InDegree Analysis |
The INDEGREE Algorithm (InDegree Analysis Link Analysis) |
1997 |
$O(mn)$ |
$O(n)$
|
| Link Analysis |
The PAGERANK Algorithm (Link Analysis Link Analysis) |
1998 |
$O(m n )$ |
$O(n)$
|
| Link Analysis |
The (Hyperlink-Induced Topic Search) HITS Algorithm (Link Analysis Link Analysis) |
1998 |
$O(n^{2} k)$ |
$O(n)$
|
| Link Analysis |
Kleinberg (Link Analysis Link Analysis) |
1998 |
$O(m^{2} n )$ |
-
|
| Link Analysis |
The (Stochastic Approach for Link Structure Analysis) SALSA Algorithm (Link Analysis Link Analysis) |
2000 |
$O(m^{2} n )$ |
$O(n)$?
|
| Link Analysis |
Randomized HITS (Link Analysis Link Analysis) |
2001 |
$O(m n\log n )$ |
$O(n)$
|
| Link Analysis |
PHITS Coheng Chan (Link Analysis Link Analysis) |
2000 |
$O(m n )$ |
$O(nz)$?
|
| Link Analysis |
Haveliwala (Link Analysis Link Analysis) |
2002 |
$O(m n )$ |
$O(nz)$?
|
| Link Analysis |
Jeh and Widom (Link Analysis Link Analysis) |
2003 |
$O(m n )$ |
$O(nh)$
|
| Link Analysis |
Richardson and Domingos (Link Analysis Link Analysis) |
2002 |
$O(m n )$ |
$O(nl)$
|
| Link Analysis |
Tomlin (Link Analysis Link Analysis) |
2003 |
$O(m n )$ |
$O(n)$?
|
| Link Analysis |
Achlioptas (Link Analysis Link Analysis) |
2001 |
$O(mn )$ |
$O((n+l)$^{2})?
|
| Distributed Locking Algorithms |
Leases (Cary G Gray and David R Cheriton) (Distributed Locking Algorithms Distributed Locking Algorithms) |
1989 |
$O(n)$ |
$O(f)$?
|
| Distributed Locking Algorithms |
Chubby (Mike Burrows) (Distributed Locking Algorithms Distributed Locking Algorithms) |
2006 |
$O(n)$ |
$O(f)$?
|
| Distributed Locking Algorithms |
Tushar Deepak Chandra and Sam Toueg (Distributed Locking Algorithms Distributed Locking Algorithms) |
1996 |
$O(n)$ |
-
|
| Cyclic Peptide Sequencing Problem |
Brute force (Cyclic Peptide Sequencing Problem Cyclic Peptide Sequencing Problem) |
1987 |
${2}^{O(n)}$ |
$O(n)$
|
| Cyclic Peptide Sequencing Problem |
Branch and bound (Cyclic Peptide Sequencing Problem Cyclic Peptide Sequencing Problem) |
1993 |
${2}^{O(n)}$ |
$O({2}^{O(n)})$
|
| Point-in-Polygon |
Ray casting algorithm Shimrat; M (Point-in-Polygon Point-in-Polygon) |
1962 |
$O(n)$ |
$O({1})$
|
| Point-in-Polygon |
Nordbeck and Rystedt (Grid Method) (Point-in-Polygon Point-in-Polygon) |
1967 |
$O(n)$ |
$O(n)$
|
| Point-in-Polygon |
Salomon (Swath Method) (Point-in-Polygon Point-in-Polygon) |
1978 |
$O(n\log n)$ |
$O(n^{2})$
|
| Point-in-Polygon |
Nordbeck and Rystedt (Sum of area) (Point-in-Polygon Point-in-Polygon) |
1967 |
$O(n)$ |
$O({1})$
|
| Point-in-Polygon |
Preparata and Shamos (Wedge) (Point-in-Polygon Point-in-Polygon) |
1985 |
$O(n)$ |
$O(n)$
|
| Point-in-Polygon |
Saalfeld (Sign of offset) (Point-in-Polygon Point-in-Polygon) |
1987 |
$O(n)$ |
$O({1})$
|
| Point-in-Polygon |
Preparata and Shamos (Intersection sum of angle) (Point-in-Polygon Point-in-Polygon) |
1985 |
$O(n)$ |
$O({1})$
|
| Point-in-Polygon |
Nordbeck and Rystedt (Orientation) (Point-in-Polygon Point-in-Polygon) |
1967 |
$O(n)$ |
$O({1})$
|
| Clock Synchronization in Distributed Systems |
ASP (Clock Synchronization in Distributed Systems Clock Synchronization in Distributed Systems) |
2005 |
$O(n)$ |
$O(n)$ (per node)
|
| Clock Synchronization in Distributed Systems |
Clock-sampling mutual network synchronization (Clock Synchronization in Distributed Systems Clock Synchronization in Distributed Systems) |
2007 |
$O(n)$ |
$O({1})$? (per node)
|
| Clock Synchronization in Distributed Systems |
MATSF (Clock Synchronization in Distributed Systems Clock Synchronization in Distributed Systems) |
2004 |
$O(n)$ |
$O(n)$? (per node)
|
| d-Neighborhood of a String |
Iterative naive (d-Neighborhood of a String d-Neighborhood of a String) |
1940 |
$O(f_{bin}(sigma-{1}, n, d)$) where f_{bin}(x, y, z) = sum_{i=0}^z C(y, i)*x^i |
$O(n)$
|
| Maximum Cut |
Hadlock (Maximum Cut Maximum Cut) |
1975 |
$O({2}^n)$ |
-
|
| Maximum Cut, Approximate |
Motwani & Raghavan (Maximum Cut, Approximate Maximum Cut) |
1995 |
$O(n)$? |
$O(n)$
|
| Maximum Cut, Approximate |
Mitzenmacher & Upfal (Maximum Cut, Approximate Maximum Cut) |
2005 |
$O(mn)$? |
$O(n)$
|
| Maximum Cut, Approximate |
Khuller; Raghavachari & Young, "Greedy Methods" (Maximum Cut, Approximate Maximum Cut) |
2007 |
$O(n^{2})$? |
$O(n)$
|
| Maximum Cut, Approximate |
Ausiello et al. (Maximum Cut, Approximate Maximum Cut) |
2003 |
$O(n^{3} \log m)$ |
$O(n^{2})$?
|
| Maximum Cut, Approximate |
Dunning; Gupta & Silberholz (Maximum Cut, Approximate Maximum Cut) |
2018 |
$O(mn)$ |
-
|
| Minimum Wiener Connector problem |
Ruchansky (Minimum Wiener Connector problem Wiener Index) |
2015 |
$O(q(m*log(n)$+n*log^{2}(n))) |
$O(q(m+n*log(n)$)?
|
| Determinant of Matrices with Integer Entries |
Bareiss algorithm (Determinant of Matrices with Integer Entries Determinant of Matrices with Integer Entries) |
1968 |
$O(n^{5} L^{2} (\log(n)$^{2} + L^{2})) |
$O(n^{2}(n*log(n)$+nL))
|
| Determinant of Matrices with Integer Entries |
Bareiss algorithm with fast multiplication (Determinant of Matrices with Integer Entries Determinant of Matrices with Integer Entries) |
1968 |
$O(n^{4} L (\log(n)$ + L) \log(\log(n) + L)) |
$O(n^{2}(n*log(n)$+nL))
|
| Integer Relation |
Ferguson–Forcade algorithm (Integer Relation Integer Relation) |
1979 |
$O(n^{3})$ |
$O(n^{2})$
|
| Integer Relation |
LLL algorithm (Integer Relation Integer Relation) |
1982 |
$O(n^{4})$ |
$O(n^{2})$
|
| Integer Relation |
PSOS algorithm (Integer Relation Integer Relation) |
1988 |
$O(n^{3})$ |
$O(n^{2})$
|
| Integer Relation |
PSLQ algorithm (Integer Relation Integer Relation) |
1992 |
$O(n^{3})$ |
$O(n^{2})$
|
| Sequence-to-Graph Alignment |
Amir et al. (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) |
1997 |
$O(m(n \log m + E)$) |
$O(mn)$
|
| Sequence-to-Graph Alignment |
Navarro (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) |
2000 |
$O(n(V + E)$) |
$O(V)$
|
| Sequence-to-Graph Alignment |
HybridSpades (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) |
2015 |
$O(m(V \log(mV)$ + E)) |
$O(m*(V+E)$)
|
| Sequence-to-Graph Alignment |
V-ALIGN (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) |
2018 |
$O(mVE)$ |
$O(mV)$
|
| Sequence-to-Graph Alignment |
Rautiainen and Marschall (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) |
2017 |
$O(V+ mE)$ |
$O(\sqrt(m)V)$
|
| Sequence-to-Graph Alignment |
Jain, Chang (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) |
2019 |
$O(V+ mE)$ |
$O(V)$
|
| Sequence-to-Graph Alignment |
Rautiainen, Marschall (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) |
2019 |
$O(V + mE)$ |
$O(mV)$
|
| Discrete Logarithm Over Finite Fields |
Trial Multiplication (Discrete Logarithm Over Finite Fields Logarithm Calculations) |
1940 |
$O({2}^n)$ |
$O({1})$
|
| Discrete Logarithm Over Finite Fields |
Baby-step Giant-step (Discrete Logarithm Over Finite Fields Logarithm Calculations) |
1971 |
$O({2}^{\sqrt{n}})$ |
$O({2}^{\sqrt{n}})$
|
| Discrete Logarithm Over Finite Fields |
Function Field Sieve (FFS) (Discrete Logarithm Over Finite Fields Logarithm Calculations) |
1999 |
$O({2}^n)$ |
$O(n^{2/3})$?
|
| Discrete Logarithm Over Finite Fields, F_q |
Index calculus algorithm (Discrete Logarithm Over Finite Fields, F_q Logarithm Calculations) |
1922 |
$O(e^{(\sqrt({2}) \sqrt(n*logn))})$ |
$O(n+r^{2})$?
|
| Discrete Logarithm Over Finite Fields |
Number Field Sieve (NFS) (Discrete Logarithm Over Finite Fields Logarithm Calculations) |
1990 |
$O({2}^n)$ |
$O(n^{2/3})$
|
| Discrete Logarithm Over Finite Fields |
Pohlig-Hellman (Discrete Logarithm Over Finite Fields Logarithm Calculations) |
1978 |
$O({2}^{\sqrt{n}})$, only for primes; does much better for composites |
$O({2}^{\sqrt{n}})$ (though only for primes)
|
| Discrete Logarithm Over Finite Fields |
Pollard's rho algorithm (Discrete Logarithm Over Finite Fields Logarithm Calculations) |
1978 |
$O({2}^{(n/{2})})$ |
$O({1})$
|
| Discrete Logarithm Over Finite Fields |
Pollard's kangaroo algorithm (Discrete Logarithm Over Finite Fields Logarithm Calculations) |
1978 |
$O({2}^n)$ |
$O({1})$
|
| Self-Balancing Trees Creation |
AVL Tree ( Self-Balancing Trees Creation) |
1962 |
$O(n \log n)$ |
$O(n)$
|
| Self-Balancing Trees Creation |
Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Creation) |
1972 |
$O(n \log n)$ |
$O(n)$
|
| Self-Balancing Trees Creation |
Hopcroft 2-3 Tree ( Self-Balancing Trees Creation) |
1970 |
$O(n \log n)$ |
$O(n)$
|
| Self-Balancing Trees Creation |
Tarjan Splay Tree ( Self-Balancing Trees Creation) |
1985 |
$O(n \log n)$ |
$O(n)$
|
| Self-Balancing Trees Creation |
Bayer, McCreight B-Tree ( Self-Balancing Trees Creation) |
1970 |
$O(n*b*\log(n)$/\log(b))? |
$O(n)$
|
| Self-Balancing Trees Insertion |
Hopcroft 2-3 Tree ( Self-Balancing Trees Insertion) |
1970 |
$O(\log n)$ |
$O({1})$
|
| Self-Balancing Trees Insertion |
Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Insertion) |
1972 |
$O(\log n)$ |
$O({1})$
|
| Self-Balancing Trees Deletion |
Hopcroft 2-3 Tree ( Self-Balancing Trees Deletion) |
1970 |
$O(\log n)$ |
$O({1})$
|
| Self-Balancing Trees Deletion |
Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Deletion) |
1972 |
$O(\log n)$ |
$O({1})$
|
| Self-Balancing Trees Search |
Hopcroft 2-3 Tree ( Self-Balancing Trees Search) |
1970 |
$O(\log n)$ |
$O({1})$
|
| Self-Balancing Trees Search |
Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Search) |
1972 |
$O(\log n)$ |
$O({1})$
|
| Transitive Reduction Problem of Directed Graphs |
Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) |
1972 |
$O(n^omega)$ where omega is the exponent on boolean matrix multiplication |
$O(n^{2})$
|
| Transitive Reduction Problem of Directed Graphs |
Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) |
1972 |
$O(n^{2.807})$ |
$O(n^{2})$
|
| Transitive Reduction Problem of Directed Graphs |
Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) |
1978 |
$O(n^{2.8})$ |
$O(n^{2})$
|
| Transitive Reduction Problem of Directed Graphs |
Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) |
1979 |
$O(n^{2.78})$ |
$O(n^{2})$
|
| Transitive Reduction Problem of Directed Graphs |
Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) |
1980 |
$O(n^{2.52})$ |
$O(n^{2})$
|
| Transitive Reduction Problem of Directed Graphs |
Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) |
1980 |
$O(n^{2.518})$ |
$O(n^{2})$
|
| Transitive Reduction Problem of Directed Graphs |
Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) |
1981 |
$O(n^{2.495})$ |
$O(n^{2})$
|
| Transitive Reduction Problem of Directed Graphs |
Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) |
1986 |
$O(n^{2.48})$ |
$O(n^{2})$
|
| Transitive Reduction Problem of Directed Graphs |
Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) |
1990 |
$O(n^{2.372})$ |
$O(n^{2})$
|
| Transitive Reduction Problem of Directed Graphs |
Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) |
2014 |
$O(n^{2.373})$ |
$O(n^{2})$
|
| Transitive Reduction Problem of Directed Graphs |
Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) |
2014 |
$O(n^{2.371})$ |
$O(n^{2})$
|
| Transitive Reduction Problem of Directed Graphs |
Gries, Martin (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) |
1989 |
$O(n^{3})$ |
$O(n^{2})$
|
| Turnpike Problem |
Outside-In algorithm (Turnpike Problem Turnpike Problem) |
1991 |
$O({2}^n nlogn)$ |
$O(n)$
|
| Counting Solutions; Constructing solutions |
Naive Algorithm (Counting Solutions; Constructing solutions n-Queens Problem) |
1848 |
$O(n^n)$ |
$O(n)$
|
| Counting Solutions; Constructing solutions |
Naive + 1 queen per row restriction (Counting Solutions; Constructing solutions n-Queens Problem) |
1850 |
$O(n!)$ |
$O(n)$
|
| Counting Solutions; Constructing solutions |
Dijkstra (Counting Solutions; Constructing solutions n-Queens Problem) |
1972 |
$O(n!)$ |
$O(n)$
|
| Counting Solutions; Constructing solutions |
Nauck (Counting Solutions; Constructing solutions n-Queens Problem) |
1850 |
$O(n!)$ |
-
|
| Counting Solutions; Constructing solutions |
Gunther Determinants solution (Counting Solutions; Constructing solutions n-Queens Problem) |
1874 |
$O(n!)$ |
$O(n!)$ ?
|
| Counting Solutions |
Rivin, Zabih (Counting Solutions n-Queens Problem) |
1992 |
$O({8}^n*poly(n)$) |
$O({8}^n*n^{2})$
|
| Median String Problem with Unbounded Alphabets |
Naive Solution (Median String Problem with Unbounded Alphabets Median String Problem) |
1965 |
{2}^$O(n)$ |
$O(n)$
|
| Frequent Words with Mismatches Problem |
Naive solution ( Frequent Words with Mismatches Problem) |
1940 |
$O(n*f_{bin}(sigma-{1}, k, d)$) where f_{bin}(x, y, z) = sum_{i=0}^z C(y, i)*x^i |
$O(max(n*f_{bin}(sigma-{1}, k, d)$, sigma^k)) auxiliary where f_{bin}(x, y, z) = sum_{i=0}^z C(y, i)*x^i
|
| Tower of Hanoi |
Iteration based (Tower of Hanoi Tower of Hanoi) |
1883 |
$O({2}^n)$ |
$O(n)$
|
| Tower of Hanoi |
Recursion based (Tower of Hanoi Tower of Hanoi) |
1940 |
$O({2}^n)$ |
$O(n \log n)$
|
| Tower of Hanoi |
Non-recursion based (Tower of Hanoi Tower of Hanoi) |
1940 |
$O({2}^n)$ |
$O(n)$
|
| Tower of Hanoi |
Gray-code based (Tower of Hanoi Tower of Hanoi) |
1940 |
$O({2}^n)$ |
$O(n)$
|
| Tower of Hanoi |
Hanoi graph (Tower of Hanoi Tower of Hanoi) |
2008 |
$O({2}^n)$ |
-
|
| The Frequent Words Problem |
Naive solution (The Frequent Words Problem The Frequent Words Problem) |
1940 |
$O(n)$ |
$O(max(n, \sigma^k)$)
|
| The Frequent Words Problem |
Rabin Karp (The Frequent Words Problem The Frequent Words Problem) |
1987 |
$O(n)$ |
$O(max(n, \sigma^k)$)?
|
| Integral Equations |
Naive Implementation ( Integral Equations) |
1800 |
$O({2}^n)$ |
-
|
| Unkeyed Hash Functions |
MD5 (Unkeyed Hash Functions One-Way Hash Functions) |
1991 |
$O(n)$ |
$O({1})$ auxiliary?
|
| Unkeyed Hash Functions |
SHA-1 (Unkeyed Hash Functions One-Way Hash Functions) |
1993 |
$O(n)$ |
$O({1})$ auxiliary?
|
| Unkeyed Hash Functions |
RIPEMD-160 (Unkeyed Hash Functions One-Way Hash Functions) |
1996 |
$O(n)$ |
$O({1})$ auxiliary?
|
| Unkeyed Hash Functions |
bcrypt (Unkeyed Hash Functions One-Way Hash Functions) |
1999 |
$O(n)$ |
$O({1})$ auxiliary??
|
| One-Way Hash Functions |
Whirlpool ( One-Way Hash Functions) |
2000 |
$O(n)$ |
$O({1})$ auxiliary?
|
| Unkeyed Hash Functions |
SHA-2 (Unkeyed Hash Functions One-Way Hash Functions) |
2001 |
$O(n)$ |
$O({1})$ auxiliary?
|
| Unkeyed Hash Functions |
SHA-3 (Unkeyed Hash Functions One-Way Hash Functions) |
2015 |
$O(n)$ |
$O(b+d)$ auxiliary?
|
| Optional Key? |
BLAKE2 (Optional Key? One-Way Hash Functions) |
2012 |
$O(n)$ |
$O({1})$ auxiliary?
|
| Secret Sharing |
Shamir's scheme ( Secret Sharing) |
1979 |
$O(t^{2})$ for secret computation? (requires polynomial interpolation) |
$O({1})$ per person, $O(t^{2})$ to figure out secret?
|
| Secret Sharing |
Blakley's scheme ( Secret Sharing) |
1979 |
$O(t^{3})$ for secret computation? (requires linear solver) |
$O(t)$ per person, $O(t^{2})$ to figure out secret
|
| Solutions to Nonlinear Equations |
Bisection method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) |
-150 |
$O(n_{max})$ |
$O({1})$
|
| Solutions to Nonlinear Equations |
Regula Falsi method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) |
-200 |
$O(n_{max})$ |
$O({1})$
|
| Solutions to Nonlinear Equations |
Secant method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) |
-1400 |
$O(n_{max})$ |
$O({1})$
|
| Solutions to Nonlinear Equations |
Newton's method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) |
1669 |
$O(n_{max})$ |
$O({1})$
|
| Block Ciphers |
Lucifer / DES (Block Ciphers Block Ciphers) |
1976 |
$O(n)$ |
$O(n)$?
|
| Block Ciphers |
IDEA (Block Ciphers Block Ciphers) |
1991 |
$O(n)$ |
$O(n)$?
|
| Block Ciphers |
RC5 (Block Ciphers Block Ciphers) |
1994 |
$O(n)$ |
$O(k+rw)$?
|
| Block Ciphers |
Rijndael / AES (Block Ciphers Block Ciphers) |
2001 |
$O(n)$ |
$O(n)$?
|
| Block Ciphers |
Blowfish (Block Ciphers Block Ciphers) |
1993 |
$O(n)$ |
$O(n)$?
|
| 2-D Polynomial Interpolation |
Gaussian elimination (2-D Polynomial Interpolation Polynomial Interpolation) |
-150 |
$O(n^{3})$ |
$O(n^{2})$
|
| 2-D Polynomial Interpolation |
Bjorck (2-D Polynomial Interpolation Polynomial Interpolation) |
1970 |
$O(n^{2})$ |
$O(n)$
|
| 2-D Polynomial Interpolation |
Higham (2-D Polynomial Interpolation Polynomial Interpolation) |
1988 |
$O(n^{2})$ |
$O(n)$
|
| 2-D Polynomial Interpolation |
Calvetti, Reichel (2-D Polynomial Interpolation Polynomial Interpolation) |
1993 |
$O(n^{2})$ |
$O(n)$?
|
| Greatest Common Divisor |
Euclid's algorithm (Greatest Common Divisor Greatest Common Divisor) |
-300 |
$O(n^{2})$ |
$O(n)$
|
| Greatest Common Divisor |
Lehmer's GCD algorithm (Greatest Common Divisor Greatest Common Divisor) |
1940 |
$O(n^{2})$ |
$O(n)$
|
| Greatest Common Divisor |
Binary GCD algorithm (Greatest Common Divisor Greatest Common Divisor) |
1967 |
$O(n^{2})$ |
$O(n)$
|
| Greatest Common Divisor |
Sthele, Zimmermann (Greatest Common Divisor Greatest Common Divisor) |
2006 |
$O(n \log^{2} n \log \log n)$ |
$O(n)$??
|
| Weighted Activity Selection Problem |
Brute force algorithm (Weighted Activity Selection Problem Interval Scheduling) |
1940 |
$O({2}^n)$ |
$O(n)$
|
| Weighted Activity Selection Problem |
$O(n^3)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) |
1953 |
$O(n^{3})$ |
$O(n^{2})$
|
| Weighted Activity Selection Problem |
$O(n^2)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) |
1953 |
$O(n^{2})$ |
$O(n)$
|
| Weighted Activity Selection Problem |
$O(n\log n)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) |
1953 |
$O(n \log n)$ |
$O(n)$
|
| Unweighted Interval Scheduling, Online |
Fixed priority shortest job first (Unweighted Interval Scheduling, Online Interval Scheduling) |
1940 |
$O(n \log n)$ |
$O(n+k)$?
|
| Unweighted Interval Scheduling, Online |
Priority scheduling (Unweighted Interval Scheduling, Online Interval Scheduling) |
1940 |
$O(n)$ |
$O(n+k)$?
|
| Unweighted Interval Scheduling, Online |
Shortest remaining time first (Unweighted Interval Scheduling, Online Interval Scheduling) |
1940 |
$O(n)$ |
$O(n+k)$?
|
| Unweighted Interval Scheduling, Online |
First come, first served (Unweighted Interval Scheduling, Online Interval Scheduling) |
1940 |
$O(n)$ |
$O(n+k)$?
|
| Unweighted Interval Scheduling, Online |
Round-robin scheduling (Unweighted Interval Scheduling, Online Interval Scheduling) |
1940 |
$O(n)$ |
$O(n+k)$?
|
| Unweighted Interval Scheduling, Online |
Multilevel queue scheduling (Unweighted Interval Scheduling, Online Interval Scheduling) |
1940 |
$O(n)$ |
$O(n+k)$?
|
| Unweighted Interval Scheduling, Online |
Work-conserving schedulers (Unweighted Interval Scheduling, Online Interval Scheduling) |
1940 |
$O(n)$ |
-
|
| Deadlock Avoidance |
Banker's Algorithm (Deadlock Avoidance Deadlock avoidance) |
1966 |
$O(mn^{2})$ |
$O(mn)$
|
| Offline |
The theoretically optimal page replacement algorithm (Offline Page Replacements) |
1940 |
$O(n^{2})$ |
$O(k)$
|
| Online |
Not recently used (Online Page Replacements) |
1940 |
$O(nk)$? |
$O(k)$
|
| Online |
First-in, first-out (Online Page Replacements) |
1940 |
$O(nk)$? |
$O(k)$
|
| Online |
Second-chance (Online Page Replacements) |
1940 |
$O(nk)$? |
$O(k)$
|
| Online |
Clock (Online Page Replacements) |
1940 |
$O(nk)$? |
$O(k)$
|
| Online |
Least recently used (Online Page Replacements) |
1940 |
$O(nk)$? |
$O(k)$
|
| Online |
Random (Online Page Replacements) |
1940 |
$O(n)$ |
$O(k)$?
|
| Online |
Not frequently used (NFU) (Online Page Replacements) |
1940 |
$O(nk)$? |
$O(k)$
|
| Online |
Aging (Online Page Replacements) |
1940 |
$O(nk)$? |
$O(k)$
|
| Online |
Longest distance first (LDF) page replacement algorithm (Online Page Replacements) |
2017 |
$O(nk)$? |
$O(k)$
|
| Steal, No-Force |
ARIES (Steal, No-Force Recovery) |
1992 |
$O(n)$ |
$O(n)$?
|
| Arbitrary edge weights, Dense graph |
Dense APSP algorithm (Arbitrary edge weights, Dense graph Graph Diameter) |
- |
$O(V^{3} / {2}^(logV)$^{0.5}) |
-
|
| Arbitrary edge weights, Sparse graph |
Sparse APSP algorithm (Arbitrary edge weights, Sparse graph Graph Diameter) |
- |
$O(V^{2}logV+VE)$ |
-
|
| Unweighted |
Binary representation search with matrix multiplication (Unweighted Graph Diameter) |
- |
$O(V^omega log(V)$) where omega is the exponent on matrix multiplication |
$O(V^{2} logV)$
|
| Bounded integer weights |
Cygan, Gabow, Sankowski (Bounded integer weights Graph Diameter) |
2012 |
$O(M*V^omega*polylog(M, V)$) |
-
|
| Boolean Matrix Multiplication |
Output-Sensitive Quantum BMM (Boolean Matrix Multiplication Matrix Product) |
2018 |
O*( \min \{n^{1/3} L^{17/{3}0}, n^{1.5} L^{1/4}\}) |
-
|
| Boolean Matrix Multiplication (Combinatorial) |
(Boolean Matrix Multiplication (Combinatorial) Matrix Product) |
2018 |
$O(n^{3} / log^{2.25} n)$ |
-
|
| Boolean Matrix Multiplication |
O'Neil 1973 (Boolean Matrix Multiplication Matrix Product) |
1973 |
$O(n^{3})$ |
-
|
| Boolean Matrix Multiplication (Combinatorial) |
Method of Four Russians (Boolean Matrix Multiplication (Combinatorial) Matrix Product) |
1970 |
$O(n^{3}/(log n)$^{2}) |
-
|
| Boolean Matrix Multiplication (Combinatorial) |
Bansal, Williams (Boolean Matrix Multiplication (Combinatorial) Matrix Product) |
2009 |
$O(n^{3} * (log log n)$^{2} / log^{2.25} n) |
-
|
| Boolean Matrix Multiplication (Combinatorial) |
Bansal, Williams (Boolean Matrix Multiplication (Combinatorial) Matrix Product) |
2009 |
$O(n^{3} * (log log n)$^{2} / (w * (log n)^{7}/{6})) |
-
|
| Boolean Matrix Multiplication (Combinatorial) |
Chan (Boolean Matrix Multiplication (Combinatorial) Matrix Product) |
2015 |
$O(n^{3} * (log log n)$^{3} / log^{3} n) |
-
|
| Boolean Matrix Multiplication (Combinatorial) |
Chan (Boolean Matrix Multiplication (Combinatorial) Matrix Product) |
2015 |
$O(n^{3} * (log w)$^{3} / (w * log^{2} n)) |
-
|
| Boolean Matrix Multiplication (Combinatorial) |
Yu (Boolean Matrix Multiplication (Combinatorial) Matrix Product) |
2015 |
$O(n^{3}*poly(log log n)$/log^{4} n) |
-
|
| Online Matrix Vector Multiplication (OMV) |
Williams ( Online Matrix Vector Multiplication (OMV)) |
2007 |
$O(n^{3} / (log n)$^{2}) |
-
|
| Online Matrix Vector Multiplication (OMV) |
Larsen, Williams (Theorem 1.1) ( Online Matrix Vector Multiplication (OMV)) |
2017 |
$O(n^{3} / {2}^(Omega(sqrt(log n)$))) |
-
|
| Online Matrix Vector Multiplication (OMV) |
Larsen, Williams (follows from Theorem 2.1) ( Online Matrix Vector Multiplication (OMV)) |
2017 |
$O(n^({11}/{4})$ / sqrt(log n)) |
-
|
| Negative Triangle |
( Negative Triangle) |
2018 |
- |
-
|
| Sorting - Comparison |
Parallel Merge Sort - Cole (1) ( Sorting - Comparison) |
1988 |
$O(logn)$ |
-
|
| Sorting - Comparison |
Parallel Merge Sort - Cole (2) ( Sorting - Comparison) |
1988 |
$O(logn)$ |
-
|
| Maximum Flow |
MKM Algorithm ( Maximum Flow) |
1978 |
$O(V^{3})$ |
$O(E)$
|
| Maximum Flow |
Galil ( Maximum Flow) |
1978 |
$O(V^({5}/{3})$E^({2}/{3})) |
$O(E)$
|
| Maximum Flow |
Shiloach ( Maximum Flow) |
1981 |
$O(V^{3}*log(V)$/p) |
$O(E)$
|
| Maximum Flow |
Gabow ( Maximum Flow) |
1985 |
$O(VE*logU)$ |
$O(E)$
|
| Maximum Flow |
Lee, Sidford ( Maximum Flow) |
2014 |
$O(E*sqrt(V)$*log^{2}(U)*polylog(E, V, log(U)) |
$O(E)$
|
| Maximum Flow |
Madry ( Maximum Flow) |
2016 |
$O(E^({10}/{7})$U^({1}/{7})polylog(V, E, log U)) |
$O(E)$
|
| Maximum Flow |
Kathuria, Liu, Sidford ( Maximum Flow) |
2020 |
$O(E^({1}+o({1})$)/sqrt(eps)) |
$O(E)$ or $O(V^{2})$ ?
|
| Maximum Flow |
Kathuria, Liu, Sidford ( Maximum Flow) |
2020 |
$O(E^({4}/{3}+o({1})$)U^({1}/{3})) |
$O(E)$ or $O(V^{2})$ ?
|
| Maximum Flow |
Brand et al ( Maximum Flow) |
2021 |
$O((E+V^{1.5})$log(U)polylog(V, E, log U)) |
$O(E)$
|
| Maximum Flow |
Gao, Liu, Peng ( Maximum Flow) |
2021 |
$O(E^({3}/{2}-{1}/{328})$*log(U)*polylog(E)) |
$O(E)$
|
| Maximum Flow |
Chen et al ( Maximum Flow) |
2022 |
$O(E^({1}+o({1})$)*log(U)) |
$O(E)$
|
| Integer Maximum Flow |
Goldberg & Rao (Parallel) (Integer Maximum Flow Maximum Flow) |
1997 |
$O(V^{1.66} log(V)$ log(U)) |
$O(V^{2})$
|
| Integer Maximum Flow |
Goldberg & Rao (Parallel) (Integer Maximum Flow Maximum Flow) |
1997 |
$O(E^{0.5} V log(V)$ log(U)) |
$O(V^{2})$
|
| Matrix Multiplication |
Method of Four Russians ( Matrix Multiplication) |
1970 |
$O(n^{3}/log n)$ |
-
|
| Matrix Multiplication |
Alman, Vassilevska Williams ( Matrix Multiplication) |
2020 |
$O(n^{2.37285956})$ |
$O(n^{2})$
|
| 5 - Graph Coloring |
Byskov ( 5 - Graph Coloring) |
2004 |
$O({2.1592}^n)$ |
-
|
| 5 - Graph Coloring |
Bjorklund, Husfeldt, Theorem 1 ( 5 - Graph Coloring) |
2006 |
$O({2}^n*poly(n)$) |
$O({2}^n*poly(n)$)
|
| 5 - Graph Coloring |
Bjorklund, Husfeldt, Proposition 2 ( 5 - Graph Coloring) |
2006 |
$O({2.2461}^n)$ |
$O(poly(n)$)
|
| 5 - Graph Coloring |
Zamir ( 5 - Graph Coloring) |
2021 |
$O(({2}-eps)$^n) for some eps>{0} |
-
|
| 6 - Graph Coloring |
Byskov, Theorem 14 ( 6 - Graph Coloring) |
2004 |
$O({2.3289}^n)$ |
-
|
| 6 - Graph Coloring |
Byskov, Theorem 20 ( 6 - Graph Coloring) |
2004 |
$O({2.2680}^n)$ |
$O({2}^n)$
|
| 6 - Graph Coloring |
Bjorklund, Husfeldt, Theorem 1 ( 6 - Graph Coloring) |
2006 |
$O({2}^n*poly(n)$) |
$O({2}^n*poly(n)$)
|
| 6 - Graph Coloring |
Bjorklund, Husfeldt, Proposition 2 ( 6 - Graph Coloring) |
2006 |
$O({2.2461}^n)$ |
$O(poly(n)$)
|
| 6 - Graph Coloring |
Zamir ( 6 - Graph Coloring) |
2021 |
$O(({2}-eps)$^n) for some eps>{0} |
-
|
| Chromatic Number |
Christofides ( Chromatic Number) |
1971 |
$O(n!*poly(n)$) |
$O(poly(n)$)
|
| Chromatic Number |
Lawler ( Chromatic Number) |
1976 |
$O(mn({1}+{3}^({1}/{3})$)^n) |
$O({2}^n*log(n)$)
|
| Chromatic Number |
Eppstein ( Chromatic Number) |
2003 |
$O(({4}/{3}+{3}^({4}/{3})$/{4})^n) ~ $O({2.4151}^n)$ |
$O({2}^n)$
|
| Chromatic Number |
Byskov ( Chromatic Number) |
2004 |
$O({80}^(n/{5})$) ~ $O({2.4023}^n)$ |
$O({2}^n)$
|
| Chromatic Number |
Bjorklund, Husfeldt, Theorem 1 ( Chromatic Number) |
2006 |
$O({2}^n*poly(n)$) |
$O({2}^n*poly(n)$)
|
| Chromatic Number |
Bjorklund, Husfeldt, Proposition 2 ( Chromatic Number) |
2006 |
$O({2.2461}^n)$ |
$O(poly(n)$)
|
| Chromatic Number |
Koivisto ( Chromatic Number) |
2006 |
$O({2}^n*poly(n)$) |
-
|
| #2 - Graph Coloring |
BFS/DFS for connected components ( #2 - Graph Coloring) |
- |
$O(m)$ |
$O(n)$ auxiliary
|
| #3 - Graph Coloring |
Angelsmark, Jonsson ( #3 - Graph Coloring) |
2003 |
$O({1.7879}^n)$ |
-
|
| #3 - Graph Coloring |
Fürer, Kasiviswanathan ( #3 - Graph Coloring) |
2005 |
$O({1.7702}^n*poly(n)$) |
-
|
| #3 - Graph Coloring |
Fomin; Gaspers & Saurabh ( #3 - Graph Coloring) |
2007 |
$O({1.6262}^n)$ |
-
|
| #4 - Graph Coloring |
Fomin; Gaspers & Saurabh ( #4 - Graph Coloring) |
2007 |
$O({1.9464}^n)$ |
-
|
| Chromatic Polynomial |
Zykov (deletion-contraction) ( Chromatic Polynomial) |
1949 |
$O((({1}+sqrt5)$/{2})^(n+m)) |
-
|
| Chromatic Polynomial |
Bjorklund, Husfeldt, Proposition 3 ( Chromatic Polynomial) |
2006 |
$O({2}^n*poly(n)$) |
$O({2}^n*poly(n)$) => $O({1.292}^n)$
|
| Chromatic Polynomial |
Koivisto ( Chromatic Polynomial) |
2006 |
$O({2}^n*poly(n)$) |
-
|
| General |
LU decomposition (General Linear system of equations) |
- |
O (n^{3}) |
$O(n^{2})$
|
| General |
Matrix inverse (General Linear system of equations) |
- |
$O(n^omega)$ where omega is the exponent on the complexity of matrix multiplication;
currently $O(n^{2.37285956})$ |
$O(n^{2})$
|
| Toeplitz |
Asymptotically fast Toeplitz algorithms (Toeplitz Linear system of equations) |
2008? |
$O(n*log^{2}(n)$) |
$O(n*log^{2}(n)$)?
|
| Sparse |
Peng, Vempala (Sparse Linear system of equations) |
2020 |
$O(max(m^{(omega-{2})/(omega-{1})}*n^{2}, n^{({5}*omega-{4})/(omega+{1})})*log^{2}(k/epsilon))$ where omega is the exponent on the complexity of matrix multiplication;
currently $O(n^{2.331642})$ || -
|
| Linear Programming |
Vaidya ( Linear Programming) |
1987 |
$O(((m+n)$n^{2}+(m+n)^{1.5}*n)L^{2} logL loglogL) |
$O((nm+n^{2})$L)?
|
| Linear Programming |
Vaidya ( Linear Programming) |
1989 |
$O((m+n)$^{1.5}*n*L^{2} logL loglogL) |
$O((nm+n^{2})$L)?
|
| Linear Programming |
Jiang, Song, Weinstein and Zhang ( Linear Programming) |
2020 |
$O(n^(max(omega, {2.5}-alpha/{2}, {37}/{18}))*polylog(n, m, L))$, where omega is the exponent on matrix multiplication, alpha is the dual exponent of matrix multiplication;
currently $O(n^{2.37285956})$ || -
|
| Counting number of intersection points / line segments |
CHAZELLE 1986 (Counting number of intersection points / line segments Line segment intersection) |
1986 |
$O(n^{1.695})$ |
$O(n)$
|
| Reporting all intersection points / general polygons |
NIEVERGELT. J.. AND PREPARATA (Section 2) (Reporting all intersection points / general polygons Line segment intersection) |
1982 |
$O((n+k)$log n) |
$O(n+k)$
|
| d-dimensional Convex Hull |
Seidel's Shelling Algorithm (d-dimensional Convex Hull Convex Hull) |
1986 |
$O(n^{2}+f_1*log(n)$) |
-
|
| d-dimensional Convex Hull |
Chand-Kapur, Gift Wrapping (d-dimensional Convex Hull Convex Hull) |
1970 |
$O(n*f_1)$ |
-
|
| d-dimensional Convex Hull |
N-dimensional Quickhull (d-dimensional Convex Hull Convex Hull) |
1996 |
$O(n*f(h)$/h) where f(h) denotes the maximum number of facets with h vertices |
-
|
| 2-dimensional Convex Hull, Online |
Online 2-d Convex Hull, Preparata (2-dimensional Convex Hull, Online Convex Hull) |
1979 |
$O(logn)$ per operation, $O(n*log(n)$) total |
$O(n)$
|
| 2-dimensional Convex Hull, Dynamic |
Dynamic 2-d Convex Hull, Overmars and van Leeuwen (2-dimensional Convex Hull, Dynamic Convex Hull) |
1980 |
$O(log^{2}(n)$) per operation, $O(n*log^{2}(n)$) total |
-
|
| 2-dimensional Convex Hull, Dynamic |
(many more...) (2-dimensional Convex Hull, Dynamic Convex Hull) |
- |
- |
-
|
| SCCs |
Geldenhuys-Valmari (SCCs Strongly Connected Components) |
2004 |
$O(V+E)$ |
$O(V)$?
|
| SCCs |
Multistep (SCCs Strongly Connected Components) |
2014 |
$O(V^{2}+E)$ |
$O(V+E)$ total?
|
| Undirected, General MST |
Prim's algorithm + binary heap (Undirected, General MST Minimum Spanning Tree (MST)) |
- |
$O(ElogV)$ |
$O(V)$ auxiliary?
|
| Undirected, General MST |
Fredman & Tarjan (Undirected, General MST Minimum Spanning Tree (MST)) |
1987 |
$O(E*beta(E, V)$) where beta(m, n) = min(i such that log^(i)(n)≤m/n); this is also $O(E (log-star)$V) |
$O(E)$ auxiliary?
|
| Undirected, Dense MST |
Cheriton-Tarjan (dense) (Undirected, Dense MST Minimum Spanning Tree (MST)) |
1976 |
$O(E)$ |
$O(E)$ auxiliary?
|
| Undirected, Planar MST |
Cheriton-Tarjan (planar) (Undirected, Planar MST Minimum Spanning Tree (MST)) |
1976 |
$O(V)$ |
$O(V)$ auxiliary
|
| Undirected, General MST |
Gabow et al, Section 2 (Undirected, General MST Minimum Spanning Tree (MST)) |
1986 |
$O(E*log(beta(E, V)$)) |
$O(E)$ auxiliary?
|
| Undirected, Integer Weights MST |
Fredman & Willard (Undirected, Integer Weights MST Minimum Spanning Tree (MST)) |
1991 |
$O(E+V)$ |
-
|
| Undirected, General MST |
Pettie, Ramachandran (Undirected, General MST Minimum Spanning Tree (MST)) |
2002 |
unknown but optimal |
$O(E)$ auxiliary?
|
| Directed (Optimum Branchings), General MST |
Chu-Liu-Edmonds Algorithm (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST)) |
1965 |
$O(EV)$ |
$O(E+V)$
|
| Directed (Optimum Branchings), General MST |
Tarjan (directed, general) (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST)) |
1987 |
$O(ElogV)$ |
$O(E)$
|
| Directed (Optimum Branchings), Super Dense MST |
Tarjan (directed, dense) (Directed (Optimum Branchings), Super Dense MST Minimum Spanning Tree (MST)) |
1987 |
$O(V^{2})$ |
$O(E)$
|
| Directed (Optimum Branchings), General MST |
Gabow, Galil, Spencer (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST)) |
1984 |
$O(VlogV+Eloglog(logV/log(E/V + {2})$)) |
$O(E)$
|
| Directed (Optimum Branchings), General MST |
Gabow et al, Section 3 (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST)) |
1986 |
$O(E+VlogV)$ |
$O(E+V)$
|
| k-dimensional space, Euclidean metric |
Khuller, Matias (k-dimensional space, Euclidean metric Closest Pair Problem) |
1995 |
infinite (can be upper bounded by $O(n^{2})$) |
$O(n)$
|
| nonnegative integer weights |
Dial's Algorithm (nonnegative integer weights Shortest Path (Directed graphs)) |
1969 |
$O(E+LV)$ |
$O(V+L)$
|
| positive integer weights; assumes constant-time multiplication |
Thorup (positive integer weights; assumes constant-time multiplication Shortest Path (Undirected graphs)) |
1999 |
$O(E)$ |
$O(E)$
|
| Unweighted |
Brandes (Unweighted Betweenness Centrality (BC)) |
2000 |
$O(nm)$ |
$O(n + m)$
|
| Weighted |
Brandes (Weighted Betweenness Centrality (BC)) |
2000 |
$O(nm + n^{2} \log n)$ |
$O(n + m)$
|
| Directed, Weighted (Arbitrary weights) |
Johnson's algorithm (Directed, Weighted (Arbitrary weights) All-Pairs Shortest Paths (APSP)) |
1977 |
$O(V^{2} log V + VE)$ |
-
|
| Directed, Unweighted |
Zwick 2002 (Directed, Unweighted All-Pairs Shortest Paths (APSP)) |
2002 |
$O(V^{2.575})$ |
-
|
| CNF-SAT |
Davis-Putnam-Logemann-Loveland Algorithm (DPLL) (CNF-SAT Boolean Satisfiability) |
1961 |
$O({2}^n)$ |
$O(n)$
|
| CNF-SAT |
Conflict-Driven Clause Learning (CDCL) (CNF-SAT Boolean Satisfiability) |
1999 |
$O({2}^n)$ |
-
|
| CNF-SAT |
GSAT (CNF-SAT Boolean Satisfiability) |
1992 |
$O(n*mt*mf)$ |
$O(n)$
|
| CNF-SAT |
WalkSAT (CNF-SAT Boolean Satisfiability) |
1994 |
$O(n*mt*mf)$ |
$O(n)$
|
| CNF-SAT |
Quantum Adiabatic Algorithm (QAA) (CNF-SAT Boolean Satisfiability) |
2001 |
$O({2}^n)$ |
$O(poly(n)$)
|
| Renamable Horn |
Lewis 1978 (Renamable Horn Boolean Satisfiability) |
1978 |
$O(mn^{2})$ |
-
|
| k-SAT |
Paturi, Pudlák, Saks, Zane (PPSZ) 2005 (k-SAT Boolean Satisfiability) |
2005 |
O^*({2}^{n-cn/k}) |
$O(kn)$
|
| 3SAT |
Hertli (Modified PPSZ) (3SAT Boolean Satisfiability) |
2014 |
$O({1.30704}^n)$ |
$O(kn)$
|
| 4SAT |
Hertli (Modified PPSZ) (4SAT Boolean Satisfiability) |
2014 |
$O({1.46899}^n)$ |
$O(kn)$
|
| NAE 3SAT |
Shi 2009 (NAE 3SAT Boolean Satisfiability) |
2009 |
$O({12}m*t_extract + {2}m*t_discard + {2}n*t_append + (n+{2}m)$*t_merge + (n-{1})*t_amplify) |
$O(n)$ tubes or $O({2}^n)$ library strands
|
| Informed Search |
Anytime Dynamic A* (ADA*) ( Informed Search) |
2005 |
$O(b^d)$ |
$O(b^d)$
|
| Informed Search |
D* Lite ( Informed Search) |
2005 |
$O(b^d)$ |
$O(b^d)$
|
| Informed Search |
Focused D* ( Informed Search) |
2005 |
$O(b^d)$ |
$O(b^d)$
|
| String Search |
Wu and Manber, Fuzzy String Matching ( String Search) |
1992 |
$O(nk \lceil m/w \rceil)$ |
$O(ms + k \lceil m/w \rceil)$
|
| Edit distance |
Wagner-Fischer algorithm (Edit distance Sequence Alignment) |
1974 |
$O(mn)$ |
$O(m)$
|
| Edit sequence |
Wagner-Fischer algorithm (Edit sequence Sequence Alignment) |
1974 |
$O(mn)$ |
$O(mn)$
|
| Edit sequence |
Masek, Paterson (Edit sequence Sequence Alignment) |
1980 |
$O(mn/log(n)$) |
$O(mn/log(n)$)
|
| bipartite graph |
Alt, Blum, Mehlhorn, Paul (bipartite graph Maximum cardinality matching) |
1991 |
$O(V^{1.5}*(E/logV)$^{0.5}) |
$O(E)$ auxiliary?
|
| general graph |
Blossom Algorithm (general graph Maximum cardinality matching) |
1961 |
$O(V^{2}E)$ |
$O(E)$ auxiliary?
|
| general graph |
Micali, Vazirani (general graph Maximum cardinality matching) |
1980 |
$O(V^{0.5} E)$ |
$O(E)$ auxiliary?
|
| Minimum value in each row of an implicitly-defined totally monotone matrix |
Divide and Conquer ( Minimum value in each row of an implicitly-defined totally monotone matrix) |
1987 |
$O(m*log(n)$) |
$O(log(n)$) auxiliary?
|
| All permutations |
Wells ( All permutations) |
1961 |
$O({1})$ per permutation |
$O(n)$ auxiliary
|
| All permutations |
Langdon ( All permutations) |
1967 |
$O(n)$ per permutation |
$O({1})$ auxiliary
|
| All permutations |
Ord-Smith ( All permutations) |
1967 |
$O({1})$ per permutation |
$O(n)$ auxiliary
|
| All permutations |
Ives' algorithm c ( All permutations) |
1976 |
$O({1})$ per permutation |
$O(n)$ auxiliary
|
| All permutations |
Zaks' prefix reversal algorithm ( All permutations) |
1984 |
$O(n)$ on specific permutations |
$O(n)$ auxiliary (see NEXT algorithm in same paper)
|
| bipartite (i.e. assignment), general |
Edmonds-Karp (bipartite (i.e. assignment), general Maximum-weight matching) |
1972 |
$O(n*(SP+))$ where $(SP+)$ denotes the time for one SSSP computation on a nonnegatively weighted graph. Initially $O(n^{3})$ |
$O(n^{2})$
|
| bipartite (i.e. assignment), general |
Johnson (Edmonds-Karp-based) (bipartite (i.e. assignment), general Maximum-weight matching) |
1975 |
$O(mn*log(n)$/log({2}+m/n)) |
$O(n^{2})$
|
| bipartite (i.e. assignment), general |
Fredman-Tarjan (Edmonds-Karp-based) (bipartite (i.e. assignment), general Maximum-weight matching) |
1984 |
$O(mn+n^{2}log(n)$) |
$O(n^{2})$
|
| general |
Gabow (general Maximum-weight matching) |
1974 |
$O(n^{3})$ |
-
|
| general |
Galil, Micali, Gabow (general Maximum-weight matching) |
1982 |
$O(mn*log(n)$) |
-
|
| general |
Gabow, Galil, Spencer (general Maximum-weight matching) |
1989 |
$O(mn*log(log(log(n)$/log({2}+m/n))) + n^{2}*log(n)) |
-
|
| general |
Gabow (general Maximum-weight matching) |
1990 |
$O(mn+n^{2}log(n)$) |
$O(m)$
|
| General Root Computation |
Illinois Algorithm (General Root Computation Root Computation) |
1971 |
$O(n_max)$ |
$O({1})$
|
| General Root Computation |
Anderson–Björck algorithm (General Root Computation Root Computation) |
1973 |
$O(n_max)$ |
$O({1})$
|
| General Root Computation |
ITP Method (General Root Computation Root Computation) |
1940? |
$O(n_0+log((b-a)$/epsilon)) |
$O({1})$
|
| Root Computation with continuous derivatives (up to d) |
Householder's Method (Root Computation with continuous derivatives (up to d) Root Computation) |
1940(?) |
$O(d*n_max)$? |
$O(d)$
|
| General Root Computation |
Steffensen's method (General Root Computation Root Computation) |
1940(?) |
$O(n_max)$ |
$O({1})$
|
| General Root Computation |
Inverse quadratic interpolation (General Root Computation Root Computation) |
1940(?) |
$O(n_max)$ |
$O({1})$
|
| General Root Computation |
Brent-Dekker Method (General Root Computation Root Computation) |
1973 |
$O(n_max)$ |
$O({1})$
|
| Off-Line Lowest Common Ancestor |
Aho, Hopcroft, and Ullman (Offline) (Off-Line Lowest Common Ancestor Lowest Common Ancestor) |
1976 |
$O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function |
$O(n)$
|
| Lowest Common Ancestor with Static Trees |
Aho, Hopcroft, and Ullman (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) |
1976 |
$O((m+n)$*log(log(n))) |
$O(n*log(log(n)$))
|
| Lowest Common Ancestor with Linking |
Aho, Hopcroft, and Ullman (Linking) (Lowest Common Ancestor with Linking Lowest Common Ancestor) |
1976 |
$O((m+n)$*log(n)) |
$O(n*log(n)$)
|
| Lowest Common Ancestor with Static Trees |
Modified van Leeuwen (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) |
1976 |
$O(n+m*log(log(n)$)) |
$O(n)$
|
| Lowest Common Ancestor with Linking Roots |
Modified van Leeuwen (Linking Roots) (Lowest Common Ancestor with Linking Roots Lowest Common Ancestor) |
1976 |
$O(n+m*log(log(n)$)) |
$O(n)$
|
| Lowest Common Ancestor with Linking |
Sleator and Tarjan (Linking) (Lowest Common Ancestor with Linking Lowest Common Ancestor) |
1983 |
$O(n+m*log(n)$) |
$O(n)$
|
| Lowest Common Ancestor with Linking and Cutting |
Sleator and Tarjan (Linking and Cutting) (Lowest Common Ancestor with Linking and Cutting Lowest Common Ancestor) |
1983 |
$O(n+m*log(n)$) |
$O(n)$
|
| Lowest Common Ancestor with Static Trees |
Harel, Tarjan (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) |
1984 |
$O(n+m)$ |
$O(n)$
|
| Lowest Common Ancestor with Linking Roots |
Harel, Tarjan (Linking Roots) (Lowest Common Ancestor with Linking Roots Lowest Common Ancestor) |
1984 |
$O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function |
$O(n)$
|
| Lowest Common Ancestor with Static Trees |
Schieber; Vishkin (Parallel) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) |
1988 |
$O(m+log(n)$) |
$O(n)$ total (auxiliary?)
|
| Lowest Common Ancestor with Static Trees |
Fischer, Heun (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) |
2006 |
$O(m+n)$ |
$O(n)$
|
| Lowest Common Ancestor with Static Trees |
Kmett (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) |
2015 |
$O(m*log(h)$) |
-
|
| Enumerating Maximal Cliques, arbitrary graph |
Kazuhisa Makino, Takeaki Uno; Section 6 (Enumerating Maximal Cliques, arbitrary graph Clique Problems) |
2004 |
$O(delta^{4})$ |
$O(n+m)$ auxiliary(?)
|
| Integer 3SUM |
Textbook Sort-and-Binary-Search (Integer 3SUM 3SUM) |
- |
$O(n^{2} log n)$ |
$O(n)$
|
| Integer 3SUM |
Textbook Sort-and-Two-Sided-Traversal (Integer 3SUM 3SUM) |
- |
$O(n^{2})$ |
$O(n)$
|
| Integer 3SUM |
Baran, Demaine, Patrascu (Integer 3SUM 3SUM) |
2008 |
$O(n^{2}/max(w/(log w)$^{2}, (log n)^{2}/(log log n)^{2})) |
-
|
| Integer 3SUM |
Baran, Demaine, Patrascu (Integer 3SUM 3SUM) |
2008 |
$O(n^{2}/(w^{2}/(log w)$^{2})) |
-
|
| Integer 3SUM |
Baran, Demaine, Patrascu (Integer 3SUM 3SUM) |
2008 |
$O(n^{2}/MB)$ |
-
|
| Integer 3SUM |
Baran, Demaine, Patrascu (Integer 3SUM 3SUM) |
2008 |
$O(n^{2}*(log M)$^{2}/MB) |
-
|
| Real 3SUM |
Gronlund, Pettie (Real 3SUM 3SUM) |
2014 |
$O(n^{2}/((log n)$/(log log n))^{2}/{3}) |
-
|
| Real 3SUM |
Gronlund, Pettie (Real 3SUM 3SUM) |
2014 |
$O(n^{2}*(log log n)$^{2}/(log n)) |
-
|
| Real 3SUM |
Freund (Real 3SUM 3SUM) |
2017 |
$O(n^{2}*(log log n)$/(log n)) |
-
|
| Real 3SUM |
Chan (Real 3SUM 3SUM) |
2018 |
$O(n^{2}*(log log n)$^{$O({1})$}/(log n)^{2}) |
-
|
| The Vertex Cover Problem |
Exhaustive search (The Vertex Cover Problem The Vertex Cover Problem) |
1940 |
$O(C(n, k)$) (i.e. (n, k) binomial coefficient) |
$O(k)$ auxiliary
|
| The Vertex Cover Problem |
Downey, Fellows (The Vertex Cover Problem The Vertex Cover Problem) |
1995 |
$O(kn+{2}^k k^{2})$ |
$O(k^{2})$ auxiliary
|
| The Vertex Cover Problem |
Papadimitriou and M Yannakakis 1996 + Buss (The Vertex Cover Problem The Vertex Cover Problem) |
1996 |
$O({3}^k k^{2}+kn)$ |
$O(k^{2})$ auxiliary?
|
| The Vertex Cover Problem |
Stege, Fellows (The Vertex Cover Problem The Vertex Cover Problem) |
1999 |
$O(kn+max(({1.25542})$^k k^{2}, ({1.2906})^k k) |
$O(k^{3})$ auxiliary? (potentially $O(k^{2})$??)
|
| The Vertex Cover Problem |
Stege, Fellows + Interleaving method (Niedermeier, Rossmanith) (The Vertex Cover Problem The Vertex Cover Problem) |
2000 |
$O(kn+({1.2906})$^k) |
$O(k^{3})$ auxiliary? (potentially $O(k^{2})$??)
|
| 1-dimensional |
Wen (1-dimensional Maximum subarray problem) |
1995 |
$O(log n)$ |
-
|
| 2-dimensional |
brute force (2-dimensional Maximum subarray problem) |
1977 |
$O(n^{6})$ |
$O({1})$ auxiliary
|
| 2-dimensional |
Bentley (2-dimensional Maximum subarray problem) |
1984 |
$O(n^{3})$ |
$O(n^{2})$ auxiliary?
|
| 2-dimensional |
Smith (2-dimensional Maximum subarray problem) |
1987 |
$O(n^{3})$ |
$O(log n)$ auxiliary?
|
| 2-dimensional |
Tamaki, Tokuyama (exact) (2-dimensional Maximum subarray problem) |
1998 |
$O(n^{3} * ((log log n)$/(log n))^({1}/{2})) |
-
|
| 2-dimensional |
Tamaki, Tokuyama (approximate) (2-dimensional Maximum subarray problem) |
1998 |
$O(n^(omega)$ * (-log(epsilon))/epsilon) |
-
|
| 2-dimensional |
Takaoka (2-dimensional Maximum subarray problem) |
2002 |
$O(n^{3} * ((log log n)$/(log n))^({1}/{2})) |
-
|
| 2-dimensional |
Smith (2-dimensional Maximum subarray problem) |
1987 |
$O(log^{2} n)$ |
-
|
| 2-dimensional |
KALYAN PERUMALLA and NARSINGH DEO (2-dimensional Maximum subarray problem) |
1995 |
$O(log n)$ |
-
|
| 2-dimensional |
Wen (2-dimensional Maximum subarray problem) |
1995 |
$O(log n)$ |
-
|
| Minimum Wiener Connector problem |
Exhaustive search (Minimum Wiener Connector problem Wiener Index) |
2015 |
{2}^($O(n)$) |
$O(n)$ auxiliary
|
| k-OV |
Exhaustive search (k-OV Orthogonal Vectors) |
- |
$O(d*n^k)$ |
$O(k)$ auxiliary
|
| OV |
Abboud, Williams, Yu (OV Orthogonal Vectors) |
2015 |
$O(n^{({2}-{1}/O(d/log(n)))})$ |
-
|
| k-OV |
Reduction to Abboud, Williams, Yu (k-OV Orthogonal Vectors) |
2015 |
$O(n^{(k-{1}/O(d/log(n)))})$ |
-
|
| OV |
Chan, Williams (OV Orthogonal Vectors) |
2016 |
$O(n^{({2}-{1}/O(d/log(n)))})$ |
-
|
| k-OV |
Reduction to Chan, Williams (k-OV Orthogonal Vectors) |
2016 |
$O(n^{(k-{1}/O(d/log(n)))})$ |
-
|
| k-Clique |
Brute force enumeration (k-Clique k-Clique Problem) |
- |
$O(n^k)$ |
$O(k)$ auxiliary
|
| k-Clique |
Nesetril, Poljak (k-Clique k-Clique Problem) |
1985 |
$O(n^(k-({3}-\omega)*floor(k/{3}))$ where omega is the exponent on matrix multiplication |
$O(n^({2}k/{3})$) ish
|
| 3-Clique |
APSP algorithm (3-Clique Min-Weight k-Clique Problem) |
- |
$O(n^{3} / {2}^(log n)$^{0.5}) |
-
|
| 3-Clique |
Gronlund, Pettie (3-Clique Exact-Weight k-Clique Problem) |
2014 |
$O(n^{3}*(log log n)$^{2}/(log n)) |
-
|
| Graph Isomporhism, Trivalent Graphs |
Babai 1980 (Graph Isomporhism, Trivalent Graphs Graph Isomorphism Problem) |
1980 |
\exp(cn^{\frac{1}{2}} \log n) |
$O(n^{2})$
|
| Graph Isomorphism, Bounded Vertex Valences |
Babai 1980 (Graph Isomorphism, Bounded Vertex Valences Graph Isomorphism Problem) |
1980 |
\exp(n^{\frac{1}{2} + $O({1})$}) |
$O(n^{2})$
|
| Self-Balancing Trees Creation |
Scapegoat Tree ( Self-Balancing Trees Creation) |
1989 |
$O(nlogn)$ |
$O(n)$
|
| Self-Balancing Trees Creation |
Treap ( Self-Balancing Trees Creation) |
1989 |
$O(nlogn)$ |
$O(n)$
|
| Self-Balancing Trees Creation |
Tango Tree ( Self-Balancing Trees Creation) |
2004 |
$O(nlogn)$ |
$O(n)$
|
| Self-Balancing Trees Insertion |
AVL Tree ( Self-Balancing Trees Insertion) |
1962 |
$O(logn)$ |
$O({1})$
|
| Self-Balancing Trees Insertion |
Tarjan Splay Tree ( Self-Balancing Trees Insertion) |
1985 |
$O(n)$ |
$O({1})$
|
| Self-Balancing Trees Insertion |
Bayer, McCreight B-Tree ( Self-Balancing Trees Insertion) |
1970 |
$O(b*log(n)$/log(b))? |
$O(b)$?
|
| Self-Balancing Trees Insertion |
Scapegoat Tree ( Self-Balancing Trees Insertion) |
1989 |
$O(n)$ |
$O({1})$?
|
| Self-Balancing Trees Insertion |
Treap ( Self-Balancing Trees Insertion) |
1989 |
$O(n)$ |
$O({1})$?
|
| Self-Balancing Trees Deletion |
AVL Tree ( Self-Balancing Trees Deletion) |
1962 |
$O(logn)$ |
$O({1})$
|
| Self-Balancing Trees Deletion |
Tarjan Splay Tree ( Self-Balancing Trees Deletion) |
1985 |
$O(n)$ |
$O({1})$
|
| Self-Balancing Trees Deletion |
Bayer, McCreight B-Tree ( Self-Balancing Trees Deletion) |
1970 |
$O(b*log(n)$/log(b))? |
$O(b)$?
|
| Self-Balancing Trees Deletion |
Scapegoat Tree ( Self-Balancing Trees Deletion) |
1989 |
$O(n)$ |
$O({1})$?
|
| Self-Balancing Trees Deletion |
Treap ( Self-Balancing Trees Deletion) |
1989 |
$O(n)$ |
$O({1})$?
|
| Self-Balancing Trees Search |
AVL Tree ( Self-Balancing Trees Search) |
1962 |
$O(logn)$ |
$O({1})$
|
| Self-Balancing Trees Search |
Tarjan Splay Tree ( Self-Balancing Trees Search) |
1985 |
$O(n)$ |
$O({1})$
|
| Self-Balancing Trees Search |
Bayer, McCreight B-Tree ( Self-Balancing Trees Search) |
1970 |
$O(b*log(n)$/log(b))? |
$O({1})$
|
| Self-Balancing Trees Search |
Scapegoat Tree ( Self-Balancing Trees Search) |
1989 |
$O(nlogn)$ |
$O({1})$?
|
| Self-Balancing Trees Search |
Treap ( Self-Balancing Trees Search) |
1989 |
$O(n)$ |
$O({1})$?
|
| Self-Balancing Trees Search |
Tango Tree ( Self-Balancing Trees Search) |
2004 |
$O((k+{1})$log(log(n))) |
-
|
| 2 player games |
Lemke-Howson Algorithm (2 player games Nash Equilibria) |
1964 |
Exponential |
$O(mn)$?
|
| Graphical games, Multi-agent influence diagrams |
Blum, Shelton, Koller (Graphical games, Multi-agent influence diagrams Nash Equilibria) |
2003 |
Unknown? |
-
|
| 2 player games |
Lipton, Markakis and Mehta method (2 player games Nash Equilibria) |
2003 |
$O(n^{c log n/eps^2})$ |
$O(log^{2} n/eps^{2})$
|
| n player games |
Lipton, Markakis and Mehta method 2 (n player games Nash Equilibria) |
2003 |
$O(n^{ck^{2} log (k^{2}n)$/eps^2}) |
$O(k^{2}log^{2} n/eps^{2})$
|
| n player games |
Support enumeration and search (n player games Nash Equilibria) |
2004 |
Unknown |
-
|
| n player games |
Mixed Integer Programming (n player games Nash Equilibria) |
2005 |
Unknown |
-
|
| n player games |
Global Newton Method (n player games Nash Equilibria) |
2008 |
Unknown |
-
|
| 4NF Decomposition for Functional and Multivalued Dependency Sets |
Grahne and Räihä (4NF Decomposition for Functional and Multivalued Dependency Sets 4NF Decomposition) |
1983 |
exponential |
exponential
|
| 4NF Decomposition for Conflict-Free Dependency Sets |
Lien (4NF Decomposition for Conflict-Free Dependency Sets 4NF Decomposition) |
1982 |
$O(k^{2} n^{2})$ |
$O(k^{2})$
|
| 4NF Decomposition for Conflict-Free Dependency Sets |
Sciore (4NF Decomposition for Conflict-Free Dependency Sets 4NF Decomposition) |
1981 |
poly-time |
-
|
| 4NF Decomposition for Functional and Multivalued Dependency Sets |
Fagin (4NF Decomposition for Functional and Multivalued Dependency Sets 4NF Decomposition) |
1977 |
exponential |
exponential
|