Editing Time complexity (section)

== Table of common time complexities ==
{{Further|Computational complexity of mathematical operations}}
The following table summarizes some classes of commonly encountered time complexities. In the table, {{math|1=poly(''x'') = ''x''<sup>''O''(1)</sup>}}, i.e., polynomial in&nbsp;''x''.

{| class="wikitable sortable"
|-
! Name !! [[Complexity class]] !! Time complexity {{nowrap|({{math|''O''(''n'')}})}} !! Examples of running times !! Example algorithms
|-
| constant time || || <math>O(1)</math> || 10 || Finding the median value in a sorted [[array data structure|array]] of numbers. Calculating  {{math|(−1){{sup|''n''}}}}.
|-
| [[inverse Ackermann function|inverse Ackermann]] time || || <math>O\bigl(\alpha(n)\bigr)</math> || || [[Amortized time]] per operation using a [[disjoint set data structure|disjoint set]]
|-
| [[iterated logarithm]]ic time || || <math>O(\log^*n)</math> || || [[Cole-Vishkin algorithm|Distributed coloring of cycles]]
|-
| log-logarithmic || || <math>O(\log\log n)</math> || || Amortized time per operation using a bounded [[priority queue]]<ref>{{Cite journal|first1=Kurt |last1=Mehlhorn |author1-link=Kurt Mehlhorn|first2=Stefan |last2=Naher|year=1990|title=Bounded ordered dictionaries in {{math|''O''(log log ''N'')}} time and {{math|''O''(''n'')}} space|journal=[[Information Processing Letters]]|doi=10.1016/0020-0190(90)90022-P|volume=35|issue=4|pages=183–189}}</ref>
|-
| logarithmic time || [[DLOGTIME]] || <math>O(\log n)</math> || <math>\log n</math>, <math>\log (n^2)</math> || [[Binary search]]
|-
| polylogarithmic time || || <math>\textsf{poly}(\log n)</math> || <math>(\log n)^2</math> ||
|-
| fractional power || || <math>O(n^c)</math> where <math>0<c<1</math> || <math>n^{\frac{1}{2}}</math>, <math>n^{\frac{2}{3}}</math> || [[Range searching]] in a [[k-d tree|''k''-d tree]]
|-
| linear time || || <math>O(n)</math> || {{mvar|n}}, <math>2n+5</math> || Finding the smallest or largest item in an unsorted [[array data structure|array]]. [[Kadane's algorithm]]. [[Linear search]].
|-
| "n log-star n" time || || <math>O(n\log^*n)</math> || || [[Raimund Seidel|Seidel]]'s [[polygon triangulation]] algorithm.
|-
| linearithmic time || || <math>O(n\log n)</math> || <math>n\log n</math>, <math>\log n!</math> || Fastest possible [[comparison sort]]. [[Fast Fourier transform]].
|-
| quasilinear time || || <math>n\textsf{poly}(\log n)</math> || <math>n\log^2 n</math> || [[Polynomial evaluation#Multipoint evaluation|Multipoint polynomial evaluation]]
|-
| quadratic time || || <math>O(n^2)</math> || <math>n^2</math> || [[Bubble sort]]. [[Insertion sort]]. [[Convolution theorem|Direct convolution]]
|-
| cubic time || || <math>O(n^3)</math> || <math>n^3</math> || Naive multiplication of two <math>n\times n</math> matrices. Calculating [[partial correlation]].
|-
| polynomial time || [[P (complexity)|P]] || <math>2^{O(\log n)}=\textsf{poly}(n)</math> || <math>n^2+n</math>, <math>n^{10}</math> || [[Karmarkar's algorithm]] for [[linear programming]]. [[AKS primality test]]<ref name="tao-aks">{{cite book|title=An epsilon of room, II: Pages from year three of a mathematical blog|last=Tao|first=Terence|publisher=American Mathematical Society|year=2010|isbn=978-0-8218-5280-4|series=Graduate Studies in Mathematics|volume=117|location=Providence, RI|pages=82–86|contribution=1.11 The AKS primality test|doi=10.1090/gsm/117|mr=2780010|author-link=Terence Tao|contribution-url=https://terrytao.wordpress.com/2009/08/11/the-aks-primality-test/}}</ref><ref>{{cite journal | last1 = Lenstra | first1 = H. W. Jr. | author1-link = Hendrik Lenstra | last2 = Pomerance | first2 = Carl | author2-link = Carl Pomerance | doi = 10.4171/JEMS/861 | issue = 4 | journal = [[Journal of the European Mathematical Society]] | mr = 3941463 | pages = 1229–1269 | title = Primality testing with Gaussian periods | url = https://math.dartmouth.edu/~carlp/aks111216.pdf | volume = 21 | year = 2019| hdl = 21.11116/0000-0005-717D-0 | s2cid = 127807021 }}</ref>
|-
| quasi-polynomial time || QP || <math>2^{\textsf{poly}(\log n)}</math> || <math>n^{\log \log n}</math>, <math>n^{\log n}</math> || Best-known {{math|''O''(log{{sup|2}}''n'')}}-[[approximation algorithm]] for the directed [[Steiner tree problem]], best known [[parity game]] solver,<ref>{{cite book |author = Calude, Cristian S. and Jain, Sanjay and Khoussainov, Bakhadyr and Li, Wei and Stephan, Frank| title = Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing| chapter = Deciding parity games in quasipolynomial time| date = 2017| isbn = 9781450345286| publisher = Association for Computing Machinery| chapter-url = https://doi.org/10.1145/3055399.3055409| doi = 10.1145/3055399.3055409 | pages = 252–263| hdl = 2292/31757| s2cid = 30338402}}</ref> best known [[graph isomorphism]] algorithm
|-
| sub-exponential time<br />(first definition) || SUBEXP || <math>O(2^{n^\epsilon})</math> for all <math>0<\epsilon <1</math> ||  || Contains [[Bounded-error probabilistic polynomial|BPP]] unless EXPTIME (see below) equals [[Arthur–Merlin protocol#MA|MA]].<ref name="bpp" />
|-
| sub-exponential time<br />(second definition) || || <math>2^{o(n)}</math> || <math>2^{\sqrt[3]{n}}</math> ||[[General number field sieve|Best classical algorithm]] for [[integer factorization]]
formerly-best algorithm for [[graph isomorphism problem|graph isomorphism]]
|-
| exponential time<br />(with linear exponent) || [[E (complexity)|E]] || <math>2^{O(n)}</math> || <math>1.1^n</math>, <math>10^n</math> || Solving the [[traveling salesman problem]] using [[dynamic programming]]
|-
| factorial time || || <math>O(n)! = 2^{O(n \log n)}
 </math> || <math>n!, n^n, 2^{n \log n}</math> || Solving the [[Travelling salesman problem|traveling salesman problem]] via [[brute-force search]]
|-
| exponential time || [[EXPTIME]] || <math>2^{\textsf{poly}(n)}</math> || <math>2^n</math>, <math>2^{n^2}</math> || Solving [[matrix chain multiplication]] via [[brute-force search]]
|-
| double exponential time || [[2-EXPTIME]] || <math>2^{2^{\textsf{poly}(n)}}</math> || <math>2^{2^n}</math> || Deciding the truth of a given statement in [[Presburger arithmetic]]
|}