List:Algorithms

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