Download

Create a customized dataset export by selecting specific domains, algorithm families, and their variations. Choose which algorithm properties to include in your export, such as time complexity, space complexity, and other characteristics.

Algorithms Table

Displaying 1922 of 1922 algorithms


Goodrich, Jacob	2023	$O(\log n)$ w/ high probability
Multi-Deque Partition DualDeque Merge Sorting algorithm (MPDMSort) - Ketchaya, Rattanatranurak	2023
Cao, Fineman	2023	n^{1/2+o(1)} whp
Carmon, Jambulapati, Jin, Lee, Liu, Sidford, Tian (Parallel EpochSGD)	2023
Carmon, Jambulapati, Jin, Lee, Liu, Sidford, Tian (Parallel AC-SA)	2023
Ashan, Puri, Prasad	2023	$O(\log{n})$
Ebnenasir, Qiu (recursEMS)	2023
Ebnenasir, Qiu (parEMS)	2023
Han, He	2022	$O((\log n)^(3/2)/ loglog n)$
Han, He	2022	$O((\log n)^(3/2)/ loglog n)$
Kunapuli	2022	$O(c)$
2mm - Mubarak, Iqbal, Naeem, Hussain	2022
Parallel D&C Bubble Sort - Ganapathi, Chowdhury (1)	2022	$O(n^2/p +n)$
Parallel D&C Selection Sort - Ganapathi, Chowdhury (2)	2022	$O(n^2/p +n)$
Parallel D&C Insertion Sort - Ganapathi, Chowdhury (3)	2022	$O(n^2/p +n)$
Kasani (1)	2022	$O(1)$
Kasani (2)	2022	$O(\log{\log{n}})$
Tchendji, Tepiele, Onabid, Myoupo	2022	$O((mnr + (m+n)\|\sigma\|)/p + p)$
Peretz, Fischler	2022	$O(V \log V)$	https://dl.acm.org/citation.cfm?id=290181
Bahig, Hazber, Al-Utaibi, Nassr	2022	$O(m/t)$
Zeutouo, Tchendji, Myoupo	2022	$O(n^2/sqrt(p) + k*sqrt(p))$
Primal-Dual Stochastic Mirror Descent - Tiapkin, Gasnikov	2022
Nachaoui, Chafik, Daoui	2022	$O(npS)$
Anchor-changing Regularized Natural Policy Gradient (ARNPG) framework - Zhou, Liu, Kalathil, Kumar, Tian	2022
Parallel Quick Sort Algorithm (PQSA) and Merging Subarrays from Quick Sort Algorithm (MSQSA) - Zeng	2021	$O(n/p \log(n/p))$
Parallel Quick Sort Algorithm (PQSA) and Merging Subarrays from Quick Sort Algorithm (MSQSA) - Zeng	2021	$O(n/p \log(n/p))$
Moghaddam, Moghaddam	2021	$O(n \log p)$ + $O(n \log(\log p /p))$
Karczmarz, Sankowski	2021
Bouillaguet, Zimmermann (GNFS with structured gaussian elimination as dimension/density reduction before iterative linear solver)	2021
Shi, Dhulipala, Shun	2021	$O(m \alpha^{k-2})$ (\alpha = arboricity, which is worst case \sqrt{m})
Gianinazzi, Besta, Schaffner, Hoefler	2021	$O(m \alpha^{k-2})$ (\alpha = arboricity, which is worst case \sqrt{m})
Guidi, Selvitopi, Ellis, Oliker, Yelick, Buluc (ELBA)	2021	(nlk+a^2m+cnl)/p+p
Alami, Aassem, Hafidi	2021	$O((pkRn+k)/J+RmT^2)$
Liu, Zhou, Kalathil, Kumar, Tian	2021
Goyal (1)	2020	$O(1)$
Goyal (1)	2020	$O(1)$
Goyal (2)	2020	$O(loglog m/ \log(p/n))$
Goyal (2)	2020	$O(loglog m/ \log(p/n))$
An, Oruc	2020	$O(1)$
Blelloch, Gu, Shun, Sun (1)	2020	$O(\log n \log* n)$
Blelloch, Gu, Shun, Sun (2)	2020	$O(\log n \log* n)$
Pham, Palem, Rao	2020	poly(n)	O(mn)
Koiliaris and Xu	2019	$\tilde{O}(\min(\sqrt{n'}t, t^{5/4}, \sigma))$	$O(t)$
Harvey; Hoeven	2019	$O(n \log n)$	$O(n)$ auxiliary
Tao Luo, Zaifeng Shi and Pumeng Wang	2019	$O(n^2)$
X Chen	2019	$O(V!)$	$O(wV^2)$
Jain, Chang	2019	$O(V + mE)$	$O(V)$
Rautiainen, Marschall	2019	$O(V + mE)$	$O(mV)$
Regions sort - Obeya, Kahssay, Fan, Shun	2019	$O((n/K+\log K)\log r)$
Histogram Sort with Sampling (HSS) - Harsh, Kale, Solomonik	2019	$O(k)$ supersteps
Han, Mishra, Sayed	2019	$O(\log^(1+epsilon) n)$
modified parallel merge sort - Marszalek, Capizzi	2019	n -1/3
Harvey, van der Hoeven (2019)	2019
Bubeck, Jiang, Lee, Li, Sidford	2019
Tchendji, Zeutouo	2019	$O(n^2/p + k*sqrt(p))$
Garcia	2019
Garcia	2019
Hierarchical Navigable Small World (HNSW)	2018	$O(n \log n)$	$O(M)$
Grigoryan	2018	$O(n)$	$O(n)$
Harvey; Hoeven; Lecerf	2018	$O(n \log n 2^{2 \log^*n})$	$O(n)$ auxiliary
Y Bai	2018	$O(V^2)$	$O(V^2)$
V-ALIGN	2018	$O(mVE)$	$O(mV)$
Output-Sensitive Quantum BMM	2018	O*( \min \{n^{1/3} L^{17/30}, n^{1.5} L^{1/4}\})
	2018	O(n^3 / log^2.25 n)
Chan	2018	O(n^2*(log log n)^{O(1)}/(log n)^2)
Fully Flexible Parallel Merge Sort - Marszalek, Wozniak, Polap	2018
Kim, Choi, Bae	2018	$O(n/p \log^2(n))$
Maurya, Singh	2018	$O(n/p)$ + $O(p log_3(n/p))$
Garg	2018	$O(n \log \log n)$
Harvey, van der Hoeven (2018)	2018
Schubert, Gertz	2018	$O(\log n)$	O(1) per processor
Das, Sanei-Mehri, Tirthapura	2018	$O(3^{n/3}/(M \log{n}) +P)$
Phan, Le	2018
Zhang, Zhang, Liao, Jin	2018
Spatial GAN-Based; Urs Bergmann, Nikolay Jetchev, Roland Vollgraf	2017	$O(N)$	$O(N)$
Bringman	2017	$\tilde{O}(nt^{1+\epsilon})$	$\tilde{O}(nt^{\epsilon})$
Fast Hybrid Algorithm	2017	$O(n+m+s)$	$O(m)$
Expectation conditional maximization (ECM)	2017	$O(n^2 \log n)$	$O(n+r)$
L Chang	2017	$O(V E^2 \log V)$	$O(V)$
Rautiainen and Marschall	2017	$O(V + mE)$	$O(V\sqrt{m})$
Longest distance first (LDF) page replacement algorithm	2017	$O(nk)$	$O(k)$
Freund	2017	O(n^2*(log log n)/(log n))
SPMS - Cole, Ramachandran	2017	$O(\log n loglog n)$
Siebert, Wolf	2017	$O(n/p \log n + p \log^2(n))$
Parallel modified merge sort - Marszalek	2017	2n - log n -2
Saukas-Song Selection Algorithm - Boxer	2017	$O(n/p^(1/2) \log p + n/p \log n)$
Dhulipala, Blelloch, Shun (1)	2017	$O(d_∆ \log \|V\|)$ whp
Dhulipala, Blelloch, Shun (1)	2017	$O(d_∆ \log \|V\|)$ whp
Dhulipala, Blelloch, Shun (2)	2017	$O(r_{src} + \|E\|)$ whp
Dhulipala, Blelloch, Shun (2)	2017	$O(r_{src} + \|E\|)$ whp
Yang, Huang, Feng, Pan, Zhu (GNFS with parallel sieving and MPI parallel block lanczos)	2017
Yang, Huang, Feng, Xu (GNFS with parallel sieving and parallel block wiedemann)	2017
Harvey (2017)	2017
Harvey, van der Hoeven (2017)	2017
CZ algorithm - Jiancheng, Yiqin, Yu	2017	$O(N+\log{M})$
Guo et al.	2017	$O(hn/p + np)$
Pearce	2016	$O(V+E)$	$O(V)$
Randomized LU Decomposition	2016	$O(n^3)$	$\tilde{O}(nl + ml)$
Covanov and Thomé	2016	$O(n \log n 2^{3 \log^*n})$	$O(n)$ auxiliary
Chan, Williams	2016	$O(n^{(2-1/O(d/log(n)))})$
Reduction to Chan, Williams	2016	$O(n^{(k-1/O(d/log(n)))})$
Blelloch, Gu, Shun, Sun	2016	$O(\log n \log^∗ n)$ whp
Maleki, Nguyen, Lenharth, Garzarán, Padua, Pingali	2016	$O((\|E\| + L_D)/P + (\|E\| + L_D)/D)$
Tchendji, Myoupo, Dequen (1)	2016	$O(n^2/p + sqrt(p))$
Tchendji, Myoupo, Dequen (2)	2016	$O(n^2/g * R(p, g))$
Two-dimensional partitioning with query point replication - Xiao, Biros (1)	2016	$O(mnd/p + 1/p^0.5 (m+n) + mn/p \log{n/p^0.5} + k\log{p^0.5})$ for large k $O(mnd/p + 1/p^0.5 (m+n) + mn/p + k\log{p^0.5})$ for small k
Two-dimensional partitioning with query point replication - Xiao, Biros (1)	2016	$O(mnd/p + 1/p^0.5 (m+n) + mn/p \log{n/p^0.5} + k\log{p^0.5})$ for large k $O(mnd/p + 1/p^0.5 (m+n) + mn/p + k\log{p^0.5})$ for small k
Cyclic partitioning - Xiao, Biros (2)	2016	$O(mnd/p + m + n + mn/p \log{n/p})$ for large k $O(mnd/p + m + n + mn/p)$ for small k
Cyclic partitioning - Xiao, Biros (2)	2016	$O(mnd/p + m + n + mn/p \log{n/p})$ for large k $O(mnd/p + m + n + mn/p)$ for small k
Chafik, Daoui	2016
Serang	2015	$\tilde{O}(n \max(S))$	$O(t\log t)$
Harvey; Hoeven; Lecerf	2015	$O(n \log n 2^{3 \log^*n})$	$O(n)$ auxiliary
Covanov and Thomé	2015	$O(n \log n 2^{O(\log^*n)})$	$O(n)$ auxiliary
T. Lindeberg DoG 2015	2015	$O(n \log n)$
Lee; Peng; Spielman	2015	$O(n)$	$O(n)$
Shaban; Amirreza; Mehrdad; Farajtabar	2015	$O(n^2 \log^2 n)$	$O(kd+d^3)$
Ruchansky	2015	$O(q(m \log(n)+n \log^2(n)))$	$O(q(m+n \log n))$
HybridSpades	2015	$O(m(V \log(mV) + E))$	$O(m(V+E))$
SHA-3	2015	$O(n)$	$O(b+d)$ auxiliary
Chan	2015	O(n^3 * (log log n)^3 / log^3 n)
Chan	2015	O(n^3 * (log w)^3 / (w * log^2 n))
Yu	2015	O(n^3*poly(log log n)/log^4 n)
Kmett	2015	O(m*log(h))
Exhaustive search	2015	2^(O(n))	O(n) auxiliary
Abboud, Williams, Yu	2015	$O(n^{(2-1/O(d/log(n)))})$
Reduction to Abboud, Williams, Yu	2015	$O(n^{(k-1/O(d/log(n)))})$
Axtmann, Bingmann, Sanders, Schulz	2015	$O(alpha \log p + beta n/sqrt(p) + n/p \log (n/p))$
Blelloch, Fineman, Gibbons, Gu, Shun (1 - PRAM))	2015	$O((n \log n+ kn)/p +k \log n)$
Chen	2015	$O(n \log n)$
Curtis, Sanches	2015	$O(n(m-w_{min})/p)$	O(n)
Krishnan, Baron	2015
Pérez, Saeed	2015	$O(n/p) + O(n/(lp)) +O(n/(rkp))$
Lima, Branco, Caceres	2015	$O(n^3 / p)$
Puri	2015	$O(\log n)$
Serang	2014	$\tilde{O}(n \max(S))$	$O(t\log t)$
Vassilevska Williams	2014	$O(n^{2.372873})$	$O(n^2)$
François Le Gall	2014	$O(n^{2.3728639})$	$O(n^2)$
Lowe’s Algorithm	2014	$O(V^2)$	$O(V)$ per processor
Williams	2014	$O(n^3/2^{\sqrt{\log n}})$	$O(n^2)$
Barghout; Lauren Visual Taxometric approach	2014	$O(n \log n)$
Probabilistic Convolution Tree	2014	$O(n \log n)$	$O(n \log n)$
HyperLogLog++	2014	$O(N)$	$O(\epsilon^{-2}\log(\log n))+\log n)$
Patrick Posser	2014	$O(n^3)$	$O(n)$
Multistep	2014	O(V^2+E)	O(V+E) total
Hertli (Modified PPSZ)	2014	O(1.30704^n)	O(kn)
Hertli (Modified PPSZ)	2014	O(1.46899^n)	O(kn)
Gronlund, Pettie	2014	O(n^2/((log n)/(log log n))^2/3)
Gronlund, Pettie	2014	O(n^2*(log log n)^2/(log n))
Bosakova-Ardenska, Vasilev, Kostadinova-Georgieva	2014
Bae, Shinn, Takaoka	2014	$O(n)$
Shun, Dhulipala, Blelloch	2014	O(log^3(n)
Daoud, Gad (GNFS with parallel sieving)	2014
Tembhurne, Sathe (1)	2014
Tembhurne, Sathe (2)	2014
Harvey, van der Hoeven, Lecerf (2014)	2014
Cevher, Becker, Schmidt (Consensus ADMM - first order mehtod)	2014	$O(n*n/m)$
Myoupo, Tchendji	2014	$O(n^2/p + sqrt(p))$
Puri, Prasad	2014	$O((n+k+k')\log{n+k+k'}/p)$
Wu et al.	2014
Edwards, Vishkin	2014	$O(\log^2{n})$
Takaoka	2014	$O(n^3 / p)$
Abbas, Abouelhoda, Bahig, Mohie-Eldin	2014
Projected radial search	2013	$O(n \log n)$	$O(n)$
James B Orlin's + KRT (King; Rao; Tarjan)'s algorithm	2013	$O(VE)$	$O(V + E)$
Hong’s algorithm	2013	$O(V(V+E))$	$O(V+E)$
Madry's algorithm	2013	$O(E^{10/7} \text{polylog}(V))$	$O(V + E)$
Kelner; Orecchia; Sidford; Zhu	2013	$O(m \log^2(n) \log \log n)$	$O(n)$
K Riesen	2013	$O(V^2)$	$O(V)$
Ballard (CAPS) (same as 2012 paper)	2013	$O(n^{\log 7}/P)$
Ballard (2.5D-Strassen) (1)	2013	max {n^3/(PM^{3/2−(log 7)/2}), n^{log 7}/P^{(log 7)/3} } + n^2/P^{2/3} + log P
Ballard (Strassen-2.5D) (2)	2013	(7/8)^l n^3/P
Demmel, Eliahu, Fox, Kamil, Lipshitz, Schwartz, Spillinger (CARMA)	2013	$O(mnk/p)$
Tripathy, Ray	2013	$O(m*\log(n)/p)$
Tripathy, Ray	2013	$O(m*\log(n)/p)$
Solomonik, Buluç, Demmel	2013	$O(n^3/p + n^2/\sqrt{p} + \sqrt{p}\log^2(p))$ or $O(n^3/p + n^2/\sqrt{pc} + \sqrt{pc}\log^2(p/c^3))$
Alzoabi, Alosaimi, Bedaiwi	2013	$O(n/k + m - 1)$
Chmielowiec (existing FFT-based algorithm)	2013
Xin et al.	2013	$O((n \log n)/p)$
Wang et al.	2013	$O((n/p)\log(n/p) + sqrt(np)\log(np))$
T. Lindeberg DoG 2012	2012	$O(n^2)$
Dual clustering - Guberman	2012	$O(n \log n)$
Quick-Skip Searching	2012	$O(mn)$	$O(m)$
Hybrid Algorithm	2012	$O(n^2)$
Bellare Active Learning	2012	$O(n^2 \log n c \log c)$
Chan	2012
Bansal	2012	$O(\log^2{n})$
Interval Based Rearrangement (IBR) bitonic sort - Peters, Schulz-Hildebrandt, Luttenberger	2012	$O(\log{n})$
Cache-efficient Parallel Sort - Odeh, Green, Mwassi, Shmueli, Birk	2012	$O(n/p \log n + n/c \log p \log c)$
Gerbessiotis	2012	$O(\log{n})$ expected
Gerbessiotis	2012	$O(\log{n})$ expected
Han, He (1)	2012	$O(\log^1.5{n}/ \log{\log{n}})$
Han, He (1)	2012	$O(\log^1.5{n}/ \log{\log{n}})$
Han, He (2)	2012	$O(\log^1.5{n}/ \log{\log{n}})$
Han, He (2)	2012	$O(\log^1.5{n}/ \log{\log{n}})$
Ballard, Demmel, Holtz, Lipshitz, Schwartz (CAPS)	2012	$O(n^{\log 7}/P)$
Reem	2012	$O((n^2)/p)$
Zhao et. al.	2012		https://www.proquest.com/docview/919780720?pq-origsite=gscholar&fromopenview=true
Zhao Ning, Wang XuBen	2012
Bokhari	2012	$O(nt/p)$	O(n)
Chedid	2012	$O(2^(n/2-eps))$	O(n)
Bosnacki et al.	2012	$O(n*ceil(n^2/p))$
Jump Point Search (JPS)	2011	$O(b^d)$	$O(b^d)$
OBF Algorithm	2011	$O(V(V+E))$	$O(E+V^2)$ total
Block A*	2011	$O(b^d)$	$O(b^d)$
Chandran and Hochbaum	2011	$O(\min(Vk, E)+\sqrt{k}\min(k^2, E))$	$O(E)$
Koutis; Miller and Peng	2011	$\tilde{O}(m \log n)$	$O(n)$
Segundo; Artieda; Strash Parallel	2011	$O(3^{n/3})$	$O(n^2)$
Ioannidou; Kyriaki; Mertzios; George B.; Nikolopoulos; Stavros D.	2011	$O(n^4)$	$O(n^3)$
Berger & Müller-Hannemann	2011	$O(\exp(n))$
Man, Ito, Nakano	2011	$O(n/p(\log{n/p} +\log{p}) + p^2k\log{p} + p\log{n/p})$
Siebert, Wolf	2011	$O(\log^2 (n))$
adaptive bitonic sorting - Zachmann	2011	$O(n \log{n}/p)$
Solomonik, Demmel (Classical 2.5D)	2011	$O(n^3/p)$
Solomonik, Demmel (Classical 2.5D)	2011	$O(sqrt(pc) \log(p/c) + n^2/sqrt(pc) + n^3/p)$
Xu, Wang [FDPI]	2011
Budiardja, Cardall	2011
Ozkural, Uçar, Aykanat	2011
Blelloch, Shun	2011	$O(\log^2(n))$
Locality-sensitive hashing	2010	$O(nLkt)$ [pre-processing] $O(L(kt+dnP_2^k))$ [query-time]	$O(nL)$
Lokshtanov	2010	$\tilde{O}(n^3 t)$	$O(n^2)$
Theta*	2010	$O(b^d)$	$O(b^d)$
Koutis; Miller and Peng	2010	$\tilde{O}(m \log n)$	$O(n)$
Blelloch; Koutis; Miller; Tangwongsan	2010	$O(n \log n)$	$m + O(n/\log n)$
Gao’s additive FFT	2010	$O(n \log n \log \log n)$	$O(n)$
David Eppstein, Maarten Löffler, Darren Strash	2010	$O(dn 3^{d/3})$	$O(n^2)$
S-hull (Sinclair)	2010	$O(n \log n)$	$O(n)$
String Graph with Ferragina–Manzini Index (Simpson, Durbin)	2010	$O(n)$	$O(n)$
Sun; M. Shao; J. Chen; K. Wong; and X. Wu	2010	$O(kmn)$	$O(kmn)$
Jalali; A. Montanari; and T. Weissman	2010	$O(n)$	$O(n)$
Korada and R. Urbanke;	2010	$O(n 2^n)$	$O(N)$
Multi-sort - Rakesh	2010	$O(n^(1/4))$
Parallel Sorting by Approximate Selection (PSAS) - Wu, Wu, Shang, Fang	2010	$O(n + n/p \log(n/p))$
Li, Peng, Chu	2010	$O((m2^k)^2)$ computation + $O((km2^k)^2)$ communication
Eswaran, RajaGopalan	2010	$O(\|LCS(X,Y)\|)$
Krusche, Tiskin	2010	$O(n^2/p)$
Hong, He	2010
Blelloch, Maggs [Parallel MergeHull]	2010	$O(\log n)$
Yang, Xu, Yeo, Hussain (GNFS with parallel sieving and montgomery block lanczos)	2010
De Stefani (COPSIM)	2010
De Stefani (COPK - Karatsuba)	2010
Mesa, Feregrino-Uribe, Cumplido, Hern´andez-Palancar	2010
Sorenson	2010	$O((n \log \log n)/(\log n))$
Time-Bounded A* (TBA*)	2009	$O(b^d)$	$O(b^d)$
Harrow (Quantum)	2009	$O(k^2 \log n)$	$O(\log n)$
Renault’s Algorithm	2009	$O(p(V+E) \alpha(V, E))$	$O(V)$ per processor
Filter Kruskal algorithm	2009	$O(E \log V)$	$O(E)$
Chan (Geometrically Weighted)	2009	$O(n^{2.844})$	$O(l n^2)$
Chan	2009	$O(n^3 \log^3 \log n / \log^2 n)$	$O(n^2)$
Chan	2009	$O(n^3 \log^3 \log n / \log^2 n)$	$O(n^2)$
Gupta; Verdu	2009	$O(n^3 \log n)$	$O(n)$
Gupta & Sarawagi CRF	2009	$O(n^3 k)$	$O(nk)$
Bansal, Williams	2009	O(n^3 * (log log n)^2 / log^2.25 n)
Bansal, Williams	2009	O(n^3 * (log log n)^2 / (w * (log n)^7/6))
Chan	2009
Mongelli et. al.	2009
Li, Peng, Chu	2009	$O(2^k + m)$ ^2 computational + $O(2^k m(2k+1) +k)$ ^2 communication
Dynamic Communication-Efficient parallel Sorting (DCES) - Thanakulwarapas, Werapun	2009	$O(n/p \log (n/p) + n/p \log p)$
Parallel Vertex Enumeration	2009
Dong, Wu, Zhou [22-merger]	2009	$O(n*(1 + (\log n)/p))$
Bennett et. al	2009	$O(n/p + p)$	O(1) per processor
parallel policy iteration - Zhang, Sun, Xu (1)	2009	$O((S^3+ AS^2)/p)$ computation, $O(pS^2)$ communication
parallel value iteration - Zhang, Sun, Xu (2)	2009	$O((AS^2)/p)$ computation, $O(pS)$ communication
Valentin Polishchuk, and Jukka Suomela	2008	$O(\Delta^2/\epsilon)$	$O(\Delta^2/\epsilon)$
Fringe Saving A* (FSA*)	2008	$O(b^d)$	$O(b^d)$
Generalized Adaptive A* (GAA*)	2008	$O(b^d)$	$O(b^d)$
De	2008	$O(n \log n 2^{O(\log^*n)})$	$O(n)$ auxiliary
Trujillo and Olague 2008	2008	$O(n^2)$
Geert Willems; Tinne Tuytelaars and Luc van Gool (2008)	2008	$O(n^2)$
Spatio-temporal Geert Willems; Tinne Tuytelaars and Luc van Gool (2008)	2008	$O(n^2)$
view frustum culling	2008	$O(n^2)$
HEALPix mapping Wong	2008	$O(n^2)$
Almeida & Zeitoun	2008	$O(n)$	$O(n)$
de Berg; Cheong	2008	$O(n \log n)$	$O(n)$
Jalali and T. Weissman	2008	$O(n)$	$O(n)$
B.I. Kvasov	2008	$O(n^3 \log^2 K)$	$O(n)$
YANG Y.; KIM J.; LUO F.; HU S.; GU X. 2008	2008	$O(n \log \log n)$
BEN-CHEN M.; GOTSMAN C.; BUNIN G. 2008	2008	$O(n \log^2 n)$
SPRINGBORN B.; SCHROEDER P.; PINKALL U. 2008	2008	$O(n \log^2 n)$
Hanoi graph	2008	$O(3^n)$	$O(3^n)$
Wei, Xiao, Zhang	2008	sqrt(2n) + $O(n^(3/4))$
Hongwei, Yafeng	2008	log^2(n) + log n
Liu, Chen	2008	$O(\|LCS(X,Y)\|)$
Wang, Korkin, Shang	2008	$O(1/p(1+p/(\|\Sigma\| \log^{d-2}{n}))(n \|\Sigma\| d + \|D\| \|\Sigma\| d (\log^{d-2}{n} + \log^{d-2}{\|\Sigma\|}) + 4d\|D\|)$
Hunold, Rauber, Rünger	2008	$O(n^3/p)$
Schudy	2008	$O(τ \log^2 n)$
Schudy	2008	$O(τ \log^2 n)$
Kechid, Myoupo	2008	$O(n^2/p + p)$
Parallel Support Enumeration	2008	$O(n^3*4^n/p)$
Connor, Kumar	2008
Connor, Kumar	2008
Schudy	2008	$O(t poly(\log n))$
Chedid	2008	$O(2^(3n/8))$	O(n)
Li, Li, Li	2008	$O(2^(n(1+eps)/4))$	O(n)
Sanches, Soma, Yanasse [Algorithm 1]	2008	$O(n/p * (c - w_min) + (c + w_max - w_min)/p + n + \log p)$	O(n)
Sanches, Soma, Yanasse [Algorithm 2a]	2008	$O(n/p * (c - 2*w_min) + c/p + n)$	O(n)
Sanches, Soma, Yanasse [Algorithm 3]	2008	$O((n-2 \log c)(c - 2*w_min)/p + c/p + n - 2 \log c + \log^2 c)$	O(n)
Craus, Archip	2008
Bidirectional A* Algorithm	2007	$O(b^{(d/2)})$	$O(b^{d/2})$
PMS	2007	$O(nm^2 \sigma)$	$O(m^2 n)$
Fomin; Gaspers & Saurabh	2007	$O(1.7272^n)$	$O(n)$
Shanks's square forms factorization (SQUFOF)	2007	$O(2^{n/4})$	$O(n)$
Press, Teukolsky, Flannery	2007	$O(n^3)$	$\tilde{O}(n)$
Furer's algorithm	2007	$O(n \log n 2^{O(\log^*n)})$	$O(n)$ auxiliary
Daitch; Spielman	2007	$O(n^{5/4} (\log^2(n) \log\log n)^{3/4} \log(1/\epsilon))$	$O(n)$
HyperLogLog algorithm	2007	$O(N)$	$O(\epsilon^{-2}\log(\log n))+\log n)$
ZAYER R.; LÉVY B.; SEIDEL H.-P. 2007	2007	$O(n)$
CHEN Z. G.; LIU L. G.; ZHANG Z. Y.; WANG G. J. 2007	2007	$O(n^2)$
Clock-sampling mutual network synchronization	2007	$O(n)$	$O(1)$ (per node)
Cheng, Shah, Gilbert, Edelman	2007	O(n log n /p + gn/p +log n max(L,gp^2 log(n))
partition and concurrent merging (PCM) - Herruzo, Ruiz, Benavides, Plata	2007	$O(n/p \log (n/p))$ + $O(n)$
Damrudi, Aval	2007	$O(sqrt(n/4))$
partition and concurrent merging (PCM) - Herruzo, Ruiz, Benavides, Plata	2007	$O((n/p)\log{n/p})+O(n)$
Furer	2007
Sun, Lu, Li, Wang	2007	$O(kn^2/p)$
Sanches, Soma, Yanasse	2007	$O(2^(n/2)/p)$	O(n)
Bae	2007	$O(n)$
Quick Kruskal algorithm	2006	$O(E \log V)$	$O(E)$
Risotto	2006	$O(mn^2 \sigma)$	$O(mn^2)$
Alon; Moshkovitz & Safra	2006	$O(n \log n)$
Field D*	2006	$O(b^d)$	$O(b^d)$
Applegate et al. (Concorde TSP Solver)	2006	$O(V^2 2^V)$
FAST E. Rosten and T. Drummond 2006	2006	$O(n^3)$
SURF Descriptor 2006	2006	$O(n^2)$
Isometric graph partitioning - Leo Grady and Eric L. Schwartz (2006)	2006	$O(n^2)$
Bader & Cong Parallel Implementation	2006	$O(E \log(V)/p)$	$O(V)$
Elliptic-curve Diffie-Hellman (ECDH)	2006	$O(n^2\text{mult}(n))$	$O(n)$
Neuhaus, Riesen, Bunke	2006	$O(V^2)$	$O(wV)$
Tomita; Tanaka & Takahashi	2006	$O(3^{n/3})$	$O(n^2)$
Belloch	2006	$O(n \log n)$	$O(n)$
Chen; I. Kanj; and W. Jia.	2006	$O(1.2738^k+ kn)$	$O(\text{poly}(n))$
Miyake 2006	2006	$O(n 2^n)$	$O(2^n)$
Martinian and M. J. Wainwright	2006	$O(n 2^n)$	$O(mn+mk)$
V. I. Paasonen	2006	$O(n^5 \log K)$
YAN J. Q.; YANG X.; SHI P. F 2006	2006	$O(n^2)$
Kingsford	2006	$O(mn)$	$O(m^2n^2)$
Chubby (Mike Burrows)	2006	$O(n)$	$O(f)$
Sthele, Zimmermann	2006	$O(n \log^2 n \log \log n)$	$O(n)$
Fischer, Heun	2006	O(m+n)	O(n)
Fischer, Heun	2006
Chen, Wan, Liu	2006	$O(\|LCS(X,Y)\|)$
Krusche, Tiskin (dynamic programming)	2006	$O(n^2/p · ( f + g/b + l/b^2))$
Krusche, Tiskin (dynamic programming)	2006	$O(n^2/p · ( f + g/b + l/b^2))$
Liu, Chen, Chen, Qin	2006	$O(\|LCS(X,Y)\|)$
Bader & Cong Parallel Implementation	2006	$O(E \\log(V)/p)$	O(V) total
Bader & Cong Parallel Implementation	2006	$O(E \\log(V)/p)$	O(V) total
Yang, Xu, Lin, Quinn (GNFS with parallel sieving and serial biorthogonal block lanczos)	2006
Fayyazi, Kaeli, Meleis	2006		O(1)
Belloch, Gu, Shun, Sun	2006	$O(\log^2 n)$	O(n)
Ye, Chiang	2006
Anytime Repairing A* (ARA*)	2005	$O(b^d)$	$O(b^d)$
Fringe	2005	$O(b^d)$	$O(b^d)$
Lindeberg 2005	2005	$O(n^2)$
Quasi-linear Topological watershed	2005	$O(n \log n)$
Poupart; 2005;	2005
Smith & Simmons; 2005;	2005
Spaan & Vlassis; 2005	2005
Paquet; Tobin; & Chaib-draa; 2005;	2005
Shani; Brafman; & Shimony; 2005	2005
Mauro Steigleder	2005	-
Maneva and M. J. Wainwright	2005	$O(n^2)$	$O(n^2)$
Ciliberti; Mézard	2005	$O(n^2)$	$O(n^2)$
Manlove; Malley	2005	$O(n^2)$	$O(n^2)$
Unsworth; C.; Prosser; P	2005	$O(n^2)$	$O(n^2)$
KARNI Z.; GOTSMAN C.; GORTLER S. J. 2005	2005	$O(n^2)$
SHEFFER A.; LÉVY B.; MOGILNITSKY M.; BOGOMYAKOV A. 2005	2005	$O(n^2)$
ZAYER R.; ROESSL C.; SEIDEL H.-P 2005	2005	$O(n \log n)$
ASP	2005	$O(n)$	$O(n)$ (per node)
Paturi, Pudlák, Saks, Zane (PPSZ) 2005	2005	$O^*(2^{n-cn/k})$	O(kn)
Anytime Dynamic A* (ADA*)	2005	O(b^d)	O(b^d)
D* Lite	2005	O(b^d)	O(b^d)
Focused D*	2005	O(b^d)	O(b^d)
Chen, Levcopoulos	2005	$O(\log n)$
Arefin, Hasan	2005	$O(n/p \log^2{n})$
Tiskin	2005	$O(mn/p)$ computation + $O(n \log p)$ communication + $O(\log p)$ barrier synchronization + $O(n)$ memory per processor
Yang, Xu, Lin (GNFS with parallel sieving and serial block lanczos)	2005
Cui-xiang, Guo-qiang, Ming-he	2005	$O((n/p) \log n)$
Nivasch	2004	$O(\mu + \lambda)$	$O(\log\mu)$
Burst Sort	2004	$O(wn)$	$O(wn)$
Byskov	2004	$O(1.7504^n)$	$O(n^2)$
CH Algorithm	2004	$O(VE)$	$O(V+E)$
Thorup's algorithm	2004	$O(E + V \min(\log \log V, \log \log L))$	$O(V)$ ("linear-space queue")
Taubenfeld's black-white bakery algorithm	2004	$O(n)$	$O(1)$ per process, $O(n)$ total
K. Mikolajczyk; K. and C. Schmid LoG 2004	2004	$O(n^2)$
Lowe (2004)	2004	$O(n^2)$
SIFT Algorithm Lowe 2004	2004	$O(n^3)$
Hessian-Laplace Mikolajczyk and Schmid 2004	2004	$O(n^3)$
R. Nock and F. Nielsen Statistical Region Merging	2004	$O(n^2)$
Braziunas & Boutilier; 2004;	2004
Maximum a Posteriori Occupancy Mapping	2004	$O(n^3)$
Mucha, Sankowski (general)	2004	$O(V^{\omega})$	$O(V^2)$
Spielman, Teng	2004	$O(m \log^c n)$	$O(n)$
Boman; Chen; Hendrickson; Toledo	2004	$O(n\log(1/\epsilon))$	$O(n)$
Stephen Alstrup, Cyril Gavoille, Haim Kaplan & Theis Rauhe	2004	$O(n+m)$	$O(n)$
Kazuhisa Makino, Takeaki Uno; Section 5	2004	$O(n^{\omega})$ per clique	$O(n^2)$
Chandran and F. Grandoni	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
Rytter	2004	$O(\log n)$	$O(n)$
Ravikumar & Cohen Generative Models	2004	$O(n^2 k)$	$O(k)$
YOSHIZAWA S.; BELYAEV A. G.; SEIDEL H.-P 2004	2004	$O(n^2)$
MATSF	2004	$O(n)$	$O(n)$ (per node)
Geldenhuys-Valmari	2004	O(V+E)	O(V)
Kazuhisa Makino, Takeaki Uno; Section 6	2004	O(delta^4)	O(n+m) auxiliary()
Tango Tree	2004	O(nlogn)	O(n)
Tango Tree	2004	O((k+1)log(log(n)))
Takaoka	2004
Parallel Sorting by Exact Splitting (PSES) - Dian, Zhizhong	2004	$O(n/p \log{n/p} + p^2 \log{p}\log{n/2p} + n/p \log{p})$
Krishnan, Nieplocha (SRUMMA)	2004	$O(n^3/p)$
Takaoka	2004	$O(\log \log n)$
Alves, Caceres, Song (1)	2004	$O(n / p)$
Alves, Caceres, Song (2)	2004	$O(n^3 / p)$
Rytter	2004	$O(\\log n)$	O(n)
Pisinger	2003	$O(nt/\log t)$	$O(t/\log t)$
Census	2003	$O(k nm \sigma)$	$O(mnk)$
Fleischer forward-backward (FB) algorithm	2003	$O(E\log V+V)$	$O(V+E)$
Kwatra 2003	2003	$O(n^3)$
Pineau; Gordon; & Thrun; 2003;	2003
Emil Praun	2003	$O(n^3)$
FastSlam	2003	$O(m \log n)$ per iteration	$O(mn)$
Lipton; Mehta	2003	$O(n^{O(\log n/\epsilon^2)}$	$O(\log^2(n)/\epsilon^2)$
α-EM algorithm	2003	$O(n^3)$	$O(n+r)$
LogLog algorithm	2003	$O(N)$	$O(\log \log n)$
Matsunaga; Yamamoto	2003	$O(n 2^n)$	$\exp(n)$
Adaptive Duplicate Detection Algorithm (ADD)	2003	$O(n^3)$	$O(1)$
V. A. Lyul’ka and I. E. Mikhailov	2003	$O(n^4)$
FLOATER 2003	2003	$O(n^2)$
α-EM Algorithm	2003	$O(n^3)$	$O(n+r)$
Jeh and Widom	2003	$O(mn)$	$O(nh)$
Tomlin	2003	$O(mn)$	$O(n)$
load balanced parallel merge sort - Jeon, Kim	2003	k_1 n/p log p + k_2 (n/p + delta) log p
Alves, Cáceres, Song	2003	$O(mn/p + \log p)$
Alves, Cáceres, Song	2003	$O(mn/p + \log p)$
Gupta, Sen	2003	$O((\log \log n)^2 \log h)$
Bunimov, Schimmler	2003
Caceres, Nasu	2003	$O((E \log p)/p)$	O(1)
Li, Pan, Shen	2003	$O(\log n)$
Kohout, Kolingerova	2003
Cheetham et. al.	2003	$O(((1.325)^k k^2 + kn)/p)$
Veloso, Meira, Parthasarathy	2003
Chung, Luo	2003
Mitra	2002	$O(k nm \sigma)$	$O(mnk)$
Compressed Extended KF	2002	$O(n^3)$	$O(n^2)$
Tim Sort	2002	$O(n \log n)$	$O(n)$
Thorup's Sorting Algorithm	2002	$O(n \log \log n)$	$O(n)$
Bead Sort	2002	$O(n)$	$O(n^2)$
Spreadsort	2002	$O(n \log n)$	$O(n)$
Pettie & Ramachandran	2002	$O(mn \log \alpha(m,n))$
Pettie & Ramachandran	2002	$O(mn \log \alpha(m,n))$
A. Chalmers; T. Davis; and E. Reinhard 2002	2002	$O(n^2)$
Maximally stable extremal regions Matas 2002	2002	$O(n^2 \log^3 n)$
Multi-scale MAP estimation - A. Bouman and M. Shapiro (2002)	2002	$O(n^2)$
srba	2002	$O(n^2)$	$O(n^2)$
Faugère F5 algorithm	2002	$O(\binom{n+D_{reg}}{D_{reg}}^{\omega})$	$O(\binom{n+D_{reg}}{D_{reg}}^2)$
Ananthakrishna	2002	$O(n^2 k)$	$O(n)$
Duplicate Elimination Sorted Neighborhood Method (DE-SNM)	2002	$O(n \log n)$	$O(n)$
LEE Y.; KIM H. S.; LEE S 2002	2002	$O(n \log^3 n)$
DESBRUN M.; MEYER M.; ALLIEZ P. 2002	2002	$O(n^2)$
LÉVY B.; PETITJEAN S.; RAY N.; MAILLOT J 2002	2002	$O(n \log^{2.5} n)$
Haveliwala	2002	$O(mn)$	$O(nz)$
Richardson and Domingos	2002	$O(mn)$	$O(nl)$
Pettie, Ramachandran	2002	unknown but optimal	O(E) auxiliary
Cerin	2002
Han, Shen	2002	$O(\log n)$
Han, Shen	2002	$O(\log n)$
Canturk	2002	$O(n/p \log(np)+tau+sigma n/p)$
AHRABIAN, NOWZARI-DALINI (1)	2002	$O(n^2 \log n)$
AHRABIAN, NOWZARI-DALINI (1)	2002	$O(n^2 \log n)$
AHRABIAN, NOWZARI-DALINI (2)	2002	$O(n^3*\log(p)/p)$
AHRABIAN, NOWZARI-DALINI (2)	2002	$O(n^3*\log(p)/p)$
Gavrilova	2002	$O(\log{n} \log)$
Tewari, Srivastava, Gupta	2002	$O(kn \log n)$
Chen, Chuang, Wu	2002
MotifSampler	2001	$O(nm)$	$O(n + m)$
Lifelong Planning A* (LPA*)	2001	$O(b^d)$	$O(b^d)$
image analogies Hertzmann	2001	$O(N \log n)$
Image quilting Efros-Freeman	2001	$O(n^3)$
Rao-Blackwellized Particle Filtering SLAM	2001	$O(n^2)$	$O(n)$
CNN Based Gatys; Leon A 2001	2001	$O(n^3)$
H.W.Jensen 2001	2001	$O(k^3 n)$
Linda G. Shapiro and George C. Stockman (2001)	2001	$O(n^2)$
Boman; Hendrickson	2001	$\tilde{O}(mn^{1/2})$
Extended Split Radix FFT algorithm	2001	$O(n \log n)$	$O(n)$
Chen; I. Kanj; and W. Jia.	2001	$O(kn + 1.2852^k)$	$O(k^3)$ auxiliary (potentially $O(k^2)$ )
Gent; I.P.; Irving; R.W.; Manlove; D.F.; Prosser; P.; Smith; B.M.	2001	$O(n^2)$	$O(n^2)$
SANDER P. V.; SNYDER J.; GORTER S. J.; HOPPE 2001	2001	$O(n^2)$
Vazirani (ILP, chapters 13-15)	2001	$O(\text{poly}(n, d))$	$O(U)$
Vazirani (ILP, chapters 13-15)	2001	$O(\text{poly}(n, d))$	$O(U)$
Randomized HITS	2001	$O(mn \log n)$	$O(n)$
Achlioptas	2001	$O(mn)$	$O((n+l)^2)$
SHA-2	2001	$O(n)$	$O(1)$
Rijndael / AES	2001	$O(n)$	$O(n)$
Quantum Adiabatic Algorithm (QAA)	2001	O(2^n)	O(poly(n))
Kose, Weckwerth, Linke, Fiehn	2001
Han	2001	$O(\log^2(n))$	O(n)
Han	2001	$O(\log^2(n))$	O(n)
Gerbessiotis, Siniolakis	2001	$(1+2/\omeg_n) n \log{n}/p + O(n/p(\delta \log{\log{n}} +m^2 +\log{n}/ \log{n/p} + \log{n/p}/ \log^0.5{n}) + \log{n}\log{p}/ \log{n/p} + L\log{n} + L\log{n}\log{p}/ \log{n/p})$ computation $O(L\log{n}\log{p}/\log{n/p} + L\log{n} + g n/p \log{n}/ \log{n/p} + g\log{n}\log{p}/ \log{n/p} + g\log{n} + n/p mg)$ communication if $l=r$ $(1-1/2^m)(1+2/\omega_n)n\log{n}/p + O(n/p \log^4{\log{n}} + n/p \log{n}/\log{n/p} + \log{n}\log{p}/\log{n/p} + L\log{n} + L\log{n}\log{p}/\log{n/p})$ computation $O(gn/p \log^4{\log{n}} + L\log{n}\log{p}/\log{n/p} +L\log{n} + gn/p \log{n}/\log{n/p} + g\log{n}\log{p}/\log{n/p} + g\log{n})$ communication if $l=/r$ and $N<=\log^{\log{\log{n}}}{n}$
Pettie, Ramachandran	2001	$O(m/p + \log^2(n) \log*(n))$
Chong, Han, Igarashi, Lam (1)	2001	$O(\log n)$
Chong, Han, Igarashi, Lam (1)	2001	$O(\log n)$
Chong, Han, Igarashi, Lam (2)	2001	$O(\log n)$
Chong, Han, Igarashi, Lam (2)	2001	$O(\log n)$
Chong, Han, Igarashi, Lam (3)	2001	$O(\log n)$
Chong, Han, Lam	2001	$O(\log n)$
Chong, Han, Lam	2001	$O(\log n)$
Pettie, Ramachandran	2001	$O(m/p + \log^2(n) \log*(n))$
Pettie, Ramachandran	2001	$O(m/p + \log^2(n) \log*(n))$
Tiskin	2001	$O(n^3/p + g(n^2/p^{2/3}) + l \log p)$
Giraud, Guivarch, Stein	2001	$O((n^3 \log n)/p)$
Bailey, Broadhurst	2001	$O(n^2)$ *number of iterations
Sedjelmaci	2001	$O(n/\log n)$
tree-structured vector quantization Wei-Levoy	2000	$O(n^2 \log n)$	$O(nd)$
UKF	2000	$O(n^3)$	$O(n^2)$
Beigel & Eppstein	2000	$O(1.3289^n)$	$O(n^2)$
Path-based depth-first search Gabow	2000	$O(V+E)$	$O(V+E)$ total, $O(V)$ auxiliary
Chazelle's algorithm	2000	$O(E \alpha(E, V))$	$O(E)$
Thorup (reverse-delete)	2000	$O(E \log V (\log \log V)^3)$	$O(E)$
A. Baumberg. 2000	2000	$O(n^3)$
Y. Dufournaud; C. Schmid; and R. Horaud 2000	2000	$O(n^2 \log \log n)$
T. Tuytelaars and L. Van Gool 2000	2000	$O(n^3)$
Florack and Kuijper	2000	$O(n^2)$
Hauskrecht; 2000;	2000
Fleury's algorithm + Thorup	2000	$O(E \log^3(E) \log\log E)$	$O(E)$
Bender; Colton [LCA <=> RMQ]	2000	$O(n+m)$	$O(n)$
J. Chen; L. Liu; and W. Jia.	2000	$O(k 1.2192^k)$	$O(k^3)$ auxiliary (potentially $O(k^2)$ )
EM Based Winkler	2000	$O(n^3 k)$	$O(k)$
B. I. Kvasov	2000	$O(n^4)$	$O(n)$
SHEFFER A.; DE STURLER E. 2000	2000	$O(n^2)$
The (Stochastic Approach for Link Structure Analysis) SALSA Algorithm	2000	$O(m^2 n)$	$O(n)$
PHITS Coheng Chan	2000	$O(mn)$	$O(nz)$
Navarro	2000	$O(n(V + E))$	$O(V)$
Stege, Fellows + Interleaving method (Niedermeier, Rossmanith)	2000	O(kn+(1.2906)^k)	O(k^3) auxiliary (potentially O(k^2))
partitioned parallel radix (PPR) sort - Lee, Jeon, Sohn, Kim	2000	ceilling(b/g) rounds
Sinkha, Mukherjee	2000	$O((t^2-3t+2)n)$
Halperin, Zwick	2000	$O(\log n)$
Halperin, Zwick	2000	$O(\log n)$
Åsbrink, Brynielsson (quadratic sieve with only parallel sieving)	2000
Pferschy	1999	$O(n' t)$	$O(t)$
Klinz	1999	$O(\sigma^{3/2})$	$O(t)$
Psinger	1999	$O(n \max(S))$	$O(t)$
non-parametric sampling Efros and Leung	1999	$O(n^3)$
Boissonnat; Snoeyink	1999	$O(n \log n + k)$	$O(n)$
Couvreur	1999	$O(V+E)$	$O(V)$
Thorup	1999	$O(mn)$	$O(m)$
Thorup	1999	$O(mn)$	$O(m)$
local scale-invariant Lowe 1999	1999	$O(n^3)$
McAllester & Singh; 1999;	1999
Bertsekas & Castanon; 1999;	1999
Schöning	1999	$O(1.333^n)$
BOM (Backward Oracle Matching)	1999	$O(mn)$	$O(m)$
Faugère F4 algorithm	1999	$O(\binom{n+D_{reg}}{D_{reg}}^{\omega})$	$O(\binom{n+D_{reg}}{D_{reg}}^2)$
MRRR algorithm	1999	$O(n)$	$O(n^2)$
MRRR algorithm	1999	$O(n)$	$O(n^2)$
Linear Scan, Poletto & Sarkar	1999	$O(n)$	$O(r)$
Flipping algorithm	1999	$O(n^2)$	$O(n)$
Niedermeier, Rossmanith	1999	$O(kn + 1.29175^k k^2)$	$O(k^3)$ auxiliary (potentially $O(k^2)$ )
The Multistage Algorithm	1999	$O(n^2)$	$O(n^2)$
The Multihash Algorithm	1999	$O(n^2)$	$O(n^2)$
BST Algorithm	1999	$O(n \log n)$	$O(\log n)$
P. Costantini, B. I. Kvasov, and C. Manni	1999	$O(n^5 \log K)$	$O(n)$
HORMANN K.; GREINER G 1999	1999	$O(n^2)$
Ocone	1999	$O(n^2)$
Tompa M	1999	$O(mn)$	$O(m^2)$
Function Field Sieve (FFS)	1999	$O(\exp((1+o(1))(32n/9)^{1/3}(\log n)^{2/3}))$ , under assumption about numbers in a sequence behaving randomly in a given range	$O(n^{2/3})$
bcrypt	1999	$O(n)$	$O(1)$ auxiliary
Conflict-Driven Clause Learning (CDCL)	1999	O(2^n)
Stege, Fellows	1999	O(kn+max((1.25542)^k k^2, (1.2906)^k k)	O(k^3) auxiliary (potentially O(k^2))
ZZ-sort - Zheng, Calidas, Zhang	1999	O(n/p log p (f(p)+log(n/p))
Zhang, Zheng	1999	$O(n/p \log p)$
Vollmer	1999	$O(V^2 \log(V))$	can be derived
Frigo, Leiserson, Prokop, Ramachandran	1999	$O(mnk/p)$
Chong, Han, Lam	1999	$O(\log n)$
Chong, Han, Lam	1999	$O(\log n)$
PETTIE, RAMACHANDRAN (1)	1999	$O(\log n)$
PETTIE, RAMACHANDRAN (1)	1999	$O(\log n)$
Pettie, Ramachandran (2)	1999	$O(\log n)$
Pettie, Ramachandran (2)	1999	$O(\log n)$
Shi, Spencer (1) (t=log(n))	1999	$O(t \log n)$
Shi, Spencer (1) (t=sqrt(n))	1999	$O(t \log n)$
Shi, Spencer (2) (t=log(n))	1999	$O(t \log n)$
Shi, Spencer (2) (t=n)	1999	$O(t \log n)$
Ferragina, Luccio	1999	$O((n \log^2 n)/p)$ + $O((gn \log^2 n)/(p \log(n/p)))$ + $O((km/p)+k)$ + $O(kg+(km/p)g)$
Park, Ryu	1999	$O(\log V)$	O(1)
Chu, George	1999	$O((n/p) \log n)$
Belloch et al.	1999	$O(\log^3 n)$
Blelloch, Miller, Hardwick, Talmor	1999	$O(\log^3 n)$
Qiu, Akl	1999	$O(\log n)$
Speller (Sagot)	1998	$O(mn^2 \sigma)$	$O(mn^2/w)$
Roth AlignACE	1998	$O(nm)$	$O(n + m)$
R. Paget ; I.D. Longstaff	1998	$O(n^3)$
EKF SLAM	1998	$O(n^3)$	$O(n^2)$
Flash Sort	1998	$O(n^2)$	$O(n)$
J.-C. Nebel 1998	1998	$O(n^2)$
Lindeberg (1998)	1998	$O(n^2)$
The Trajkovic and Hedley corner detector 1998	1998	$O(n^2 \log^2 n)$
Hessain Determinant Lindeberg 1998	1998	$O(n^3)$
Heidrich; W.; and H.-P. Seidel	1998	$O(n^3)$
Hirsch	1998	$O(1.239^n)$
Backward Non-Deterministic DAWG Matching (BNDM)	1998	$O(n+m)$	$O(sm)$
Greiner–Hormann clipping algorithm	1998	$O(n^2)$	$O(n^2)$
Parameter-expanded expectation maximization (PX-EM) algorithm	1998	$O(n^3)$	$O(n+r)$
Kong and Wilken Algorithm	1998	$O(n^3)$	Probably dependent on the choice of ILP solver
Finch	1998	$O(V^2 E)$	$O(V^2)$
Downey	1998	$O(kn + 1.31951^k k^2)$	$O(k^3)$ auxiliary (potentially $O(k^2)$ )
Sorted Neighborhood Algorithm (SNA)	1998	$O(n \log n)$	$O(n)$
Parameter-expanded expectation maximization (PX-EM)	1998	$O(n^3)$	$O(n+r)$
Damiano Brigo; Bernard Hanzon and François LeGland	1998	$O(n^{2.45} \log n)$
Del Moral; Pierre	1998	$O(n^2)$
The PAGERANK Algorithm	1998	$O(n^3)$	$O(n)$
The (Hyperlink-Induced Topic Search) HITS Algorithm	1998	$O(n^2 k)$	$O(n)$
Signature Sort	1998	O(n log log n)	O(n)
variation of sample sort - Helman, Bader, JaJa	1998	$O(n/p \log(n))$ "with high probability"
Load Balanced Parallel Radix Sort - Sohn, Kodama	1998
Bradford, Rawlins, Shannon (1)	1998	$O(\log^3 n)$	$O(n)$
Bradford, Rawlins, Shannon (2)	1998	$O(\log^2 n \log \log n)$	$O(n)$
Bradford, Rawlins, Shannon (3)	1998	$O(\log^2 n)$	$O(n)$
Dehne, Gotz	1998	$O(\log p)$
Adler, Dittrich, Juurlink, Kutylowski, Rieping (1)	1998	$O(\log p)$
Adler, Dittrich, Juurlink, Kutylowski, Rieping (2)	1998	$O(1)$
Adler, Dittrich, Juurlink, Kutylowski, Rieping (3)	1998	$O(\log^2(p)/\log((m+n)/p))$
Adler, Dittrich, Juurlink, Kutylowski, Rieping (3)	1998	$O(\log^2(p)/\log((m+n)/p))$
Takaoka	1998	$O(\log^2(n))$
Czumaj et al. (1)	1998	$O(\log \log n)$
Czumaj et al. (2)	1998	$O(\log n)$
Edelman, McCorquodale, Toledo [Algorithm 1]	1998	$O((n/p) \log n)$
Edelman, McCorquodale, Toledo [Algorithm 2]	1998	$O((n/p) \log n)$
Diallol, Ferreira, Rau-Chaplin	1998	$O((n \log n \log p)/p)$
Cesati, Ianni	1998	$4 log n + O(k^k)$
Cheung, Hu, Xia	1998
Simpson, Sabharwal	1998	$O(n+nL^2/p)$
Eppstein	1997	$\tilde{O}(n \max(S))$	$O(t\log t)$
Intro Sort	1997	$O(n \log n)$	$O(\log n)$
Okunev; Johnson	1997	$O(n^3)$	$O(1)$
Zhao-Saalfeld	1997	$O(n)$	$O(n)$
Karger, Blum	1997	$O(\text{poly}(n))$
The SUSAN corner detector	1997	$O(n^3)$
Goldberg & Rao	1997	$O(E^{1.5} \log(V^2/E) \log U)$	$O(V + E)$
Goldberg & Rao	1997	$O(V^{0.66}E \log(V^2/E) \log U)$	$O(V + E)$
Jean-Daniel Boissonnat and Franco P. Preparata.	1997	$O((n+k) \log n)$	$O(n)$
Raymond's algorithm	1997	$O(\log n)$ (originally this had $O(n)$ )	$O(1)$ per process, $O(n)$ total
T. Lindeberg and J. Garding (1997)	1997	$O(n^2)$
topological watershed	1997	$O(n^2)$
Vertex clustering - Low; K. L. and Tan; T. S 1997	1997
Vertex clustering - Rossignac; J. and Borrel; P. 1997	1997
Washington; 1997;	1997
Heejo Lee; Jong Kim; Sungje Hong; and Sunggu Lee	1997	$O(n^2)$	$O(n^2)$
Alon and Kahale	1997	$O(\text{poly}(n))$
Gapped BLAST	1997	$O(mn)$	$O(mn)$
Klein (section 5)	1997	$O(V^{4/3} \log V)$	$O(V^{4/3})$
Hariharan	1997	$O(\log^4 n)$	$O(n)$
Farach	1997	$O(\log n)$	$O(n)$
Gusfield	1997	$O(n)$	$O(n)$
FLOATER 1997	1997	$O(n^2)$
EM with Quasi-Newton Methods (Jamshidian; Mortaza; Jennrich; Robert I.)	1997	$O(n^2 \log^3 n)$	$O(n+r^2)$
The INDEGREE Algorithm	1997	$O(mn)$	$O(n)$
Amir et al.	1997	$O(m(n \log m + E))$	$O(mn)$
Goldberg & Rao (Parallel)	1997	O(V^1.66 log(V) log(U))	O(V^2)
Goldberg & Rao (Parallel)	1997	O(E^0.5 V log(V) log(U))	O(V^2)
Galil, Margalit	1997
Eppstein	1997	$O(qt log t log n)$	O(nt)
Shear-sort - De et al.	1997	$O(n^(1/4))$
Albers, Hagerup (1)	1997	$O(t)$ t>=log n loglog n
Albers, Hagerup (1)	1997	$O(t)$ t>=log n loglog n
Albers, Hagerup (2)	1997	$O(t)$ t>=log n
Albers, Hagerup (2)	1997	$O(t)$ t>=log n
Albers, Hagerup (3)	1997	$O(\log^2(n))$
Albers, Hagerup (3)	1997	$O(\log^2(n))$
Jang, Kim	1997	$O(4^k)$
Babu, Saxena (1)	1997	$O(\log m)$
Babu, Saxena (2)	1997	$O(\log^2 n)$
Goldberg & Rao (Parallel) (1)	1997	$O(V^{5/3} \log(V) \log(U))$	https://dl.acm.org/citation.cfm?id=290181
Goldberg & Rao (Parallel) (2)	1997	$O(E^0.5 V \log(V) \log(U))$	https://dl.acm.org/citation.cfm?id=290181
Van De Geijn, Watts (SUMMA, Classical 2D)	1997	$O(n^3/p)$
Lee, Robertson, Fortes (Cannon generalized for block-cyclic distributed matrices)	1997	$O(n^3/p)$
Choi (DIMMA)	1997	$O(n^3/p)$
Gupta, Sen	1997	$O(\log h \log \log n)$
Poon, Ramachandran	1997
Poon, Ramachandran	1997
Zaroliagis (1)	1997	$O(\log^2 n)$
Zaroliagis (1)	1997	$O(\log^2 n)$
Zaroliagis (2)	1997	$O(\log n)$
Zaroliagis (2)	1997	$O(\log n)$
Klein, Subramanian	1997	$O(sqrt(n) \log(L) \log(n) \log*(n))$
Brodal, Traff, Zaroliagis	1997	$O(n)$
Liu, Cheung	1997
Lee, Erçal	1997	$O(1)$
Lee, Park, Park	1997	$O((n/p)^2 + (n/p) \log p)$
Hardwick	1997	$O((n \log n \log p)/p)$
Zaki, Parthasarathy, Ogihara, Li	1997
optimal - Hirschberg, Stauffer (1)	1997	$O(m+\log{m}\log{n})$
LEF - Hirschberg, Stauffer (2)	1997	$O(\log^2{n})$
Hariharan	1997	$O(\log^4(n))$	O(n)
Farach	1997	$O(\\log n)$	O(n)
Karpinski	1996	$O(n^{0.6})$	$O(1)$
Czumaj	1996	$O(\log n)$	$O(n)$
Czumaj	1996	$O(\log \log n)$	$O(n)$
Coplanar facets merging - A.D. Kalvin and R.H. Taylor 1996	1996
Controlled vertex/edge/face decimation - M.E. Algorri and F. Schmitt 1996	1996
Controlled vertex/edge/face decimation - Guéziec 1996	1996
Controlled vertex/edge/face decimation - R. Ronfard and J. Rossignac 1996	1996
Controlled vertex/edge/face decimation - Cohen; J.; Varshney; A 1996	1996
Vertex clustering - Reddy 1996	1996
Wavelet-based - M.H. Gross; O.G. Staadt and R. Gatti 1996	1996
Wavelet-based - Certain; A.; Popovic; J.; 1996	1996
Simplification via intermediate hierarchical rep-resentation - Andujar 1996	1996
Simplification via intermediate hierarchical rep-resentation - He; T.; Hong; 1996	1996
Prakesh Ramanan	1996	$O(\log^4 n)$	$O(n)$
General number field sieve	1996	$O(\exp((1+o(1))(64n/9)^{1/3}(log n)^{2/3})$ , under assumption about numbers in a sequence behaving randomly in a given range	$O(\Gamma n^{4/3} \log n)$
Naimi-Trehel's algorithm	1996	$O(\log n)$	$O(1)$ per process, $O(n)$ total
Von zur Gathen-Gerhard additive FFT	1996	$O(n (\log n)^2)$	$O(n)$
Optimal Register Allocation (ORA), Goodwin & Wilken Algorithm	1996	$O(n^3)$	Depends on the choice of 0-1 ILP solver
Drysdale; Su	1996	$O(n)$	$O(n)$
Balasubramanian; Fellows	1996	$O(kn + 1.324718^k k^2)$	$O(k^3)$ auxiliary (potentially $O(k^2)$ )
Papadimitriou and M Yannakakis	1996	$O(3^k n)$	$O(k)$ auxiliary
Demand-Driven Register Allocation	1996	$O(n^2)$	$O(n^2)$
Particle filter Del Moral	1996	$O(n^3)$	$O(nN)$
Tushar Deepak Chandra and Sam Toueg	1996	$O(n)$
RIPEMD-160	1996	$O(n)$	$O(1)$
N-dimensional Quickhull	1996	O(n*f(h)/h) where f(h) denotes the maximum number of facets with h vertices
Papadimitriou and M Yannakakis 1996 + Buss	1996	O(3^k k^2+kn)	O(k^2) auxiliary
Goodrich	1996	O(n log(n)/p + (L+gn/p)(log(n)/(log(n/p)))
Gerbessiotis, Siniolakis	1996	(1+floor(e(1-e)^(-1))(e/2) +o(1))(T_seq/p) computation + $O(gT_seq/(p \log n))$ communication = $O(n \log n/p)$ computation + $O(g n/p)$ communication
Olariu, Schwing	1996	$O(1)$
Jianxian	1996	$O(n \log n/p)$ + $O(n)$
JaJa, Ryu, Vishkin (1)	1996	$O(\log^2 n/loglog n)$
JaJa, Ryu, Vishkin (2)	1996	$O(\log n)$
samplesort - Helman, JaJa, Bader (1)	1996	$O(n/p \log{n} + \tau + n/p \sigma)$ whp
regular sampling - Helman, JaJa, Bader (2)	1996	$O(n/p \log{n} + \tau + n/p \sigma)$
Folwell, Guha, Suzuki	1996	$O(n^0.5)$
Folwell, Guha, Suzuki	1996	$O(n^0.5)$
Prakesh Ramanan	1996	$O(\log^4 n)$	$O(n)$
Grayson, Shah, Van De Geijn (Strassen-2D)	1996	(7/8)^l*n^3/P
Ajtai & Megiddo	1996	$O((\log \log n)^d)$
Cole, Klein, Tarjan	1996	$O(\log n)$
Cole, Klein, Tarjan	1996	$O(\log n)$
Chong	1996	$O(\log n \log \log n)$
Chong	1996	$O(\log n \log \log n)$
Lee, Lee	1996
CESARI, MAEDER (parallel Karatsuba's) (1)	1996
CESARI, MAEDER (parallel Karatsuba's) (2)	1996
Alonso et al.	1996	$O(\log^2 n)$
Narayanaswami	1996	$O(n/p)$
Ravikumar, Xiong	1996	$O((kn \log n)*max(1, (\log n)/p))$
Ferreira, Robson	1996	$O(n * 2^(n/2) * sigma(2^(n/2))/p)$	O(n)
Agrawal, Shafer	1996
Franaszek, Robinson, Thomas	1996
Karger; Klein & Tarjan	1995	$O(\min(V^2, E \log V))$	$O(E)$
Perumalla and Deo	1995	$O(\log n)$	$O(n)$
Khuller; Matias	1995	$O(n)$	$O(n)$ , not sure if this is auxiliary
Beigel & Eppstein	1995	$O(1.3446^n)$	$O(n^2)$
Balaban.	1995	$O(n \log n + k)$	$O(n)$
Seidel's algorithm	1995	$O(n^{2.373} \log n)$	$O(n^2)$
Seidel's algorithm	1995	$O(n^{2.373} \log n)$	$O(n^2)$
The Wang and Brady corner detection algorithm 1995	1995	$O(n^2)$
Hanrahan–Krueger	1995	$O(n^2 \log n)$
Bijaoui and Rué	1995	$O(n^2)$
Wavelet-based - D.J. Hebert and H-J. Kim 1995	1995
Wavelet-based - Eck; M.; DeRose; T.; 1995	1995
Simplification via intermediate hierarchical rep-resentation - He; T.; Hong; L.; Kaufman 1995	1995
Barto;Bradtke; & Singhe; 1995;	1995
Rick (Algorithm 2)	1995	$O(sn + \min(r(n - r), rm))$	$O(sn + p)$
Rick (Section 4)	1995	$O(sn + \min(sp, rm))$	$O(sn + p)$
Gremban; Miller; Zagha	1995	$O(n^2)$	$O(n^2)$
The Algorithm of Park; Chen; and Yu (PCY)	1995	$O(n^2)$	$O(n^2)$
Ukkonen	1995	$O(n)$	$O(n)$
ECK M.; DEROSE T.; DUCHAMP T.; 1995	1995	$O(n^2)$
Bailey TL; Elkan C MEME	1995	$O(n^2m^2)$	$O(mn)$
Downey, Fellows	1995	O(kn+2^k k^2)	O(k^2) auxiliary
Han and Shen	1995	$O(n \log \log min(m,n)/p + \log n)$
Han and Shen	1995	$O(n \log \log min(m,n)/p + \log n)$
Bast, Hagerup	1995	$O(\log{n}/ \log{\log{n}})$ whp
Bast, Hagerup	1995	$O(\log{n}/ \log{\log{n}})$ whp
Das, Sinha	1995	3n^(1/3) log(n^(1/3))+14n^(1/3)+ $O(n^(1/3))$
Andersson, Hagerup, Nilsson, Raman (1)	1995	$O(\log n)$
Andersson, Hagerup, Nilsson, Raman (1)	1995	$O(\log n)$
Andersson, Hagerup, Nilsson, Raman (2)	1995	$O(\log n)$ expected
Andersson, Hagerup, Nilsson, Raman (2)	1995	$O(\log n)$ expected
MM-sort - Zhang, Zheng	1995	$O(n/p \log p)$
Jang, Prasanna	1995	$O(1)$
(padded sorting) Goldberg, Zwick	1995	$O(log n/(log k) loglog^3(k) 2^(O(\logn-\logk))$
Tridgell, Brent	1995	$O(n/p \log{n/p} +n)$
Parallel Sorting by Median-Median (PSMM) - Min	1995	$O(n/p \log{n/p} +p^2 \log{n/p})$
Louri, Hatch, Na	1995	$O(1)$
Zhang, Zheng	1995	$O(n/p \log{n})$
Agarwal, Bale, Gustavson, Joshi, Palkar (P_GEMM, Classical 3D)	1995	$O(n^3/p)$
Luo, Drake (2D-Strassen) (1)	1995	$O(n^{\log 7}/P^{(\log 7−1)/2})$
Luo, Drake (Strassen-2D) (2)	1995	(7/8)^l*n^3/P
Galil	1995	$O(1)$
Czumaj, Galil, Gąsieniec, Park, Plandowski (1)	1995	$O(\log n)$
Czumaj, Galil, Gąsieniec, Park, Plandowski (2)	1995	$O(\log n)$
Andrews et al. (1)	1995	$O(\log^3 n)$
Andrews et al. (2)	1995	$O(\log^3 n)$
Callahan, Kosaraju	1995	$O(\log{n})$
Callahan, Kosaraju	1995	$O(\log{n})$
Belinskaya, DeAgostino, Storer	1995	$O(km + m\log{m})$
Farach, Muthukrishnan (1)	1995	$O(\log{d}+\log{n})$
Farach, Muthukrishnan (2)	1995	$O(\log{n})$
Nagumo, Lu, Watson (1)	1995	$O(L+\log{n})$
longest-fragment-first (LFF) dictionary compression - Nagumo, Lu, Watson (2)	1995	$O(L+\log{n})$
Perumalla and Deo	1995	$O(\\log n)$	O(n) auxiliary
Wen (1)	1995	$O(\log n)$
KALYAN PERUMALLA and NARSINGH DEO	1995	$O(\log n)$
Wen (2)	1995	$O(\log n)$
Jana, Sinha	1995	$O((n^2 \log n)/p)$
Schiermeyer	1994	$O(1.415^n)$	$O(nm+n^2)$ loose bound, possibly $O(n+m)$
D*	1994	$O(b^d)$	$O(b^d)$
O(lg N) algorithm	1994	$O(n \log p)$	$O(1)$ auxiliary
Lindeberg (1994)	1994	$O(n^2)$
Hessain Determinant Lindeberg 1994	1994	$O(n^3)$
Multiple Resolution segmentation - J. Liu and Y. H. Yang (1994)	1994	$O(n^2)$
Controlled vertex/edge/face decimation - Hamann 1994	1994
Generalized expectation maximization (GEM) algorithm	1994	$O(n^4 \log^{1.5} n)$	$O(n+r)$
de Bruijn Graph (Idury, Waterman)	1994	$O(n^2)$	$O(n)$
String Graph (Myers)	1994	$O(n \log n)$	$O(n)$
A-Priori algorithm	1994	$O(n^2)$	$O(n^2)$
Tomas Feder, Nimrod Megiddoy, Serge A Plotki	1994	$O(n^{0.5})$	$O(n^{0.5})$ auxiliary per processor
Süleyman Cenk Sahinalp ; Uzi Vishkin	1994	$O(\log^2 n)$	$O(n^{1+\epsilon})$ for any fixed $\epsilon>0$
Jeuring	1994	$O(n)$	$O(n)$
V. A. Lyul’ka and A. V. Romanenko	1994	$O(n^5)$
Expectation conditional maximization either (ECME) (Liu; Chuanhai; Rubin; Donald B)	1994	$O(n^3)$	$O(n+r)$
RC5	1994	$O(n)$	$O(k+rw)$
WalkSAT	1994	O(nmtmf)	O(n)
Nuutila, Soisalon-Soininen	1994
Skala	1994
Parallel Sorting by OverPartitioning (PSOP) - Li, Sevcik (Quicksort / PQOP)	1994	$CQn log n /p+CQpsk log(psk)+CQpk log(pk) +2t_r psk/W +t_r n/(pW)$
Parallel Sorting by OverPartitioning (PSOP) - Li, Sevcik (Quicksort / PQOP)	1994	$CQn log n /p+CQpsk log(psk)+CQpk log(pk) +2t_r psk/W +t_r n/(pW)$
Chen, Chen	1994	$O(1)$
Chen, Chen (generalized)	1994	$O(4^(k+1))$
Gibbons, Matias, Ramachandran (1)	1994	$O(\log^2(n)/loglog(n))$
Gibbons, Matias, Ramachandran (2)	1994	$O(\log n)$
Gibbons, Matias, Ramachandran (3)	1994	$O(\log n)$
Nikolopoulos, Danielopoulos	1994	$O(\log^2{n})$
Lu & Lin (1)	1994	$O(\log^2 m + \log n)$
Lu & Lin (2)	1994	$O(\log^2 m \log \log m)$ if log^2 m log log m > log n else $O(\log n)$
Agarwal, Gustavson, Zubair	1994	$O(n^3/p)$
Dumitrescu, Roch, Trystram (1)	1994	$O(n^\log 7)$
Dumitrescu, Roch, Trystram (2)	1994	$O((n/2^k)^\log 7)$
Choi, Walker, Dongarra (PUMMA)	1994	$O(n^3/p)$
Mathur, Johnsson (multiple algorithms)	1994	$O(PQR/N)$
Amato, Goodrich, Ramos [output-sensitive] (1)	1994	$O(\log^3 n)$
Amato, Goodrich, Ramos [randomized] (2)	1994	$O(n^(floor(d/2))+n \log n)$
Amato, Goodrich, Ramos [randomized] (3)	1994	$O(n^(floor(d/2))+n \log n)$
Halperin, Zwick	1994	$O(\log n)$
Iwama, Kambayashi	1994	$O(l(n \log(n) + m )/p)$
Sorenson	1994	$O(\log^{2d+2} n)$
Karpinski, Rytter	1994	$O(n^(1-eps) \log n)$
Neff	1994	$O(\log^3{n+m+\mu})$
Neff	1994	$O(\log^3{n+m+\mu})$
Schenk	1994	$O(m/p + r \log p + min(m, r \log n))$	https://www.proquest.com/docview/919780720?pq-origsite=gscholar&fromopenview=true
Stauffer, Hirschberg	1994	$O(L \log{n})$
Tomas Feder, Nimrod Megiddo, Serge A. Plotkin	1994	$O(\Delta^{0.5} \log^3(\Delta)$	$O(n^{0.5})$ auxiliary per processor
Süleyman Cenk Sahinalp ; Uzi Vishkin	1994	$O(n^\epsilon)$	$O(n^{(1+\eps)})$ for any fixed eps>0
Sorenson (left shift k-ary)	1994	$O(n/\log k + (\log n)^2(\log \log n))$
Sorenson (right shift k-ary)	1994	$O(n/\log k + (\log n)^2(\log \log n))$
Klawe; Mumey	1993	$O(n)$	$O(n)$
Lawrence Gibbs Sampling	1993	$O(nm)$	$O(n + m)$
Visvalingam–Whyatt	1993	$O(n^2)$	$O(n)$
Phillips & Westbrook	1993	$O(VE(\log(V)/\log(V/E) + (\log V)^2))$	$O(V + E)$
Rational sieve	1993	$O(e^{\sqrt{(2+o(1))n \log n}})$	$O(n+(B/\log B)^2)$
P.Hanrahan and W.Krueger 1993	1993	$O(k n^2)$
Coplanar facets merging - Hinker; P. and Hansen; C. 1993	1993
Vertex clustering - Rossignac; J. and Borrel; P. 1993	1993
Vertex clustering - Hoppe; H.; DeRose; T.; 1993	1993
Czumaj	1993	$O(\log^3 n)$	$O(n^2)$
de Prisco	1993	$O(n)$	$O(n)$
Berkman; Vishkin	1993	$O(n+m)$	$O(n)$
Schlimmer	1993	$O(n 2^n p)$	$O(2^n)$
Sam Buss	1993	$O(kn + 2^k k^{2k + 2})$	$O(k^2)$
Ukkonen and D. Wood	1993	$O(n^2)$	$O(n^2)$
BOYS algorithm	1993	$O(n^2 k)$	$O(n^2)$
PINKALL U.; POLTHIER K 1993	1993	$O(n^2)$
Expectation conditional maximization (ECM)	1993	$O(n^3)$	$O(n+r)$
Branch and bound	1993	$O(k^{O(n)} \text{poly}(n))$	$O(k^{O(n)})$
SHA-1	1993	$O(n)$	$O(1)$
Blowfish	1993	$O(n)$	$O(n)$
Calvetti, Reichel	1993	$O(n^2)$	$O(n)$
Padded-sort - Hagerup, Raman	1993	$n \log{n}/ \log{k} (\log{\log{k})^5(2^(O(\log{n}-\log{k}+1)))$
Kale, Krishnan	1993	local sort time + ceiling(log_k(p)) $O(\log n)$ (time per histogram) + data movement and merging
Vaidyanathan, Hartmann, Varshney	1993	$O(t(n) \log{m})$
T&B sort - Tridgell, Brent	1993
generalized bitonic sort - Liszka, Batcher	1993	$O(\log^2{n})$
Chen, Reif	1993	$O(\log{n})$ expected
Tianzhen, Zhou, Xiozhen	1993	$O(1)$
Czumaj	1993	$O(\log^3 n)$	$O(n^2)$
Gupta, Kumar (variant of DNS81)	1993	n^3/p + 5/3 t_s log(p) + 5/3 t_w n^2/p^{2/3} log(p)
Dyer	1993	$O(\log n(\log \log n)^(d-1))$
Goodrich	1993	$O(\log^2 n)$
Chong, Lam	1993	$O(\log n \log \log n)$
Suraweera, Bhattacharya	1993	$O(\log m)$
Suraweera, Bhattacharya	1993	$O(\log m)$
Chong, Lam	1993	$O(\log n \log \log n)$
Chong, Lam	1993	$O(\log n \log \log n)$
Callahan	1993	$O(\log n)$
Cohen (d=sqrt(n))	1993	$O(nR \log^3{n}/d)$
Cohen (d=n)	1993	$O(nR \log^3{n}/d)$
Yan (trial division)	1993	pi(sqrt(n))/p
Rational sieve	1993	$O(e^{sqrt((2+o(1))n*logn)}/p)$	O(n+(B/logB)^2)
Caceres, Deo, Sastry, Szwarcfiter	1993	$O(\log^2 V)$	O(1)
Cignoni, Montani, Perego, Scopigno	1993	$O((n/p)^2 + (n/p) \log p)$
Teng, Sullivan, Beichl, Puppo	1993	$O(n^2/p)$
Chen, Davis, Kruskal	1993	$O(\log n)$
Compression/Clustering [Vector Quantization]	1992	Varies by codebook structure	Varies by codebook structure
Simplified Memory-Bounded A* (SMA*)	1992	$O(b^d)$	$O(b^d)$
Cube Sort Parallel Implementation	1992	$O(n \log n)$	$O(n)$
King et al. (KRT)	1992	$O(VE + V^{2+\epsilon})$	$O(V + E)$
Chazelle & Edelsbrunner	1992	$O(n \log n + k)$	$O(n+k)$
Westin; S. H.; Arvo; J. R.; and Torrance; K. E 1992	1992	$O(k n^2)$
Re-tiling - Turk; G 1992	1992
Vatti clipping algorithm	1992	$O(n^2)$	$O(n^2)$
Homotopy method	1992	$O(n^2)$	$O(n^2)$
Homotopy method	1992	$O(n^2)$	$O(n^2)$
Homotopy method	1992	$O(n^2)$	$O(n^2)$
Homotopy method	1992	$O(n^2)$	$O(n^2)$
Homotopy method	1992	$O(n^2)$	$O(n^2)$
Revuz's algorithm	1992	$O(n)$	$O(n)$
Liu	1992	$O(kn^2)$	$O(n)$
Räihä; Manilla	1992	$O(n^2 2^n p \log p)$	$O(n2^n)$
Rivin, Zabih	1992	$O(8^n \text{poly}(n))$	$O(8^n n^2)$
ARIES	1992	$O(n)$	$O(n)$
GSAT	1992	O(nmtmf)	O(n)
Takaoka	1992	O(n^3(log log n/log n)^{1/2})
Cube Sort Parallel Implementation - Cypher, Sanz	1992	$O(n \log^2{n} / (p \log{n/p})$	O(n)
Varman, Doshi	1992	$O(n \log{n}/p + \log^2{p})$
Parallel sorting by regular sampling (PSRS) - Shi, Schaeffer	1992	$O(n/p \log{n})$
MeshSort (generalized Bitonic and Shear Sort) - Corbett, Scherson	1992	$k^2 n \log{n}/2$
Rajesekaran, Sen	1992	$O(n \log{n} \log{\log{\log{n}}} / (p \log{\log{n}}))$
Rajesekaran, Sen	1992	$O(n \log{n} \log{\log{\log{n}}} / (p \log{\log{n}}))$
Hagerup, Raman (comparsion)	1992	$O(\log{n} / \log{k})$ w/ high probability
Hagerup, Raman (random ints)	1992	$O(\log*{n})$ w/ high probability
Hagerup, Raman (random ints)	1992	$O(\log*{n})$ w/ high probability
Hagerup, Raman (ints in range)	1992	$O(1)$ w/ high probability
Hagerup, Raman (ints in range)	1992	$O(1)$ w/ high probability
Hagerup, Raman (ints in range, stable)	1992	$O(\log{\log{n}/ \log{k})$ w/ high probability
Hagerup, Raman (ints in range, stable)	1992	$O(\log{\log{n}/ \log{k})$ w/ high probability
Chen, Das	1992	$O(n/p +\log{n})$
Chen, Das	1992	$O(n/p +\log{n})$
Pairwise Sorting Network - Parberry	1992	$(\log{n}(\log{n}+1)/2$
Galil, Park	1992		$O(n)$
Bradford, Rawlins, Shannon	1992	$O(\log^4 n)$	$O(n)$
Lin, Snyder	1992	$O(n^3/p)$
Bjørstad, Manne, Sørevik, Vajteršic (Winograd's algorithm)	1992	$O(n^3/p)$
Kaltofen, Pan	1992	$O(gammak(n,p) \\log^2{n})$ where gammak(n,p)= $O(\\log^3{n})$ for singular matrices; $O(gammak(n,p) \\log{n})$ for non-singular so, $O(\\log^5{n})$ or $O(\\log^4{n})$ Field must be characteristic 1 $O(\\log^5(n))$
Reif, Sen (implicit)	1992	$O(1)$	O(n+k) total
Rüb	1992	$O(((n+k) \log n \log \log n)/p)$	O(n+k) total
Amato, Preparata	1992	$O(\log^2 n)$
Reif, Sen	1992	$O(\log n)$
Karger, Nisan, Parnas (1)	1992	$O(\log n)$
Karger, Nisan, Parnas (2)	1992	$O(\log n \log \log n)$
Karger, Nisan, Parnas (3)	1992	$O(\log^1.5(n))$
Johnson, Metaxas	1992	$O(\log^{3/2}(n))$
Johnson, Metaxas	1992	$O(\log^{3/2}(n))$
Karger	1992	$O(\log n)$
Karger	1992	$O(\log n)$
Lenhof & Smid	1992	$O((\log n)^2 \log \log n)$
Takaoka	1992	$O(\log^2(n))$
Han, Pan & Reif (1)	1992	$O(\log^2(n))$
Han, Pan & Reif (2)	1992	$O(\log(n)*\log(\log n))$
Han, Pan & Reif (3)	1992	$O(\log n)$
Graham, Iyengar, Zheng	1992	$O(n/p)$
Narendran, Tiwari	1992	$O(n^2(\log{n} + \log^2{X}))$
Narendran, Tiwari	1992	$O(n^2(\log{n} + \log^2{X}))$
Frieze, Miller, Teng	1992	$O(\log{n})$
Frieze, Miller, Teng	1992	$O(\log{n})$
Chaudhuri	1992	$O(\log n)$	O(V^2)
Cho, Huynh	1992	$O(\log^2 n)$
Barnard, Skillicorn	1992	$O(n^2)$
Agostino, Storer (1)	1992	$O(L+\log{n})$
Agostino, Storer (2)	1992	$O(L+\log^2{n})$
Penzhorn	1992	$O(n)$
Kruskal’s algorithm with demand-sorting	1991	$O(E \log V)$	$O(E)$
Tuned Boyer-Moore algorithm	1991	$O(mn)$	$O(m + s)$
Lindeberg's watershed-based grey-level blob detection algorithm 1991	1991	$O(n^3)$
Sector-Based Culling	1991	$O(n^2)$
He; X. D.; Torrance; K. E.; Sillion; 1991	1991	$O(k n^2)$
Chen's lambda-connected segmentation	1991	$O(n \log n)$
Coplanar facets merging - M.J. De Haemer and M.J. Zyda 1991	1991
Coplanar facets merging - Kalvin; A. D.; Cutting; C. B.; Haddad; B. and Noz; M. E. 1991	1991
Chin and Poon	1991	$O(sn + \min(sp, rm))$	$O(p + n)$
Two-way String-Matching Algorithm	1991	$O(n + m)$	$O(1)$
Raita Algorithm	1991	$O(mn + s)$	$O(s)$
Gabow; Tarjan	1991	$O(V^{0.5} E)$	$O(E)$
Xiaolin Wu's line algorithm	1991	$O(n)$	$O(1)$
Outside-In algorithm	1991	$O(2^n n \logn)$	$O(n)$
MD5	1991	$O(n)$	$O(1)$
IDEA	1991	$O(n)$	$O(n)$
Fredman & Willard	1991	O(E+V)
Buhler, Lenstra, Pomerance	1991
Bhatt, Diks, Hagerup, Prasad, Radzik, Saxena	1991	$O(\log{n}/ \log{\log{n}} + \log{\log{m}})$
Bhatt, Diks, Hagerup, Prasad, Radzik, Saxena	1991	$O(\log{n}/ \log{\log{n}} + \log{\log{m}})$
Matias, Vishkin (random)	1991	$O(\log{n} \log{\log{m}})$ expected
Matias, Vishkin (random)	1991	$O(\log{n} \log{\log{m}})$ expected
Matias, Vishkin (deterministic)	1991	$O(\log{n})$
Matias, Vishkin (deterministic)	1991	$O(\log{n})$
Deo, Sarkar	1991	$O(n/p \log{n/p} + (n/p + \log{p} \log{n}) \log{n/p}$
Parallel Quicksort - Chlebus, Vrt'o	1991	$O(\log{n})$ w/ high probability
Das, Moser, Melliar-Smith	1991	$O(n \log^2{n}/p)$
Lin, Lu, Fang	1991	max(log^2 m log log m, log n)
Ho, Johnsson, Edelman	1991	$O(n^3/p)$
Lee, Aboelaze (Winograd's algorithm)	1991	$O(n^2)$
Bader, Gehrke	1991	$O(n^3/p)$
Ghouse, Goodrich (following [Kirkpatrick, Seidel (1986)])	1991	$O(\log^2 n)$
Ghouse, Goodrich [Theorem 5]	1991	$O(\log n)$
Ghouse, Goodrich (following [Edelsbrunner, Shi (1991)])	1991	$O(\log^3 n)$
Ghouse, Goodrich [Theorem 6]	1991	$O(\log^2 n)$
Cole, Vishkin	1991	$O(\log n)$
Johnson, Metaxas	1991	$O(\log^{3/2}(n))$
Cole, Vishkin	1991	$O(\log n)$
Cole, Vishkin	1991	$O(\log n)$
Gazit	1991	$O(\log(n))$
Gazit	1991	$O(\log(n))$
Amato	1991	$O(\log^2 n)$
Spencer	1991	$O((n/p) \log n \log(pL))$
Hagerup (1)	1991	$O(1)$
Hagerup (2)	1991	$O(\log*n)$
Hagerup (3)	1991	$O(\log^2 n)$
Hagerup (4)	1991	$O(\log n)$
Matias et al.	1991	$O(\log*n)$
Ma, Iwama, Takaoka, Gu	1991	$O(\\log^2 n)$	O(V^2)
Ferreira	1991	$O(n2^(neps/2))$	O(n)
Crochemore, Rytter	1991
Naor	1991	$O(\log{n})$ expected
Kedem, Palem, Pantziou, Spirakis, Zaroliagis	1991	$O(\log^4{n}/ \log{\log{n}})$ whp
Lawrence, Reilly	1990	$O(nm)$	$O(nm)$
Coppersmith–Winograd algorithm	1990	$O(n^{2.3755})$	$O(n^2)$
Cheriyan et al.	1990	$O(V^3 / \log V)$	$O(V + E)$
Alon	1990	$O(VE + V^{2.66} \log V)$	$O(V + E)$
Gabow Ahuja Algorithm	1990	$O(E + V \sqrt{\log(L)} )$	$O(E + \log C)$
Nakamae; E.; Kaneda; K.; Okamoto; T.; and Nishita 1990	1990	$O(k^3 n^2)$
Cabral; B.; Max; N.; and Springmeyer; R 1990	1990	$O(k n^2)$
Wu et al.	1990	$O(n(m-r))$	$O(m^2)$
Basic Local Alignment Search Tool (BLAST)	1990	$O(mn)$	$O(mn)$
Blum	1990	$O(V^{0.5} E)$	$O(E)$
Chan-Singhal-Liu	1990	$O(\log n)$	$O(1)$ per process, $O(n)$ total
Vaidya	1990	$O(mn^{3/4})$	$O(n)$
Number Field Sieve (NFS)	1990	$O(\exp((1+o(1))(64n/9)^{1/3}(\log n)^{2/3}))$ , under assumption about numbers in a sequence behaving randomly in a given range	$O(n^{2/3})$
Sorting with Fusion Trees	1990	O((n log n)/(log log n))	O(n)
Takefuji, Lee	1990	2
Hagerup, Shen	1990	$O(\log{n})$
Hagerup, Shen	1990	$O(\log{n})$
Raman	1990	$O(\log{n}/ \log{\log{n}}+ \log{\log{m}})$ w/ very high probability
Raman	1990	$O(\log{n}/ \log{\log{n}}+ \log{\log{m}})$ w/ very high probability
Sharesort - Cypher, Plaxton	1990	$O(\log{n} (\log{\log{n}})^2)$
Leighton, Plaxton (1)	1990	$O(\log{n})$ w/ very high probability
Leighton, Plaxton (2)	1990	$O(m + \log{n})$ w/ very high probability
Abali, Ozguner, Bataineh	1990	$O(n \log{n}/p + p \log^2{n)})$
AGGARWAL, CHANDRA, SNIR	1990	$O(n \log{n} /p)$
Kruskal, Rudolph, Snir	1990	$O(n/p \log{n}/ \log{n/p} +m/p)$
Wang, Chen, Lin	1990	$O(1)$
Dey, Srimani	1990	$O(\log{n})$
Parasort - Wheat, Evans	1990	$O((n/p)^2 +(5n/(3p) + 2 \log^2{n/p} +1) \log{p+1} + 2 \log^3{p+1}/3 + p)$
Powers	1990	$O(\log{n})$
Paterson	1990	$O(\log{n})$
Heidelberger, Norton, Robinson	1990	$O(\log^2{n)})$
Tang	1990
Chen (1)	1990	$O(\log{n})$
Chen (1)	1990	$O(\log{n})$
Chen (2)	1990	$O(\log{n}/ \log{\log{n}})$
Chen (2)	1990	$O(\log{n}/ \log{\log{n}})$
Huang, Kleinrock	1990	$O(n \log{n} /p)$
Lin, Lin	1990	$O(n)$
Huang, Liu, Viswanathan	1990	$O(\log^2 n)$	$O(n)$
Apostolico, Atallah, Larmore, McFaddin (1)	1990	$O(\log m \log n)$
Apostolico, Atallah, Larmore, McFaddin (2)	1990	$O(\log n (\log \log m)^2)$
Galper, Brutlag (synchronous Row Wavefront approach) (1)	1990	$O(ceil(m/p)*(n+p))$
Galper, Brutlag (asynchronous Row Wavefront approach) (also asynch DWF) (2)	1990	$O(ceil(mn/p + p))$
Galper, Brutlag (synchronous Diagonal Wavefront approach) (3)	1990	$O(\sum_i^{m-1} ceil(i/p) + (n-m+1)ceil(m/p) )$
Lu	1990	$O(\log{\rho} \log^2{n})$ + $O(\log m + \log n)$
AGGARWAL, CHANDRA, SNIR	1990	$O(n^3/p + n^2/p^{2/3})$ )
Vaidya	1990	$O((nd)^(1/4)(\log n)^3 L)$
Alon & Megiddo	1990	$O(d^2 \log^2 d)$ with probability approaching 1
Kruskal, Rudolph, Snir	1990	$O(m/p\log(n)/\log(m/(p^2\log(p))) + n/p*\log(p))$
Kruskal, Rudolph, Snir	1990	$O(m/p\log(n)/\log(m/(p^2\log(p))) + n/p*\log(p))$
Han, Wagner (1)	1990	$O(m/p + (n \log n)/p + \log^2 n)$
Das, Deo, Prasad	1990	$O(m/p + n \log p)$
Han, Wagner (2)	1990	$O(m/p + (n \log n)/p + \log^2 n)$
Kruskal, Rudolph, Snir	1990	O(mlog(n)/p + log(n)log(p)
Kruskal, Rudolph, Snir	1990	O(mlog(n)/p + log(n)log(p)
Parallel Lenstra's ECM (Brent)	1990	TP = T_1/P + $O(T_1^{1=2+\eps})$ , T_1 = $O(exp(c(\log f \log \log f)^{1/2}) * (\log N)^2)$ expected, where c is a constant
Apostolico et al. (1)	1990	$O(\log m \log n)$
Apostolico et al. (2)	1990	$O(\log n (\log \log m)^2)$
Osiakwan, Akl	1990	$O(n^3/p + n^2 \log n)$	O(1)
Pang	1990	$O(n/p)$
Wright	1990	$O(n/p)$
Schieber, Vishkin	1990	$O(\log{\log{n}})$
Cole, Goodrich, Ó'Dúnlaing [Theorem 7.1]	1990	$O(\log n \log \log n)$
Cole, Goodrich, Ó'Dúnlaing [Theorem 7.2]	1990	$O(\log^2 n)$
Berkman, Vishkin	1990	$O(m*alpha(n))$	https://www.proquest.com/docview/919780720?pq-origsite=gscholar&fromopenview=true
Cole, Goodrich, Ó'Dúnlaing	1990	$O(\log^2 n)$
Djokić et al [enumeration of subsets]	1990	$O(n*2^n/p)$	O(n)
Chang, Henschen	1990	$O(n+e_max)$
Egecioglu, Gallopoulos, Koc	1990	$O(\log n)$
Chor, Goldreich [CRCW]	1990	$O(n/\log n)$
Chor, Goldreich [CREW]	1990	$O((n \log \log n)/(\log n))$
Petford and Welsh	1989	$O(n \log n)$	$O(n)$
Cheriyan & Hagerup	1989	$O(VE \log V)$	$O(V + E)$
Goodrich	1989	$O(\log^2(n))$	$O(n+k)$
Bird	1989	$O(n)$	$O(1)$ auxiliary
Ward anisotropic	1989	$O(n^{1.67} \log^2 n)$
David Mumford and Jayant Shah (1989)	1989	$O(n^2)$
Kuo and Cross	1989	$O(p + n(r+\log n))$	$O(p + n)$
Levcopoulos; Lingas; Sack	1989	$O(n)$	$O(n)$
M. Chrobak and D. Eppstein	1989	$O(n d^2 2^d)$	$O(n)$
Chen Ensembles of classifiers	1989	$O(n^2 \log n)$
Leases (Cary G Gray and David R Cheriton)	1989	$O(n)$	$O(f)$
Gries, Martin	1989	$O(n^3)$	$O(n^2)$
Scapegoat Tree	1989	O(nlogn)	O(n)
Treap	1989	O(nlogn)	O(n)
Scapegoat Tree	1989	O(n)	O(1)
Treap	1989	O(n)	O(1)
Scapegoat Tree	1989	O(n)	O(1)
Treap	1989	O(n)	O(1)
Scapegoat Tree	1989	O(nlogn)	O(1)
Treap	1989	O(n)	O(1)
Rajesekaran, Reif (1)	1989	$O(\alpha \log{n})$ w/ high $(1-n^(-\alpha))$ probability
Rajesekaran, Reif (1)	1989	$O(\alpha \log{n})$ w/ high $(1-n^(-\alpha))$ probability
Rajesekaran, Reif (2)	1989	$O(\alpha \log{n} / \log{\log{n}})$ w/ high $(1-n^{-\alpha})$ probability
Rajesekaran, Reif (3)	1989	$O(\alpha \log{n} / \log{log{n}}) w/ high$ (1-n^{-\alpha})$ probability
Rajesekaran, Reif (3)	1989	$O(\alpha \log{n} / \log{log{n}}) w/ high$ (1-n^{-\alpha})$ probability
shearsort - Scherson, Sen	1989
Hagerub, Rub	1989	$O(\log^2{n})$
Bitonic Merge Sort Parallel Implementation - Bilardi, Nicolau	1989	$O((n \log{n})/p)$	O(1)
Parallel iterated bucket sort - Chlebus	1989	$O(\log{n})$
Parallel iterated bucket sort - Chlebus	1989	$O(\log{n})$
SmoothSort - Plaxton (adaptive)	1989	$O(n/p \log^2{p}/ \loxg{n/p} + \log^3{p} \loxg{n/p})$
SmoothSort - Plaxton (nonadaptive)	1989	$O(n/p \log^2{p} / \log{n/(p \log{p})})$
SquareSort - Plaxton	1989	$O(\log^2{n})$
parallel binsort 0 - Seidel, George (1)	1989
parallel binsort 1 - Seidel, George (2)	1989
parallel binsort 2 - Seidel, George (3)	1989
Periodic Balanced Sorting Network - Dowd, Perl, Rudolph, Saks	1989	$O(\log^2{n})$
Aggarwal, Chandra, Snir	1989	$O(n \log{n} /p + l \log{p})$
Martel, Gusfield	1989	$O(\log{n})$ expected
Gallo, Grigoriadis, Tarjan	1989	$O(V^2 \log(V))$	can be derived
Ahuja, Orlin	1989	$O(V^2 \log(U) \log(E/V))$	can be derived
Berntsen (Classical 3D)	1989	n^3/p + 2 t_s p^{1/3} + 1/3 t_s log(p) + 3 t_w n^2/p^{2/3}
Goodrich	1989	$O(\log^2(n))$	O(n+k) total
Atallah, Cole, Goodrich	1989	$O(\log n)$	O(n+k) total
Akl	1989	$O(n^eps \log n)$
Kedem et al.	1989	$O(\log n)$
Berkman et al.	1989	$O(\log \log m)$
Rajasekaran et al.	1989	$O(\log n/\log \log n)$
Berkman et al.	1989	$O(\log n \log \log \log n)$
Theoharis, Page (1)	1989	$(P+6)t_{clip.one.plane}$
Theoharis, Page (2)	1989	$6 \lceil P/n^2 \rceil t_{clip.one.plane}$
parallel Graeffe's method - Rice, Jamieson	1989	$O(1)$
Reif, Sen	1989	$O(\log n)$
Reif, Sen	1989	$O(\log n)$
Akl	1989	$O(\log n)$
Eberly	1989	$O(\log n)$
Harris and Stephens algorithm	1988	$O(n^2)$
Hinrichs; Nievergelt; Schorn	1988	$O(n \log n)$	$O(n)$
Szymanski's algorithm	1988	$O(n)$	$O(1)$ per process, $O(n)$ total
J. J. Koenderink and W. Richards 1988	1988	$O(n^3)$
Johnson	1988	$O(1.4422^n)$
Wang-Zhu-Cantor additive FFT	1988	$O(n(\log n)^{1.585})$	$O(n)$
Schieber; Vishkin	1988	$O(n+m)$	$O(n)$
Katajainen and M. Koppinen	1988	$O(n \log n)$
Higham	1988	$O(n^2)$	$O(n)$
Parallel Merge Sort - Cole (1)	1988	O(logn)
Parallel Merge Sort - Cole (2)	1988	O(logn)
Schieber; Vishkin [Parallel]	1988	O(m+log(n))	O(n) total (auxiliary)
Kunde	1988	$rn+O(n^{1-1/r})$
Parallel Merge Sort - Cole (1)	1988	$O(\log{n})$
Francis and Mathieson	1988	$O(n \log{n}/p + n \log{p}/p)$
parallel shellsort - Quinn	1988	$O(n^{3/2})$
Quicksort with quickmerge - Quinn	1988	$O((n/p)^2+p \log{n/p}+n \log{p} + p)$
Jagadish	1988	$O(n)$
Saxena, Bhatt, Prasad	1988	$O(\log{n}/\log{\log{m}})$
Rytter	1988	$O(\log^2 n)$	$O(n)$
Aggarwal & Park	1988	$O(\log m \log n)$
Mathies	1988	$O(\log m \log n)$
Gazit, Miller (parallel Coppersmith & Winograd 1987)	1988	$O(\log n)$
Fox, Johnson, Lyzenga, Otto, Salmon, Walker	1988
Aggarwal, Chazelle, Guibas, Ó'Dúnlaing, Yap	1988	$O(\log n)$	O(n+k) total
Miller; Stout	1988	$O(\log n)$	O(n) total
Aggarwal, Chazelle, Guibas, Ó'Dúnlaing, Yap	1988	$O(\log n)$
Cole, Goodrich	1988	$O(\log n)$	O(n) total
Aggarwal, Chazelle, Guibas, Ó'Dúnlaing, Yap	1988	$O(\log^3 n)$
Cole & Gooddrich	1988	$O(\log n)$
van de Vorst (grids) (1)	1988
van de Vorst (blocks) (2)	1988
Mathies	1988	$O(\log m \log n)$
Sinha, Srimani	1988
Aggarwal, Chazelle, Guibas, Ó'Dúnlaing, Yap	1988	$O(\log^2 n)$
Levcopoulos, Katajainen, Lingas	1988	$O(\log^2 n)$
JaJa, Kosaraju	1988	$O(\log^2 n)$
Schieber; Vishkin [Parallel]	1988	$O(m+\log(n))$	https://www.proquest.com/docview/919780720?pq-origsite=gscholar&fromopenview=true
Dahlhaus, Karpinski	1988	$O(\log^3{nM})$
Aggarwal, Chazelle, Guibas, Ó'Dúnlaing, Yap	1988	$O(\log^2 n)$
Apostolico, Iliopoulos, Landau, Schieber, Vishkin	1988	$O((\log n)/eps)$	O(n)
Gibbons et al.	1988	$O(\log^4 n)$
Rodger	1988	$O(\log n)$
Larmore	1987	$O(n^{1.6})$	$O(n)$
Rabin-Karp (RK) algorithm	1987	$O(mn)$	$O(1)$
Nicholl–Lee–Nicholl	1987	$O(n)$	$O(1)$
Fast clipping	1987	$O(n)$	$O(1)$
Prim's algorithm + Fibonacci heaps; Fredman & Tarjan	1987	$O(E + V \log V)$	$O(V)$
Lenstra elliptic curve factorization	1987	$O(e^{\sqrt{(1+o(1))n\log n}})$	$O(n)$
Fortune	1987	$O(n \log n)$	$O(n)$
Overlap Layout Consensus	1987	$O(n^2)$	$O(n^2)$
Förstner algorithm 1987	1987	$O(n^2 \log^2 n)$
Contribution Culling	1987	$O(n^2)$
Kass; Witkin and Terzopoulos	1987	$O(n^2)$
Apostolico and Guerra (HS1 Algorithm)	1987	$O(m \log n +p \log(2mn/p))$	$O(p + n)$
Apostolico and Guerra (Algorithm 2)	1987	$O(rm + sn + n \log s)$	$O(p + sn)$
Ahuja, Orlin, Tarjan	1987	$O(VE \log((V \log U)/(E \log \log U) + 2))$
SMAWK algorithm	1987	$O(n(1+\log(n/m)))$	$O(n)$
Dwyer	1987	$O(n \log n)$	$O(n)$
Brute force	1987	$O(k^{O(n)} \text{poly}(n))$	$O(n)$
Saalfeld (Sign of offset)	1987	$O(n)$	$O(1)$
Rabin-Karp (hashing-based)	1987	$O(k(n-k))$	$O(\max(n, \sigma^k))$
Fredman & Tarjan	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
Tarjan (directed, general)	1987	O(ElogV)	O(E)
Tarjan (directed, dense)	1987	O(V^2)	O(E)
Divide and Conquer	1987	O(m*log(n))	O(log(n)) auxiliary
Hagerup	1987	$O(\log{n})$
Hagerup	1987	$O(\log{n})$
Akl, Santoro	1987	$O(\log^2{p}+n/p \log{n})$
paralleldouble distributive partitioning sort - Noga	1987	$O(n)$
Fox, Otto, Hey (aka broadcast-multiply-roll)	1987	2M^3/Nt_flop + 2M^2/sqrt(N)t_comm + sqrt(N)(sqrt(N)-1)*t_start
Johnsson, Ho (multiple algorithms)	1987	$O(PQR/N)$
Cosnard, Robert, Trystram (Jordan method)	1987	$O(n^2)$
Cosnard, Robert, Trystram (Huard method)	1987	$O(n^2)$
Dadoun, Kirkpatrick [randomized]	1987	$O(\log^2 n)$
Dadoun, Kirkpatrick [deterministic]	1987	$O(\log^2 n \log* n)$
Cole, Vishkin	1987	$O(\log^2 n)$
Awerbuch, Shiloach	1987	$O(\log m)$
Awerbuch, Shiloach (1)	1987	$O(\log^2(n))$
Awerbuch, Shiloach (1)	1987	$O(\log^2(n))$
Awerbuch, Shiloach (2)	1987	$O(\log m)$
Awerbuch, Shiloach (2)	1987	$O(\log m)$
Driscoll, Gabow, Shrairman, Tarjan	1987	$O(m/p)$
Driscoll, Gabow, Shrairman, Tarjan	1987	$O(m/p + n \log n)$
Silverman (multiple polynomial quadratic sieve)	1987
Kim, Chwa	1987	$O(n \log n \log \log n)$
Akl	1987	$O(n!/k * n)$
Norton, Silberger	1987	$O((n/p) \log n)$
Swarztrauber	1987	$O(\log n)$
Dongarra, Sorensen	1987	$O( n^3 / p )$
Dadoun, Kirkpatrick	1987	$O(\log^2 n)$
Smith	1987	$O(\log^2 n)$
Landau, Schieber, Vishkin	1987	$O(\log n)$
Kannan, Miller, Rudolph	1987	$O((n \log \log n)/(\log n))$
Strassen's algorithm	1986	$O(n^{\log(54)/\log(5)})$ , approximately $O(n^{2.4785})$	$O(n^2)$
Tree sort	1986	$O(n \log n)$	$O(n)$
Shell Sort (Sedgewick)	1986	$O(n^{1.33})$	$O(1)$
CHAZELLE	1986	$O(n\log^2(n)/(\log \log n) + k)$	$O(n+k)$
Occlusion Culling	1986	$O(n^2)$
Iterated conditional modes algorithm	1986	$O(n^2)$
Nate Green	1986	$O(n^4)$
Apostolico–Giancarlo Algorithm	1986	$O(m + s + n)$	$O(m)$
Sattolo's algorithm	1986	$O(n)$	$O(1)$
Divide-and-conquer	1986	$O(n \log n)$	$O(n^2)$
Divide-and-conquer	1986	$O(n \log n)$	$O(n^2)$
Fortune's algorithm	1986	$O(n \log n)$	$O(n)$
CHAZELLE 1986	1986	O(n^1.695)	O(n)
Seidel's Shelling Algorithm	1986	O(n^2+f_1*log(n))
Gabow et al, Section 2	1986	O(E*log(beta(E, V)))	O(E) auxiliary
Gabow et al, Section 3	1986	O(E+VlogV)	O(E+V)
Wagner, Han	1986	$O(ceiling(log m/ log(n/p + log p))(n/p+log p)$
Wagner, Han	1986	$O(ceiling(log m/ log(n/p + log p))(n/p+log p)$
Schnorr, Shamir	1986	$O(n^{1/2})$
Kunde	1986	$O(n^{1/3})$
Alon, Azar, Vishkin	1986	k rounds
Tsukennan, Gray, Stewart, Uren, Vaughan	1986	$O(\log{n})$
Tsukennan, Gray, Stewart, Uren, Vaughan	1986	$O(\log{n})$
Cole, Vishkin	1986	$O(\log n \log* n)$	$O(n)$
Atallah, Goodrich (1)	1986	$O(\log^2 n)$	O(n+k) total
Atallah, Goodrich (2)	1986	$O(\log n \log \log n)$	O(n+k) total
Atallah, Goodrich	1986	$O(\log n)$
Stout	1986	$O(\log n)$
Gazit	1986	$O(\log(n))$
Cole, Vishkin	1986	$O(\log n)$
Akl	1986	$O(n)$
Akl	1986	$O(n)$
Cole, Vishkin	1986	$O(\log n)$
Cole, Vishkin	1986	$O(\log n)$
Atallah, Goodrich	1986	$O(\log n \log \log n)$
Galil (1)	1986	$O(\log^3 n)$	O(1)
Galil (2)	1986	$O(\log^2 n)$	O(1)
Paardekooper	1986
Ben-Or, Feig, Kozen, Tiwari (BFKT)	1986
Ben-Or, Feig, Kozen, Tiwari (BFKT)	1986
Saxena, Bhatt, Prasad (1)	1986	$O(n)$
Saxena, Bhatt, Prasad (2)	1986	$O(\log n \log \log n)$
Saxena, Bhatt, Prasad (3)	1986	$O(\log \log n)$
Saxena, Bhatt, Prasad (4)	1986	$O(1)$
Tsin [Section 3]	1986	$O(ceil((n+m)/p) \log n)$	https://www.proquest.com/docview/919780720?pq-origsite=gscholar&fromopenview=true
Tsin [Section 4]	1986	$O(n^2/p + \log n)$	https://www.proquest.com/docview/919780720?pq-origsite=gscholar&fromopenview=true
Saxena, Bhatt, Prasad (1)	1986	$O(n)$
Saxena, Bhatt, Prasad (2)	1986	$O(\log n \log \log n)$
Saxena, Bhatt, Prasad (3)	1986	$O(\log \log n)$
Saxena, Bhatt, Prasad (4)	1986	$O(1)$
Landau, Vishkin	1986	$O(\log n)$	O(n)
Reif	1986	$O(\log n)$
Iterative Deepening A* (IDA*)	1985	$O(b^d)$	$O(b^d)$
Petro Vlahos Algorithm	1985	$O(n^2 k/r)$	$O(nk)$
Maekawa's algorithm	1985	$O(n^{0.5})$	$O(1)$ per process, $O(n)$ total
Suzuki-Kasami's algorithm	1985	$O(n)$ (originally this had $O(\log n)$ )	$O(1)$ per process, $O(n)$ total
Kajiya; J. Anisotropic Reflection Models 1985	1985	$O(k n^2)$
Miller and Myers	1985	$O(n(m-r))$	$O(m^2)$
Bisection method	1985	$O(n^2)$	$O(n^2)$
Chiba and Nishizeki	1985	$O(a(G)m)$ per clique	$O(m)$
Guibas; Stofli	1985	$O(n \log n)$	$O(n)$
Irving's Algorithm	1985	$O(n^2)$	$O(n^2)$
Preparata and Shamos (Wedge)	1985	$O(n)$	$O(n)$
Preparata and Shamos (Intersection sum of angle)	1985	$O(n)$	$O(1)$
Tarjan Splay Tree	1985	O(n)	O(1)
Tarjan Splay Tree	1985	O(n)	O(1)
Tarjan Splay Tree	1985	O(n)	O(1)
Reif	1985	$O(\log{n})$
Reif	1985	$O(\log{n})$
Reischuk	1985	$O(\log{n})$ whp
n-sorter - Tseng and Lee	1985	$O(n \log^2{mn} / \log^2{n})$
Lang, Schimmler, Schmeck and Schroder	1985	$O(n^(1/2))$
Owens, JaJa (1)	1985	$O(n +n^2/p^2)$
Owens, JaJa (2)	1985	$O(n/p^{1/2} +n^2/p^2)$
Rudolph	1985	$O(\log^2{n})$
Han	1985	$O(1/ \alpha \log{n})$
Goldberg	1985	$O(V^2 \log(V))$	can be derived
Koubek, Kršňáková (1)	1985	$O(\log(n))$
Koubek, Kršňáková (2)	1985	$O(\log^2(n))$
Reif	1985	$O(\log n)$
Wunderlich (continued fraction factoring)	1985	M^a / (r(a) a^2 log^2 M) / P
Vishkin	1985	$O(\log m)$
Karp, Upfal, Widgerson	1985	$O(\log^3 n)$
Reif	1985	$O(\log n)$
Goodrich	1985	$O(\log{n})$
Parallel Earley's method	1985	$O(n)$
Liang–Barsky	1984	$O(n)$	$O(1)$
Dijkstra's algorithm with Fibonacci heap (Fredman & Tarjan 1984; Fredman & Tarjan 1987)	1984	$O(E + V \log V)$	$O(V)$
Greedy SEQAID	1984	$O(n^2)$	$O(n^2)$
Geman and Geman Markov random fields	1984	$O(n^2)$
Sphere mapping	1984	-
Spaghetti Sort Parallel Implementation	1984	$O(n)$	$O(1)$ auxiliary per processor
Hsu and Du (Scheme 2)	1984	$O(rm \log(n/r) + rm)$	$O(rm)$
Hsu and Du (Scheme 1)	1984	$O(rm \log(n/m) + rm)$	$O(rm)$
Flajolet–Martin algorithm	1984	$O(N)$	$O(\log n)$
Chow's Algorithm	1984	$O(n^2)$	$O(n^2)$
Tarjan's off-line lowest common ancestors algorithm	1984	$O(n+m)$	$O(n)$
S. S. TSENG and R. C. T. LEE	1984	$O(n^2)$	$O(n)$ per processor
Gabow, Galil, Spencer	1984	O(VlogV+Eloglog(logV/log(E/V + 2)))	O(E)
Zaks' prefix reversal algorithm	1984	O(n) on specific permutations	O(n) auxiliary (see NEXT algorithm in same paper)
Harel, Tarjan [Static Trees]	1984	O(n+m)	O(n)
Harel, Tarjan [Linking Roots]	1984	O(n+ m*alpha(m + n, n)) where alpha is the inverse Ackermann function	O(n)
Cyclic sort - Johnsson (1)	1984	$O(n \log n/p)$ when p< $O(\log^2(n))$ when n~=p
Consecutive sort - Johnsson (2)	1984	$O(n \log n/p)$ when p< $O(\log^2(n))$ when n~=p
Bucket sort - Johnsson (3)	1984	$O(n/p+L)$ when p<=L $O(n/p+L+\log p \log L)$ when p>L
Bucket sort - Johnsson (3)	1984	$O(n/p+L)$ when p<=L $O(n/p+L+\log p \log L)$ when p>L
re-circulating systolic sorter (RSS) - Wong, Ito	1984	$O(n)$
Hsu, Du	1984	$O(m \log(n/m) + m)$
Frieze & Rudolph	1984
Akl	1984	$O(n^eps \log h)$
Tsin, Chin	1984	$O(\log^2(n))$
Atallah, Vishkin	1984	$O(\log V)$	O(1)
Awerbuch, Israeli, Shiloach	1984	$O(\log V)$	O(1)
Tsin, Chin	1984	$O(ceil(m/(nK)) \log n + n/K)$	https://www.proquest.com/docview/919780720?pq-origsite=gscholar&fromopenview=true
Vatjersic	1984	$O(\log n)$
S. S. TSENG and R. C. T. LEE	1984	$O(n)$	$O(n)$ per processor
Gabow's algorithm	1983	$O(E \log L/\log(2+(E/V)))$	$O(V+E)$
Digital Differential Analyzer (DDA)	1983	$O(n)$	$O(1)$
Babai and Luks	1983	$\exp(n^{1/2 + o(1)})$
Sorting based [Merge Sort] + real-time elimination	1983	$O(n \log n)$	$O(n)$
Cholesky Decomposition	1983	$O(n^2)$	$O(n^2)$
Sleator and Tarjan [Linking]	1983	O(n+m*log(n))	O(n)
Grahne and Räihä	1983	exponential	exponential
Pomerance, Wagstaff	1983
Ajtai, Komlos, Szemeredi (AKS)	1983	$O(\log{n})$
Kumar and Hirschberg	1983	11n^(1/2)t_r+2log n^(1/2) t_c +5/2 n^(1/2) t_e
Kruskal	1983	1.893 log n loglog n / logloglog n
Akl	1983	$O(n^\epsilon)$
Reif and Valiant	1983	$O(\alpha \log{n}) w/ high (1-n^(-alpha)) probability for big alpha
Miranker, Tang, Wong	1983	$O(n)$
Bollobas and Thomason	1983	2 // $O(1)$
Akl	1983	$O(n^eps)$	$O(n)$
Vishkin	1983	$O(\log n \log \log n)$	$O(n)$
Valiant, Skyum, Berkowitz, Rackoff [implicit]	1983	$O(\log^2 n)$	$O(n)$
Yoo	1983	$O(m)$
Yoo	1983	$O(m)$
Kruskal	1983	$O(\log n \log \log n)$
Er	1983
von zur Gathen	1983	$O(\log^2 n \log^2 k \log p)$
Sedgewick; Szymanski; and Yao	1982	$(\mu + \lambda)(1+\Theta(1/\sqrt{M}))$	$M$
Kadane's Algorithm	1982	$O(n)$	$O(1)$
L. Kitchen and A. Rosenfeld	1982	$O(n^3)$
T. C. Hu ; M. T. Shing	1982	$O(n \log n)$	$O(n)$
NIEVERGELT. J.. AND PREPARATA (Section 3)	1982	$O(n \log n + k)$	$O(n)$
Williams' p + 1 algorithm	1982	$O(2^n)$	$O(n)$
Nakatsu et al.	1982	$O(n(m-r))$	$O(m^2)$
Yao	1982	$O(n^2)$	$O(n^2)$
Fulkerson–Chen–Anstee	1982	$O(n)$	$O(1)$
NIEVERGELT. J.. AND PREPARATA (Section 2)	1982	O((n+k)log n)	O(n+k)
Lien	1982	O(k^2 n^2)	O(k^2)
Dohi et al.	1982	n b tau (a+1+(n-l)/2^(l-1))
Parallel enumeration sorting scheme - Yasuura et al.	1982	$2n$
N&S sort - Nassimi, Sahni	1982	$O(k \log{n})$
Cheung, Dhall, Lakshmivarahan, Miller, Walker	1982	$O(n)$
Kamdoum	1982	Worth mentioning that the typical bad case for simplex is $O(2^n)$ iterations, with d=Theta(n). https://mathoverflow.net/questions/127423/how-many-vertices-can-a-convex-polytope-have says guaranteed bound $O(n^floor(d/2))$ . I've plugged in 2^n iterations here, because that's probably the more cited worst case.
Akl	1982	$O(1)$
Chin et al.	1982	$O(\log^2(n))$
Chin et al.	1982	$O(\log^2(n))$
Chin et al.	1982	$O(\log^2(n))$
Nath and Maheshwari	1982	$O(\log^2(n))$
Shiloach and Vishkin	1982	$O(\log(n))$
Vishkin	1982	$O(n^2/p)$
Kucera	1982	$O(\log(n))$
Nath and Maheshwari (1)	1982	$O(\log^2(n))$
Nath and Maheshwari (1)	1982	$O(\log^2(n))$
Nath and Maheshwari (2)	1982	$O(\log^3(n))$
Nath and Maheshwari (2)	1982	$O(\log^3(n))$
Kucera	1982	$O(\log n)$
Kucera	1982	$O(\log n)$
Chin et al.	1982	$O(\log^2(n))$
Chin et al.	1982	$O(\log^2(n))$
Hirschberg	1982	$O(\log n)$
Hirschberg	1982	$O(\log n)$
Kucera	1982	$O(\log(n))$
Shiloach, Vishkin	1982	$O(n^1.5 \log n)$
Romani's algorithm	1981	$O(n^{2.51665})$	$O(n^2)$
Coppersmith–Winograd algorithm	1981	$O(n^{2.495548})$	$O(n^2)$
Opheim simplification	1981	$O(n)$	$O(1)$
Dijkstra's algorithm with Fibonacci heap (Johnson 1981; Karlsson & Poblete 1983)	1981	$O(E \log \log L)$	$O(V+L)$
Dixon's algorithm	1981	$O(e^{2 \sqrt{2} \sqrt{n\log n}})$	$O(n+(B/\log B)^2)$
Quadratic sieve	1981	$O(e^{\sqrt{(1+o(1))n \log n}})$ , under assumption about numbers in a sequence behaving randomly in a given range	$O(n+(B/\log B)^2)$
Lin–Kernighan	1981	$O(V^2)$	$O(V)$
Peterson's algorithm	1981	$O(n)$	$O(n)$ total
Gupta-Sproull algorithm	1981	$O(n)$	$O(1)$
Chaitin's Algorithm	1981	$O(n^2)$	$O(n^2)$
Bowyer–Watson algorithm	1981	$O(n \log n)$	$O(n)$
Dekel; Nassimi & Sahni Parallel Implementation	1981	$O(\log^2 V)$	$O(V^2)$
Bowyer–Watson algorithm	1981	$O(n \log n)$	$O(n)$
Sciore	1981	poly-time
Haggkvist and Hell	1981	2 // $O(1)$
Lee et al.	1981	$2n$
Shiloach and Vishkin	1981	$O(n/p log n + log n log p)$ for $p<=n$ $O(log^2(n)/log(p/n) + log n)$ for $p>=n$
Reischuk	1981	$O(\log{n})$
Shiloach, Vishkin	1981	$O(V^3*\log(V)/p)$	can be derived
Dekel; Nassimi & Sahni (1)	1981	$O(\log n)$
Dekel; Nassimi & Sahni (2)	1981	$O(n)$
Dekel; Nassimi & Sahni (3)	1981	$O(n/m + \log m)$
Dekel; Nassimi & Sahni (4)	1981	$O(n^2/m+n^2.61/m^1.61)$
Dekel; Nassimi & Sahni (5)	1981	$O(\log n)$
Dekel; Nassimi & Sahni (6)	1981	$O(n/m + \log n)$
Dekel; Nassimi & Sahni (7)	1981	$O(n^2/m+n^2.61/m^1.61)$
Nath, Maheshwari, Bhatt [modified CONVEXHULL-4]	1981	$O(n/k \log n + \log k \log n)$
Nath, Maheshwari, Bhatt [CONVEXHULL-5]	1981	$O(k \log n)$
Deo and Yoo (1)	1981	$O(n^1.5)$
Deo and Yoo (1)	1981	$O(n^1.5)$
Deo and Yoo (2)	1981	$O(n^2 \log n / p)$
Deo and Yoo (2)	1981	$O(n^2 \log n / p)$
Savage and Ja'Ja'	1981	$O(\log^2(n))$
Savage and Ja'Ja'	1981	$O(\log^2(n))$
Dekel; Nassimi & Sahni	1981	$O(\log^2(n))$
Dekel; Nassimi & Sahni Parallel Implementation	1981	$O(\\log^2 V)$	O(V^2)
Schonhage's algorithm	1980	$O(n^{3\log(52)/\log(110)})$ , approximately $O(n^{2.5218})$	$O(n^2)$
Mukhopadhyay	1980	$O((n + p) \log n)$	$O(p + n)$
Dyer	1980	$O(n)$ using $O(n^2)$ processors	$O(n^2)$
Moravec's algorithm 1980	1980	$O(n^3)$
Boyer-Moore-Horspool (BMH)	1980	$O(mn + s)$	$O(s)$
Micali; Vazirani	1980	$O(E \sqrt{V})$	$O(E)$
Babai	1980	$o(\exp(2n^{1/2}\log^2 n))$	$O(n^2)$
Dynamic 2-d Convex Hull, Overmars and van Leeuwen	1980	O(log^2(n)) per operation, O(n*log^2(n)) total
Babai 1980	1980	\exp(n^{\frac{1}{2} + O(1)})	O(n^2)
odd-even sort - Hsiao and Menon (1)	1980	$O(n/p \log{n/p} + n)$
modified Stone sort - Hsiao and Menon (2)	1980	$O(n/p \log{n/p} + n/p \log^2{p})$
specialized minimum time sort - Hsiao and Menon (3)	1980	$O(n/p \log{n/p})$
sorting on two or more ladders - Chin, Fok	1980	$2n+1$
Chow	1980	$O(\log^2(n))$
Chow	1980	$O(\log^3 n)$
Chow	1980	$O(\log^3 n)$
Bentley–Ottmann algorithm	1979	$O(n \log n + k \log n)$	$O(n)$
Bini's algorithm	1979	$O(n^{2.7799})$	$O(n^2)$
Brélaz (DSatur)	1979	$O(n^2)$	$O(m+n)$
Chvatal greedy heuristic	1979	$O(dn^2)$	$O(dm)$
Fortune and Hopcroft	1979	$O(kn \log\log n + n 3^k)$	$O(n)$
Whitted's algorithm 1979	1979	$O(n^2)$
watershed transformation 1979	1979	$O(n^2)$
Commentz-Walter Algorithm	1979	$O(mn)$	$O(km)$
Ridder's method	1979	$O(n_{max})$	$O(1)$
Weighted incremental algorithm	1979	$O(n)$	$O(1)$
Chan's algorithm Parallel Implementation	1979	$O(\log n)$	$O(1)$ per processor
FCFS	1979	$O(n)$	$O(1)$
SSTF	1979	$O(n \log n)$ with binary tree	$O(n)$
SCAN	1979	$O(n \log n)$	$O(n)$
LOOK	1979	$O(n \log n)$	$O(n)$
C-SCAN	1979	$O(n \log n)$	$O(n)$
C-LOOK	1979	$O(n \log n)$	$O(n)$
Maybeck; Peter S Extended Kalman Filter	1979	$O(n^2 \log^2 n)$	$O(n^2)$
Shamir's scheme	1979	$O(t^2)$ for secret computation (requires polynomial interpolation)	$O(1)$ per person, $O(t^2)$ to figure out secret
Blakley's scheme	1979	$O(t^3)$ for secret computation (requires linear solver)	$O(t)$ per person, $O(t^2)$ to figure out secret
Online 2-d Convex Hull, Preparata	1979	O(logn) per operation, O(n*log(n)) total	O(n)
Nassimi and Sahni	1979	$O(n^0.5)$
Preperata and Vuillemin	1979	$O(\log^2{n})$
Hirschberg et al.	1979	$O(\log^2(n))$
Hirschberg et al.	1979	$O(\log^2(n))$
Hirschberg et al.	1979	$O(\log^2(n))$
Wyllie	1979	$O(\log^2(n))$
Hirschberg, Chandra, Sarwate	1979	$O(\log^2(n))$
Hirschberg, Chandra, Sarwate	1979	$O(\log^2(n))$
Hirschberg, Chandra, Sarwate	1979	$O(\log^2(n))$
Hirschberg, Chandra, Sarwate	1979	$O(\log^2(n))$
Chan's algorithm Parallel Implementation	1979	$O(\\log n)$	O(1) per processor
Pan's algorithm	1978	$O(n^{\log(143640)/\log(70)})$ , approximately $O(n^{2.795})$	$O(n^2)$
Cyrus–Beck	1978	$O(np)$	$O(1)$
Cyrus–Beck	1978	$O(np)$	$O(1)$
Shamos	1978	$O(n \log n)$	$O(\log n)$
Chin	1978	$O(n)$	$O(n)$
Kosaraju's algorithm	1978	$O(V+E)$	$O(V+E)$
Recursive Region Splitting	1978	$O(n^2)$
Diffie–Hellman key exchange	1978	$O(n\cdot \text{mult}(n))$	$O(n)$
Gosper's algorithm	1978	$O((\lambda + \mu) \log(\lambda + \mu) t_f)$	$\Theta(\log(\mu + \lambda))$
Bruun's FFT algorithm	1978	$O(n \log n)$	$O(n)$
9-point FFT	1978	$O(n^3 \log n)$	$O(n^3)$
Salomon (Swath Method)	1978	$O(n \log n)$	$O(n^2)$
Pohlig-Hellman	1978	$O(2^{\sqrt{n}})$	$O(2^{\sqrt{n}})$ (though only for primes)
Pollard's rho algorithm	1978	$O(2^{n/2})$	$O(1)$
Pollard's kangaroo algorithm	1978	$O(2^n)$	$O(1)$
Lewis 1978	1978	O(mn^2)
Rebound sort - Chen, Lum, Tung	1978	$O(n)$
Odd-even transposition sort w/ uniform ladder - Chen, Eswaran, Lum, Tung	1978	$(n+1)/2$
Todd	1978	$2n+\log{n}-1$
Sameh, Kuck (1)	1978	$O(n)$
Reghbati (Arjomandi) and Corneil (1)	1978	T/p+L log(p)+2n
Reghbati (Arjomandi) and Corneil (1)	1978	T/p+L log(p)+2n
Reghbati (Arjomandi) and Corneil (2)	1978	$O(\log^2(n))$
Reghbati (Arjomandi) and Corneil (2)	1978	$O(\log^2(n))$
Reghbati (Arjomandi) and Corneil (2)	1978	$O(\log^2(n))$
Ja'Ja'	1978	$O(\log n \log d)$
Ja'Ja'	1978	$O(\log n \log d)$
Ja'Ja'	1978	$O(\log n \log d)$
Knuth-Morris-Pratt (KMP) algorithm	1977	$O(m+n)$	$O(m)$
Boyer-Moore (BM) algorithm	1977	$O(mn + s)$	$O(s)$
Brute Force	1977	$O(n^3)$	$O(1)$
Grenander	1977	$O(n^2)$	$O(n)$
Faster Brute Force (via x[L:U] = x[L:U-1]+x[U])	1977	$O(n^2)$	$O(1)$
Hunt and Szymanski	1977	$O((n + p) \log n)$	$O(p + n)$
Dijkstra's algorithm with binary heap (Johnson 1977)	1977	$O((E + V) \log V)$	$O(V)$
Blinn–Phong	1977	$O(n^3)$
Hirschberg	1977	$O(rn + n \log n)$	$O(n + p)$
Garsia–Wachs algorithm	1977	$O(n \log n)$	$O(n)$
Weiler–Atherton clipping algorithm	1977	$O(n^2)$	$O(n^2)$
Expectation–maximization (EM) algorithm	1977	$O(n^3)$	$O(n+r)$
Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa	1977	$O(nm)$ per clique	$O(m)$
Catriel Beeri Ronald Fagin John H. Howard	1977	$O(4^n)$
Expectation-Maximization (EM) algorithm	1977	$O(n^3)$	$O(n+r)$
Fagin	1977	exponential	exponential
Parallel bucket-sort - Hirschberg (1)	1977	$O(\log{n})$
Parallel bucket-sort - Hirschberg (1)	1977	$O(\log{n})$
Parallel bucket-sort - Hirschberg (2)	1977	$O(k \log{n})$
Parallel bucket-sort - Hirschberg (2)	1977	$O(k \log{n})$
Preperata (1)	1977	$O(\log{n})$
Preperata (2)	1977	$C/alpha \log{n} + o(\log{n})$
s^2-way merge sort - Thompson and Kung (1)	1977	$O(n^0.5)$
adaptation of Batcher's bitonic merge sort - Thompson and Kung (2)	1977	$O(n^0.5)$
Savage	1977	$O(\log^2(n))$
Savage	1977	$O(\log^2(n))$
Savage	1977	$O(\log^2(n))$
Multigrid	1977
Lawler	1976	$O(mn 3^{n/3}) ~ O(mn(1.445)^n)$	$O(n)$
Lawler	1976	$O((m+n)2^n)$	$O(n)$
Path-based strong components algorithm; Dijkstra	1976	$O(V+E)$	$O(V)$
Cheriton-Tarjan Algorithm	1976	$O(E \log \log V)$	$O(E)$
Rabin' Algorithm	1976	$O(3^k n^2)$	$O(n)$
Bentley; Shamos	1976	$O(kn \log n)$	$O(kn)$
Blinn and Newell	1976	-
Buchberger's algorithm	1976	$O(d^{2^{n+o(1)}})$	$d^{2^{n+o(1)}}$
Rader–Brenner algorithm	1976	$O(n \log n)$	$O(n)$
Tarjan's DFS based algorithm	1976	$O(V+E)$	$O(V)$
Christofides algorithm	1976	$O(V^3)$	$O(V^2)$
McCreight	1976	$O(n)$	$O(n)$
Priority Queue Algorithm	1976	$O(n^2)$	$O(n)$
Lucifer / DES	1976	$O(n)$	$O(n)$
Cheriton-Tarjan (dense)	1976	O(E)	O(E) auxiliary
Cheriton-Tarjan (planar)	1976	O(V)	O(V) auxiliary
Ives' algorithm c	1976	O(1) per permutation	O(n) auxiliary
Aho, Hopcroft, and Ullman [Offline]	1976	O(n+ m*alpha(m + n, n)) where alpha is the inverse Ackermann function	O(n)
Aho, Hopcroft, and Ullman [Static Trees]	1976	O((m+n)*log(log(n)))	O(n*log(log(n)))
Aho, Hopcroft, and Ullman [Linking]	1976	O((m+n)*log(n))	O(n*log(n))
Modified van Leeuwen [Static Trees]	1976	O(n+m*log(log(n)))	O(n)
Modified van Leeuwen [Linking Roots]	1976	O(n+m*log(log(n)))	O(n)
Fredman	1976	O(n^3(log log n/ log n)^{1/3})
Chandra (1)	1976	$O(n^{\log 7}/p)$
Chandra (2)	1976
Chandra	1976	$O(\log^2(n))$
Hirschberg (1)	1976	$O(\log^2(n))$
Hirschberg (2)	1976	$O(\log^2(n))$
Sameh, Chen, Kuck	1976	$O(\log n)$
Melhorn's Approximation algorithm	1975	$O(n)$	$O(n)$
Naive Implementation	1975	$O(kn^2)$	$O(1)$
Chandra	1975	$O(n)$	$O(n)$
Yao's algorithm	1975	$O(E \log \log V)$	$O(E)$
Shamos; Hoey	1975	$O(n \log n)$	$O(n)$
Pollard's rho algorithm	1975	-	$O(n)$
Closed formula	1975	$O(n^6)$	$O(n^2)$
Aho–Corasick (AC) Algorithm	1975	$O(n + m + z)$	$O(km)$
Valiant	1975	$O(n^{\omega} \|G\|)$	$O(n^2)$
Manacher	1975	$O(n)$	$O(n)$
Brute Force	1975	$O(m 2^n)$
Hadlock	1975	$O(n^4)$	$O(n^2)$
Parallel Neighborhood sort - Baudet, Stevenson	1975	$O(n \log{n}/p +n)$
Muller and Preperata	1975	$O(\log{n})$
Drysdale, Young	1975	$O(\log^2{n})$
Csanky	1975
Wagner and Fischer	1974	$O(mn)$	$O(mn)$
Reumann–Witkam	1974	$O(n)$	$O(1)$
Horowitz and Sahni	1974	$O(2^{(n/2)} n)$	$O(2^{n/2})$
Bunch; Hopcroft	1974	$O(n^{2.376})$	$\tilde{O}(n^2)$
Pollard's p − 1 algorithm	1974	$O(B \log(B) \log^2(n))$	$O(n+B)$
Lamport's bakery algorithm	1974	$O(n)$	$O(1)$ per process, $O(n)$ total
Rosenkrantz; D. J.; Stearns; R. E.; Lewis; P. M.	1974	$O(V^2)$	$O(1)$
S.L. Horowitz and T. Pavlidis - directed split and merge	1974	$O(n^2)$
Fleury's algorithm + Tarjan	1974	$O(E^2)$	$O(E)$
Sutherland–Hodgman algorithm	1974	$O(n^2)$	$O(n)$
GLR parser	1974	$O(n^3)$	$O(n^3)$
Discrete Cosine Transform	1974	$O(n \log n)$	$O(n)$
Puterman Modified Policy Iteration (MPI)	1974	$O(n^3)$	$O(n)$
Faaland	1973	$O(n' t)$	$O(t)$
Cook–Torrance (microfacets)	1973	$O(n^2)$
Satia & Lave; 1973;	1973
Hopcroft–Karp algorithm	1973	$O(V^{0.5} E)$	$O(V)$
Brent's algorithm	1973	$O((\lambda + \mu) t_f)$	$O(1)$
Bron–Kerbosch algorithm	1973	$O(3^{n/3})$	$O(n^2)$
Akkoyunlu; E. A.	1973	$O(3^{n/3})$	$O(n^2)$
Naive	1973	$O(n^2)$	$O(n)$
Weiner's algorithm	1973	$O(n)$	$O(n)$
Kleitman–Wang Algorithm	1973	$O(n)$	$O(n)$
O'Neil 1973	1973	O(n^3)
Anderson–Björck algorithm	1973	O(n_max)	O(1)
Brent-Dekker Method	1973	O(n_max)	O(1)
Buzbee [MD]	1973
Ramer–Douglas–Peucker algorithm	1972	$O(n^2)$	$O(n)$
Tarjan's strongly connected components algorithm	1972	$O(V+E)$	$O(V)$
Odd Even Sort Parallel Implementation	1972	$O(n^2)$	$O(1)$
Xu; Renio	1972	$O(2^n)$
Xu; Renio	1972	$O(2^n)$
Xu; Renio	1972	$O(2^n)$
Xu; Renio	1972	$O(2^n)$
Xu; Renio	1972	$O(2^n)$
Xu; Renio	1972	$O(2^n)$
Xu; Renio	1972	$O(2^n)$
Aho, Garey & Ullman	1972	$O(n^{\omega})$	$O(n^2)$
Dijkstra	1972	$O(n!)$	$O(n)$
Dijkstra	1972	$O(n!)$	$O(n)$
Shellsort on sorting networks- Pratt	1972	$O(\log^2{n})$
Aasen's method	1971	$O(n^3)$	$O(n^2)$
Shell Sort (Pratt)	1971	$O(n \log^2 n)$	$O(1)$
Munro’s algorithm	1971	$O(E + V \log V)$	$O(V)$
Schönhage–Strassen algorithm	1971	$O(n \log n \log\log n)$	$O(n)$ auxiliary
Phong	1971	$O(n^3)$
Hu–Tucker algorithm	1971	$O(n \log n)$	$O(n)$
Knuth's DP algorithm	1971	$O(n^2)$	$O(n^2)$
Hopcroft's algorithm	1971	$O(kn \log n)$	$O(kn)$
Baby-step Giant-step	1971	$O(2^{\sqrt{n}})$	$O(2^{\sqrt{n}})$
Illinois Algorithm	1971	O(n_max)	O(1)
Batcher's bitonic sort using perfect shuffle - Stone	1971	$O(\log^2{n})$
Van Voorhis	1971	$O(\log^2{n})$
Schönhage–Strassen	1971
Kuck, Sameh (Jacobi's method)	1971	$O( n^3 / p + n^2 / p^{1/2} + n )$
Kuck, Sameh (Householder's method)	1971	$O( n^3 / p )$
Kuck, Sameh (QR algorithm)	1971	$O( n^3 / p + n^2 )$
Sameh (Jacobi)	1971	$O( ( n^2 / p + \log(n) ) n \log(n) )$
Bjorck-Pereyra	1970	$O(n^2)$	$O(n^2)$
Paul Purdom	1970	$O(V^2+VE)$	$O(V^2)$
Knuth–Bendix algorithm	1970	$O(1.5^n n^2 \log n)$	$O(ng)$
5-point cyclic reduction	1970	$O(n^3 \log n)$	$O(n^3)$
Sethi–Ullman Algorithm	1970	$O(n)$	$O(1)$
Bjorck	1970	$O(n^2)$	$O(n)$
Method of Four Russians	1970	O(n^3/(log n)^2)
Chand-Kapur, Gift Wrapping	1970	O(n*f_1)
Bayer, McCreight B-Tree	1970	O(b*log(n)/log(b))	O(b)
Bayer, McCreight B-Tree	1970	O(b*log(n)/log(b))	O(b)
Bayer, McCreight B-Tree	1970	O(b*log(n)/log(b))	O(1)
Strassen's algorithm	1969	$O(n^{\log(7)/\log(2)})$ , approximately $O(n^{2.807})$	$O(n^2)$
Bareiss Algorithm	1969	$O(n^2)$	$O(n^2)$
Toom-3	1969	$O(n^{1.46})$	$O(n)$
Lang simplification	1969	$O(n)$	$O(1)$
Bergland; Glenn radix-8 algorithm	1969	$O(n \log n)$	$O(n)$
9-point ADI iteration + smooth guess	1969	$O(n^3 \log n)$	$O(n^3)$
Berlekamp–Massey algorithm	1969	$O(n^2)$	$O(n)$
Fellegi & Sunter Model	1969	$O(n^3 k)$	$O(k)$
Zakai	1969	$O(n^3)$
Dial's Algorithm	1969	O(E+LV)	O(V+L)
Cannon (Classical 2D)	1969	n^3/p + 2sqrt(p) * (t_s + n^2/p t_w)
A* Algorithm	1968	$O(b^d)$	$O(b^d)$
Bitonic Merge Sort Parallel Implementation	1968	$O(\log^2 n)$	$O(1)$
Appel's algorithm 1968	1968	$O(n^2)$
Yavne Split Radix FFT algorithm	1968	$O(n \log n)$	$O(n)$
Cocke–Younger–Kasami algorithm	1968	$O(n^3 \|G\|)$	$O(n^2)$
Earley parser	1968	$O(n^3)$	$O(n^2)$
Bareiss algorithm	1968	$O(n^5 L^2 (\log(n)^2 + L^2))$	$O(n^2(n\log(n)+nL))$
Bareiss algorithm with fast multiplication	1968	$O(n^4 L (\log(n) + L) \log(\log(n) + L))$	$O(n^2(n\log(n)+nL))$
odd-even sort - Batcher	1968	$O(\log^2{n})$
Bitonic sort - Batcher	1968	$O(\log^2{n})$
Pease	1968	$O(\log n)$
Cohen–Sutherland	1967	$O(n)$	$O(1)$
Floyd's tortoise and hare algorithm	1967	$O((\lambda + \mu) t_f)$	$O(1)$
Brute force algorithm	1967	$O(n^2 2^n p \log p)$	$O(n2^n)$
Tradu; Mirc	1967	$O(2^n)$
Kushner non-linear filter	1967	$O(n^3)$	$O(n^2)$
Nordbeck and Rystedt (Grid Method)	1967	$O(n)$	$O(n)$
Nordbeck and Rystedt (Sum of area)	1967	$O(n)$	$O(1)$
Nordbeck and Rystedt (Orientation)	1967	$O(n)$	$O(1)$
Binary GCD algorithm	1967	$O(n^2)$	$O(n)$
Langdon	1967	O(n) per permutation	O(1) auxiliary
Ord-Smith	1967	O(1) per permutation	O(n) auxiliary
Gentleman; Morven and Gordon Sande radix-4 algorithm	1966	$O(n \log n)$	$O(n)$
Banker's Algorithm	1966	$O(mn^2)$	$O(mn)$
Resource hierarchy solution	1965	$O(2^n)$	$O(n)$
Arbitrator solution	1965	$O(2^n)$	$O(1)$
Edmonds	1965	$O(mn^2)$	$O(mn^2)$
Naive algorithm	1965	$O(n^2)$	$O(1)$
Cooley–Tukey algorithm	1965	$O(n \log n)$	$O(n)$
Bresenham's line algorithm	1965	$O(n)$	$O(1)$
9-point ADI iteration	1965	$O(n^2 \log n)$	$O(n^2)$
5-point FFT	1965	$O(n^2 \log n)$	$O(n^2)$
5-point FFT	1965	$O(n^2 \log n)$	$O(n^2)$
5-point FFT	1965	$O(n^2 \log n)$	$O(n^2)$
5-point FFT	1965	$O(n^2 \log n)$	$O(n^2)$
9-point ADI iteration	1965	$O(n^3 \log n)$	$O(n^3)$
5-point FFT	1965	$O(n^3 \log n)$	$O(n^3)$
Naive Solution	1965	$2^{O(n)}$	$O(n)$
Chu-Liu-Edmonds Algorithm	1965	O(EV)	O(E+V)
Heap Sort	1964	$O(n \log n)$	$O(1)$
Bitap algorithm	1964	$O(mn)$	$O(m)$
Durstenfeld's Algorithm 235	1964	$O(n)$	$O(1)$
Lemke–Howson algorithm	1964	$2^{O(n+m)}$	$O(mn)$
9-point Tensor product	1964	$O(n^3)$	$O(n^2)$
9-point Tensor product	1964	$O(n^4)$	$O(n^3)$
Sorting based [Merge Sort] + sequential pass	1964	$O(n \log n)$	$O(n)$
Prim's algorithm + binary heap	1964	O(ElogV)	O(V) auxiliary
Steinhaus–Johnson–Trotter algorithm	1963	$O(n \cdot n!)$	$O(1)$
Heap's algorithm	1963	$O(n \cdot n!)$	$O(n)$
Brzozowski's algorithm	1963	$O(2^n)$	$O(2^n)$
Karatsuba	1963
Toom–Cook	1963
Selection Sort	1962	$O(n^2)$	$O(1)$
Karatsuba Algorithm	1962	$O(n^{1.58})$	$O(n)$
Floyd–Warshall algorithm	1962	$O(n^3)$	$O(n^2)$
Bresenham Algorithm	1962	$O(n)$	$O(1)$
QR algorithm	1962	$O(n^2)$	$O(n^2)$
QR algorithm	1962	$O(n^2)$	$O(n^2)$
Welford's Online algorithm	1962	$O(n)$	$O(1)$
Kahn's algorithm	1962	$O(V+E)$	$O(V)$
Held–Karp algorithm	1962	$O(V^2 2^V)$	$O(V 2^V)$
Gale–Shapley algorithm	1962	$O(n^2)$	$O(n)$
Ray casting algorithm Shimrat; M	1962	$O(n)$	$O(1)$
AVL Tree	1962	O(logn)	O(1)
AVL Tree	1962	O(logn)	O(1)
AVL Tree	1962	O(logn)	O(1)
Kahn	1962	10(M + M X E + 4A + 6E)*V	O(V^2)
Hoare's Selection Algorithm (QuickSelect)	1961	$O(n^2)$	$O(1)$
Quick Sort	1961	$O(n^2)$	$O(\log n)$
Davis-Putnam-Logemann-Loveland Algorithm (DPLL)	1961	O(2^n)	O(n)
Wells	1961	O(1) per permutation	O(n) auxiliary
Miller-Tucker-Zemlin (MTZ) formulation	1960	$\text{exp}(V)$	$O(V^4)$
Shell Sort (Frank & Lazarus)	1960	$O(n^{1.5})$	$O(1)$
Bellman–Ford algorithm (Dantzig 1960)	1960	$O(V^2 \log V)$	$O(E)$
Dijkstra's algorithm with list (Whiting & Hillier 1960)	1960	$O(V^2)$	$O(V)$
Nested loop join	1960	$O(nm)$	$O(1)$
Sort merge join	1960	$O(n \log n + m \log m)$	$O(n+m)$
Hash join	1960	$O(n+m)$	$O(n+m)$
Kalman Filter	1960	$O(n^3)$	$O(n^2)$
Stratonovich	1960	$O(n^3)$
Howard Policy Iteration (PI)	1960	$O(n^3)$	$O(n)$
Rabin–Scott powerset construction	1959	$O(2^n)$	$O(1)$
Shell Sort (Shell)	1959	$O(n^2)$	$O(1)$
Bellman–Ford algorithm (Shimbel 1955; Bellman 1958; Moore 1959)	1959	$O(VE)$	$O(V)$
Greedy Best-First Search	1959	$O(b^d)$	$O(b^d)$
DP algorithm (Gilbert, Moore)	1959	$O(n^3)$	$O(n^2)$
Stratonovich	1959	$O(n^3)$
Prim's algorithm + adjacency matrix searching	1957	$O(V^2)$	$O(V)$
Bellman Value Iteration (VI)	1957	$O(2^n)$	$O(n)$
Bubble Sort	1956	$O(n^2)$	$O(1)$
Bellman dynamic programming algorithm	1956	$O(nt)$	$O(t)$
Kruskal's algorithm	1956	$O(E \log E)$	$O(E)$
Bellman–Ford algorithm (Ford 1956)	1956	$O(V^2 EL)$	$O(E)$
Dürer rendering algorithm	1956	$O(n^2)$
Ford–Fulkerson algorithm	1956	$O(VE)$	$O(E)$
Tompkins–Paige algorithm	1956	$O(n \cdot n!)$	$O(n)$
Muller's method	1956	$O(n_{max})$	$O(1)$
Moore's algorithm	1956	$O(n^2 k)$	$O(n)$
9-point SOR iteration	1956	$O(n^3)$	$O(n^2)$
9-point SOR iteration	1956	$O(n^4)$	$O(n^3)$
Hungarian algorithm	1955	$O(n^4)$	$O(n^2)$
5-point ADI iteration	1955	$O(n^2 \log^2 n)$	$O(n^2)$
5-point ADI iteration	1955	$O(n^3 \log^2 n)$	$O(n^3)$
QR Matrix Decomposition	1955	$O(n^2)$	$O(n^2)$
Counting Sort	1954	$O(n+k)$	$O(n+k)$
Dantzig-Fulkerson-Johnson (DFJ) formulation	1954	$O(\text{exp}(V))$	$O(V^2 2^V)$
5-point SOR iteration	1954	$O(n^3 \log n)$	$O(n^2)$
5-point SOR iteration	1954	$O(n^4 \log n)$	$O(n^3)$
Dynamic Programming Algorithm (S. S. Godbole)	1953	$O(n^3)$	$O(n^2)$
Dynamic Programming	1953	$O(n^2)$	$O(n)$
Dynamic Programming	1953	$O(Sn)$	$O(Sn)$
Shimbel Algorithm	1953	$O(n^4)$	$O(n^2)$
Dynamic Programming	1953	$O(n^2)$	$O(n^2)$
$O(n^3)$ Dynamic Programming	1953	$O(n^3)$	$O(n^2)$
$O(n^2)$ Dynamic Programming	1953	$O(n^2)$	$O(n)$
$O(n\log n)$ Dynamic Programming	1953	$O(n \log n)$	$O(n)$
LOBPCG algorithm	1948	$O(n^2)$	$O(n)$
LOBPCG algorithm	1948	$O(n^2)$	$O(n)$
LOBPCG algorithm	1948	$O(n^2)$	$O(n)$
Levinson–Durbin recursion	1947	$O(n^2)$	$O(n^2)$
Merge Sort	1945	$O(n \log n)$	$O(n)$
5-point star Cramer's rule	1945	$O(4^{n^2})$	$O(4^{(n^2)})$ for sure, $O(n^2)$ possibly (if super conservative)
5-point Gauss elimination	1945	$O(n^4)$	$O(n^4)$
5-point Gauss Seidel iteration	1945	$O(n^4 \log n)$	$O(n^2)$
5-point star Cramer's rule	1945	$O(5^{n^3})$	$O(5^{(n^3)})$ for sure, $O(n^3)$ possibly (if super conservative)
5-point Gauss elimination	1945	$O(n^7)$	$O(n^6)$
5-point Gauss Seidel iteration	1945	$O(n^5 \log n)$	$O(n^3)$
LU Matrix Decomposition	1945	$O(n^3)$	$O(n^2)$
Crout algorithm	1941	$O(n^3)$	$\tilde{O}(1)$
Steffensen's method	1940()	O(n_max)	O(1)
Inverse quadratic interpolation	1940()	O(n_max)	O(1)
Insertion Sort	1940	$O(n^2)$	$O(1)$
Bucket Sort	1940	$O(n^2)$	$O(n)$
Radix Sort	1940	$O(wn)$	$O(w+n)$
Naive Selection	1940	$O(n \log n)$	$O(1)$
Brute Force	1940	$O(4^n)$	$O(n)$
Naive algorithm	1940	$O(n^3)$	$O(1)$
Cholesky	1940	$O(n^3)$	$O(n^2)$
Naive	1940	$O(n^2)$	$O(1)$
Naïve string-search algorithm	1940	$O(m(n-m+1))$	$O(1)$
Long Multiplication	1940	$O(n^2)$	$O(n)$
Brute Force	1940	$O(n 2^n)$	$O(n)$
Brute Force	1940	$O(S^n)$	$O(n)$
Insertion Sort	1940	$O(n^2)$	$O(1)$
Hashing	1940	$O(n)$	$O(n)$
Wheel factorization	1940	$O(2^{n/2})$	$O(n)$
Euler's factorization method	1940	$O(2^{n/2})$	$O(n)$
Special number field sieve	1940	$O(\exp((1+o(1))(32n/9)^{1/3}(log n)^{2/3})$ , under assumption about numbers in a sequence behaving randomly in a given range	$O(\Gamma n^{4/3} \log n)$
String-Matching with Finite Automata	1940	$O(mn)$	$O(m)$
Naive Implementation	1940	$O(n!)$	$O(n^2)$
Naive algorithm	1940	$O(mn)$	$O(1)$
Naive algorithm	1940	$O(4^n/n^{3/2})$	$O(1)$
Naive algorithm	1940	$O(n)$	$O(1)$
Digital Differential Analyzer	1940	$O(n)$	$O(1)$
Rayleigh quotient iteration	1940	$O(n^2)$	$O(n^2)$
Rayleigh quotient iteration	1940	$O(n^2)$	$O(n^2)$
Laguerre iteration	1940	$O(n^2)$	$O(n^2)$
Newton's method	1940	$O(n_{max})$	$O(1)$
Secant method	1940	$O(n_{max})$	$O(1)$
Haselgrove-Leech-Trotter (HLT) algorithm	1940	$O(2^n)$	$O(ng)$
Naive solution	1940	$O(N)$	$O(n)$
Naïve algorithm	1940	$O(n)$	$O(1)$
Two-pass algorithm	1940	$O(n)$	$O(1)$
Naive algorithm	1940	$O(n 2^n)$	$O(n)$
Brute force (backtracking search)	1940	$O(2^k n^{O(1)})$	$O(k)$
Brute force	1940	$O(n 2^n)$	$O(n2^n)$
Schubert's algorithm/Kronecker's method	1940	$O(p^{n/2 + O(\log n)})$	$O(n)$
Naive	1940	$O(n^3)$	$O(1)$
Naive	1940	$O(m)$	$O(n)$
Iterative naive	1940	$O(f_{bin}(\sigma-1, n, d))$ where $f_{bin}(x, y, z) = \sum_{i=0}^z \binom{y}{i}x^i$	$O(n)$
Trial Multiplication	1940	$O(2^n)$	$O(1)$
Naive solution	1940	$O(n f_{bin}(\sigma-1, k, d))$ where $f_{bin}(x, y, z) = \sum_{i=0}^z \binom{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 \binom{y}{i}x^i$
Naive solution	1940	$O(k(n-k)^2)$	$O(\max(n, \sigma^k))$
Lehmer's GCD algorithm	1940	$O(n^2)$	$O(n)$
Brute force algorithm	1940	$O(2^n)$	$O(n)$
Fixed priority shortest job first	1940	$O(n \log n)$	$O(n+k)$
Priority scheduling	1940	$O(n)$	$O(n+k)$
Shortest remaining time first	1940	$O(n)$	$O(n+k)$
First come, first served	1940	$O(n)$	$O(n+k)$
Round-robin scheduling	1940	$O(n)$	$O(n+k)$
Multilevel queue scheduling	1940	$O(n)$	$O(n+k)$
The theoretically optimal page replacement algorithm	1940	$O(n^2)$	$O(k)$
Not recently used	1940	$O(nk)$	$O(k)$
First-in, first-out	1940	$O(nk)$	$O(k)$
Second-chance	1940	$O(nk)$	$O(k)$
Clock	1940	$O(nk)$	$O(k)$
Least recently used	1940	$O(nk)$	$O(k)$
Random	1940	$O(n)$	$O(k)$
Not frequently used (NFU)	1940	$O(nk)$	$O(k)$
Aging	1940	$O(nk)$	$O(k)$
ITP Method	1940	O(n_0+log((b-a)/epsilon))	O(1)
Exhaustive search	1940	O(C(n, k)) (i.e. (n, k) binomial coefficient)	O(k) auxiliary
Fisher–Yates/Knuth shuffle	1938	$O(n^2)$	$O(n)$
Todd–Coxeter algorithm	1936	$O(2^n)$	$O(gkc)$
Folded spectrum method	1934	$O(n^2)$	$O(n)$
Folded spectrum method	1934	$O(n^2)$	$O(n)$
Folded spectrum method	1934	$O(n^2)$	$O(n)$
Naive algorithm	1934	$O(n^4)$	$O(n)$
Continued fraction factorization (CFRAC)	1931	$O(e^{\sqrt{2n\log n}})$	$O(n+(B/\log B)^2)$
Power Iteration	1929	$O(n^2)$	$O(n)$
Borůvka's algorithm	1926	$O(E \log V)$	$O(V)$
Inverse iteration	1921	$O(n^2)$	$O(n^2)$
Inverse iteration	1921	$O(n^2)$	$O(n^2)$
Inverse iteration	1921	$O(n^2)$	$O(n^2)$
Fermat's factorization method	1894	$O(2^n)$	$O(n)$
Radix sorting method	1887	$O(n)$	$O(n)$
Iteration based	1883	$O(2^n)$	$O(n)$
Recursion based	1883	$O(2^n)$	$O(n \log n)$
Non-recursion based	1883	$O(2^n)$	$O(n)$
Gray-code based	1883	$O(2^n)$	$O(n)$
Doolittle Algorithm	1878	$O(n^3)$	$\tilde{O}(1)$
Method of determinants	1874	$O(n!)$
Method of determinants	1874	$O(n!)$
Gunther Determinants solution	1874	$O(n!)$	$O(n!)$
Gunther Determinants solution	1874	$O(n!)$	$O(n!)$
Hierholzer's algorithm	1873	$O(E)$	$O(E)$
Brute-force search	1852	$O((m+n) 3^n)$	$O(n)$
Brute force	1852	$O((m+n) 4^n)$	$O(n)$
Naive + 1 queen per row restriction	1850	$O(n!)$	$O(n)$
Naive + 1 queen per row restriction	1850	$O(n!)$	$O(n)$
Naive Algorithm	1848	$O(n^n)$	$O(n)$
Naive Algorithm	1848	$O(n^n)$	$O(n)$
Jacobi eigenvalue algorithm	1846	$O(n^2)$	$O(n^2)$
Jacobi eigenvalue algorithm	1846	$O(n^2)$	$O(n^2)$
Bisection method	1820	$O(n_{max})$	$O(1)$
False position method	1690	$O(n_{max})$	$O(1)$
Newton–Raphson algorithm	1685	$O(n^3)$	$O(n+r^2)$
Newton's method	1669	$O(n_{max})$	$O(1)$
Trial division	1202	$O(2^{n/2})$	$O(n)$
Gaussian-Jordan Elimination	-150	$O(n^3)$	$O(n^2)$
Gaussian-Jordan Elimination	-150	$O(n^3)$	$O(n^2)$
Gaussian-Jordan Elimination	-150	$O(n^3)$	$O(n^2)$
Gaussian-Jordan Elimination	-150	$O(n^3)$	$O(n^2)$
Gaussian-Jordan Elimination	-150	$O(n^3)$	$O(n^2)$
Gaussian Elimination	-150	$O(n^3)$	$O(n^2)$
Bisection method	-150	$O(n_{max})$	$O(1)$
Gaussian elimination	-150	$O(n^3)$	$O(n^2)$
Regula Falsi method	-200	$O(n_{max})$	$O(1)$
Euclid's algorithm	-300	$O(n^2)$	$O(n)$
Secant method	-1400	$O(n_{max})$	$O(1)$
Exhaustive search	-	$O(d*n^k)$	O(k) auxiliary
(many more...)

Download

Algorithms Table

Domains

Families

Variations

Columns