Editing Time complexity

{{Short description|Estimate of time taken for running an algorithm}}
{{Redirect-distinguish|Running time|Running Time (film)}}
[[File:comparison computational complexity.svg|thumb|Graphs of functions commonly used in the [[analysis of algorithms]], showing the number of operations ''N'' as the result of input size ''n'' for each function]]

In [[theoretical computer science]], the '''time complexity''' is the [[computational complexity]] that describes the amount of computer time it takes to run an [[algorithm]]. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a [[constant factor]].

Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the [[Worst-case complexity|worst-case time complexity]], which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the [[average-case complexity]], which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally expressed as a [[Function (mathematics)|function]] of the size of the input.<ref name="Sipser" />{{RP|226}} Since this function is generally difficult to compute exactly, and the running time for small inputs is usually not consequential, one commonly focuses on the behavior of the complexity when the input size increases—that is, the [[asymptotic analysis|asymptotic behavior]] of the complexity. Therefore, the time complexity is commonly expressed using [[big O notation]], typically {{nowrap|<math>O(n)</math>,}} {{nowrap|<math>O(n\log n)</math>,}} {{nowrap|<math>O(n^\alpha)</math>,}} {{nowrap|<math>O(2^n)</math>,}} etc., where {{mvar|n}} is the size in units of [[bit]]s needed to represent the input.

Algorithmic complexities are classified according to the type of function appearing in the big O notation. For example, an algorithm with time complexity <math>O(n)</math> is a ''linear time algorithm'' and an algorithm with time complexity <math>O(n^\alpha)</math> for some constant <math>\alpha > 0</math> is a ''polynomial time algorithm''.

== 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]]
|}

== Constant time ==
{{redirect|Constant time|programming technique to avoid a timing attack|Timing attack#Avoidance}}

An algorithm is said to be '''constant time''' (also written as <math display="inline">O(1)</math> time) if the value of <math display="inline">T(n)</math> (the complexity of the algorithm)  is bounded by a value that does not depend on the size of the input. For example, accessing any single element in an [[array data structure|array]] takes constant time as only one [[Instruction (computer science)|operation]] has to be performed to locate it. In a similar manner, finding the minimal value in an array sorted in ascending order; it is the first element. However, finding the minimal value in an unordered array is not a constant time operation as scanning over each [[element (math)|element]] in the array is needed in order to determine the minimal value. Hence it is a linear time operation, taking <math display="inline">O(n)</math> time. If the number of elements is known in advance and does not change, however, such an algorithm can still be said to run in constant time.

Despite the name "constant time", the running time does not have to be independent of the problem size, but an upper bound for the running time has to be independent of the problem size. For example, the task "exchange the values of {{mvar|a}} and {{mvar|b}} if necessary so that <math display="inline">a \le b</math>" is called constant time even though the time may depend on whether or not it is already true that <math display="inline">a \le b</math>. However, there is some constant {{mvar|t}} such that the time required is always ''at most'' {{mvar|t}}.

== Logarithmic time ==
{{Further|Logarithmic growth}}
An algorithm is said to take '''logarithmic time''' when <math>T(n) = O(\log n)</math>.  Since <math>\log_a n</math> and <math>\log_b n</math> are related by a [[Logarithmic identities#Changing the base|constant multiplier]], and such a [[Big O notation#Multiplication by a constant|multiplier is irrelevant]] to big O classification, the standard usage for logarithmic-time algorithms is <math>O(\log n)</math> regardless of the base of the logarithm appearing in the expression of {{mvar|T}}.

Algorithms taking logarithmic time are commonly found in operations on [[binary tree]]s or when using [[binary search]].

An <math>O(\log n)</math> algorithm is considered highly efficient, as the ratio of the number of operations to the size of the input decreases and tends to zero when {{mvar|n}} increases. An algorithm that must access all elements of its input cannot take logarithmic time, as the time taken for reading an input of size {{mvar|n}} is of the order of {{mvar|n}}.

An example of logarithmic time is given by dictionary search. Consider a [[Dictionary (data structure)|dictionary]] {{math|''D''}} which contains {{mvar|n}} entries, sorted in [[alphabetical order]]. We suppose that, for <math>1 \le k \le n</math>, one may access the {{mvar|k}}th entry of the dictionary in a constant time. Let <math>D(k)</math> denote this {{mvar|k}}th entry. Under these hypotheses, the test to see if a word {{mvar|w}} is in the dictionary may be done in logarithmic time: consider <math>D\left(\left\lfloor \frac{n}{2} \right\rfloor\right)</math>, where <math>\lfloor\;\rfloor</math> denotes the [[floor function]]. If <math>w = D\left(\left\lfloor \frac{n}{2} \right\rfloor\right)</math>--that is to say, the word {{mvar|w}} is exactly in the middle of the dictionary--then we are done. Else, if <math>w < D\left(\left\lfloor \frac{n}{2} \right\rfloor\right)</math>--i.e., if the word {{mvar|w}} comes earlier in alphabetical order than the middle word of the whole dictionary--we continue the search in the same way in the left (i.e. earlier) half of the dictionary, and then again repeatedly until the correct word is found. Otherwise, if it comes after the middle word, continue similarly with the right half of the dictionary. This algorithm is similar to the method often used to find an entry in a paper dictionary. As a result, the search space within the dictionary decreases as the algorithm gets closer to the target word.

== Polylogarithmic time ==
An algorithm is said to run in '''[[polylogarithmic function|polylogarithmic]] time''' if its time <math>T(n)</math> is <math>O\bigl((\log n)^k\bigr)</math> for some constant {{mvar|k}}. Another way to write this is <math>O(\log^kn)</math>.

For example, [[Matrix chain multiplication|matrix chain ordering]] can be solved in polylogarithmic time on a [[parallel random-access machine]],<ref>{{cite journal | last1 = Bradford | first1 = Phillip G. | last2 = Rawlins | first2 = Gregory J. E. | last3 = Shannon | first3 = Gregory E. | doi = 10.1137/S0097539794270698 | issue = 2 | journal = [[SIAM Journal on Computing]] | mr = 1616556 | pages = 466–490 | title = Efficient matrix chain ordering in polylog time | volume = 27 | year = 1998}}</ref> and [[Graph (discrete mathematics)|a graph]] can be [[Planarity testing|determined to be planar]] in a [[Dynamic connectivity|fully dynamic]] way in <math>O(\log^3n)</math> time per insert/delete operation.<ref>{{cite conference | last1 = Holm | first1 = Jacob | last2 = Rotenberg | first2 = Eva | editor1-last = Makarychev | editor1-first = Konstantin | editor2-last = Makarychev | editor2-first = Yury | editor3-last = Tulsiani | editor3-first = Madhur | editor4-last = Kamath | editor4-first = Gautam | editor5-last = Chuzhoy | editor5-first = Julia | editor5-link = Julia Chuzhoy | arxiv = 1911.03449 | contribution = Fully-dynamic planarity testing in polylogarithmic time | doi = 10.1145/3357713.3384249 | pages = 167–180 | publisher = Association for Computing Machinery | title = Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020 | year = 2020| isbn = 978-1-4503-6979-4 }}</ref>

== Sub-linear time ==
An algorithm is said to run in '''sub-linear time''' (often spelled '''sublinear time''') if <math>T(n)=o(n)</math>. In particular this includes algorithms with the time complexities defined above. 

The specific term ''sublinear time algorithm'' commonly refers to randomized algorithms that sample a small fraction of their inputs and process them efficiently to [[approximation algorithm|approximately]] infer properties of the entire instance.<ref>{{cite journal | last1 = Kumar | first1 = Ravi | last2 = Rubinfeld | first2 = Ronitt | author2-link = Ronitt Rubinfeld | title = Sublinear time algorithms | journal = [[SIGACT News]] | volume = 34 | issue = 4 | pages = 57–67 | url = http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/kumarR-survey.pdf | year = 2003 | doi = 10.1145/954092.954103| s2cid = 65359 }}</ref> This type of sublinear time algorithm is closely related to [[property testing]] and [[statistics]].

Other settings where algorithms can run in sublinear time include:

* [[Parallel algorithm]]s that have linear or greater total [[Analysis of parallel algorithms#Definitions|work]] (allowing them to read the entire input), but sub-linear [[Analysis of parallel algorithms#Definitions|depth]]. 
* Algorithms that have [[Promise problem|guaranteed assumptions]] on the input structure. An important example are operations on [[data structures]], e.g. [[binary search algorithm|binary search]] in a sorted array.
* Algorithms that search for local structure in the input, for example finding a local minimum in a 1-D array (can be solved in&nbsp;<math>O(\log(n))</math> time using a variant of binary search).&nbsp; A closely related notion is that of [[Local Computation Algorithms (LCA)]] where the algorithm receives a large input and queries to local information about some valid large output.<ref>{{cite book | last1=Rubinfeld | first1=Ronitt |author1-link = Ronitt Rubinfeld | date=2019 | chapter=Local Computation Algorithms | title=Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing | page=3  | doi=10.1145/3293611.3331587 | isbn=978-1-4503-6217-7 }}</ref>

== Linear time ==
An algorithm is said to take '''linear time''', or <math>O(n)</math> time, if its time complexity is <math>O(n)</math>. Informally, this means that the running time increases at most linearly with the size of the input. More precisely, this means that there is a constant {{mvar|c}} such that the running time is at most <math>cn</math> for every input of size {{mvar|n}}. For example, a procedure that adds up all elements of a list requires time proportional to the length of the list, if the adding time is constant, or, at least, bounded by a constant.

Linear time is the best possible time complexity in situations where the algorithm has to sequentially read its entire input. Therefore, much research has been invested into discovering algorithms exhibiting linear time or, at least, nearly linear time. This research includes both software and hardware methods. There are several hardware technologies which exploit [[Parallel computing|parallelism]] to provide this. An example is [[content-addressable memory]]. This concept of linear time is used in string matching algorithms such as the [[Boyer–Moore string-search algorithm]] and [[Ukkonen's algorithm]].

== <span id="Linearithmic time"></span> Quasilinear time ==
An algorithm is said to run in '''quasilinear time''' (also referred to as '''log-linear time''') if <math>T(n)=O(n\log^kn)</math> for some positive constant {{mvar|k}};<ref>{{cite journal | last1 = Naik | first1 = Ashish V. | last2 = Regan | first2 = Kenneth W. | last3 = Sivakumar | first3 = D. | doi = 10.1016/0304-3975(95)00031-Q | issue = 2 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]] | mr = 1355592 | pages = 325–349 | title = On quasilinear-time complexity theory | url = http://www.cse.buffalo.edu/~regan/papers/pdf/NRS95.pdf | volume = 148 | year = 1995| doi-access = free }}</ref> '''linearithmic time''' is the case <math>k=1</math>.<ref>{{cite book | last1 = Sedgewick | first1 = Robert | last2 = Wayne | first2 = Kevin | edition = 4th | page = 186 | publisher = Pearson Education | title = Algorithms | url = https://algs4.cs.princeton.edu/home/ | year = 2011}}</ref> Using [[soft O notation]] these algorithms are <math>\tilde{O}(n)</math>. Quasilinear time algorithms are also <math>O(n^{1+\varepsilon })</math> for every constant <math>\varepsilon >0</math> and thus run faster than any polynomial time algorithm whose time bound includes a term <math>n^c</math> for any <math>c>1</math>.

Algorithms which run in quasilinear time include:
* [[In-place merge sort]], <math>O(n\log^2n)</math>
* [[Quicksort]], <math>O(n\log n)</math>, in its randomized version, has a running time that is <math>O(n\log n)</math> in expectation on the worst-case input. Its non-randomized version has an <math>O(n\log n)</math> running time only when considering average case complexity.
* [[Heapsort]], <math>O(n\log n)</math>, [[merge sort]], [[introsort]], binary tree sort, [[smoothsort]], [[patience sorting]], etc. in the worst case
* [[Fast Fourier transform]]s, <math>O(n\log n)</math>
* [[Monge array]] calculation, <math>O(n\log n)</math>

In many cases, the <math>O(n\log n)</math> running time is simply the result of performing a <math>\Theta (\log n)</math> operation {{mvar|n}} times (for the notation, see {{slink|Big O notation|Family of Bachmann–Landau notations}}). For example, [[binary tree sort]] creates a [[binary tree]] by inserting each element of the {{mvar|n}}-sized array one by one. Since the insert operation on a [[self-balancing binary search tree]] takes <math>O(\log n)</math> time, the entire algorithm takes <math>O(n\log n)</math> time.

[[Comparison sort]]s require at least <math>\Omega (n\log n)</math> comparisons in the worst case because <math>\log (n!)=\Theta (n\log n)</math>, by [[Stirling's approximation]]. They also frequently arise from the [[recurrence relation]] <math display="inline">T(n) = 2T\left(\frac{n}{2}\right)+O(n)</math>.

== Sub-quadratic time ==
An [[algorithm]] is said to be '''subquadratic time''' if <math>T(n)=o(n^2)</math>.

For example, simple, comparison-based [[sorting algorithm]]s are quadratic (e.g. [[insertion sort]]), but more advanced algorithms can be found that are subquadratic (e.g. [[shell sort]]). No general-purpose sorts run in linear time, but the change from quadratic to sub-quadratic is of great practical importance.

== Polynomial time ==
{{main|P (complexity)}}
An algorithm is said to be of '''polynomial time''' if its running time is [[upper bound]]ed by a [[polynomial]] expression in the size of the input for the algorithm, that is, {{nowrap|1=''T''(''n'') = ''O''(''n''<sup>''k''</sup>)}} for some positive constant ''k''.<ref name=Sipser>{{Cite book| last=Sipser | first=Michael | author-link=Michael Sipser | title=Introduction to the Theory of Computation | year=2006 | publisher=Course Technology Inc | isbn=0-619-21764-2 }}</ref><ref>{{Cite book| last=Papadimitriou | first=Christos H. | author-link=Christos H. Papadimitriou | title=Computational complexity | year=1994 | publisher=Addison-Wesley | location=Reading, Mass.  | isbn=0-201-53082-1 }}</ref> [[Decision problem|Problems]] for which a deterministic polynomial-time algorithm exists belong to the [[complexity class]] '''[[P (complexity)|P]]''', which is central in the field of [[computational complexity theory]]. [[Cobham's thesis]] states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast".<ref>{{Cite book| last=Cobham | first=Alan | author-link=Alan Cobham (mathematician) | year = 1965 | chapter = The intrinsic computational difficulty of functions | title = Proc. Logic, Methodology, and Philosophy of Science II | publisher = North Holland}}</ref>

Some examples of polynomial-time algorithms:
* The [[selection sort]] sorting algorithm on ''n'' integers performs <math>An^2</math> operations for some constant ''A''. Thus it runs in time <math>O(n^2)</math> and is a polynomial-time algorithm.
* All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) can be done in polynomial time.
* [[Maximum matching]]s in [[Graph (discrete mathematics)|graphs]] can be found in polynomial time. In some contexts, especially in [[Optimization (mathematics)|optimization]], one differentiates between '''[[Strongly-polynomial time|strongly polynomial time]]''' and '''weakly polynomial time''' algorithms. 

These two concepts are only relevant if the inputs to the algorithms consist of integers.

=== Complexity classes ===

The concept of polynomial time leads to several complexity classes in computational complexity theory. Some important classes defined using polynomial time are the following.

* '''[[P (complexity)|P]]''': The [[complexity class]] of [[decision problem]]s that can be solved on a [[deterministic Turing machine]] in polynomial time
* '''[[NP (complexity)|NP]]''': The complexity class of decision problems that can be solved on a [[non-deterministic Turing machine]] in polynomial time
* '''[[ZPP (complexity)|ZPP]]''': The complexity class of decision problems that can be solved with zero error on a [[probabilistic Turing machine]] in polynomial time
* '''[[RP (complexity)|RP]]''': The complexity class of decision problems that can be solved with 1-sided error on a probabilistic Turing machine in polynomial time.
* '''[[BPP (complexity)|BPP]]''': The complexity class of decision problems that can be solved with 2-sided error on a probabilistic Turing machine in polynomial time
* '''[[BQP]]''': The complexity class of decision problems that can be solved with 2-sided error on a [[quantum Turing machine]] in polynomial time

P is the smallest time-complexity class on a deterministic machine which is [[Robustness (computer science)|robust]] in terms of machine model changes. (For example, a change from a single-tape Turing machine to a multi-tape machine can lead to a quadratic speedup, but any algorithm that runs in polynomial time under one model also does so on the other.) Any given [[abstract machine]] will have a complexity class corresponding to the problems which can be solved in polynomial time on that machine.

== Superpolynomial time ==
An algorithm is defined to take '''superpolynomial time''' if ''T''(''n'') is not bounded above by any polynomial; that is, if {{tmath|T(n)\not\in O(n^c)}} for every positive integer {{math|''c''}}.

For example, an algorithm that runs for {{math|2<sup>''n''</sup>}} steps on an input of size {{math|''n''}} requires superpolynomial time (more specifically, exponential time).

An algorithm that uses exponential resources is clearly superpolynomial, but some algorithms are only very weakly superpolynomial. For example, the [[Adleman–Pomerance–Rumely primality test]] runs for {{math|''n''<sup>''O''(log log ''n'')</sup>}} time on {{math|''n''}}-bit inputs; this grows faster than any polynomial for large enough {{math|''n''}}, but the input size must become impractically large before it cannot be dominated by a polynomial with small degree.

An algorithm that requires superpolynomial time lies outside the [[complexity class]] '''[[P (complexity)|P]]'''. [[Cobham's thesis]] posits that these algorithms are impractical, and in many cases they are. Since the [[P versus NP problem]] is unresolved, it is unknown whether [[NP-complete]] problems require superpolynomial time.

== Quasi-polynomial time ==
{{main|Quasi-polynomial time}}
'''Quasi-polynomial time''' algorithms are algorithms whose running time exhibits [[quasi-polynomial growth]], a type of behavior that may be slower than polynomial time but yet is significantly faster than [[exponential time]]. The worst case running time of a quasi-polynomial time algorithm is <math>2^{O(\log^c n)}</math> for some fixed {{nowrap|<math>c > 0</math>.}} When <math>c=1</math> this gives polynomial time, and for <math>c < 1</math> it gives sub-linear time.

There are some problems for which we know quasi-polynomial time algorithms, but no polynomial time algorithm is known. Such problems arise in approximation algorithms; a famous example is the directed [[Steiner tree problem]], for which there is a quasi-polynomial time approximation algorithm achieving an approximation factor of <math>O(\log^3 n)</math> (''n'' being the number of vertices), but showing the existence of such a polynomial time algorithm is an open problem.

Other computational problems with quasi-polynomial time solutions but no known polynomial time solution include the [[planted clique]] problem in which the goal is to [[clique problem|find a large clique]] in the union of a clique and a [[random graph]]. Although quasi-polynomially solvable, it has been conjectured that the planted clique problem has no polynomial time solution; this planted clique conjecture has been used as a [[computational hardness assumption]] to prove the difficulty of several other problems in computational [[game theory]], [[property testing]], and [[machine learning]].<ref>{{cite conference | last1 = Braverman | first1 = Mark | author1-link = Mark Braverman (mathematician) | last2 = Kun-Ko | first2 = Young | last3 = Rubinstein | first3 = Aviad | last4 = Weinstein | first4 = Omri | editor-last = Klein | editor-first = Philip N. | arxiv = 1504.08352 | contribution = ETH hardness for densest-{{mvar|k}}-subgraph with perfect completeness | doi = 10.1137/1.9781611974782.86 | mr = 3627815 | pages = 1326–1341 | publisher = Society for Industrial and Applied Mathematics | title = Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 | year = 2017| isbn = 978-1-61197-478-2 }}</ref>

The complexity class '''QP''' consists of all problems that have quasi-polynomial time algorithms. It can be defined in terms of [[DTIME]] as follows.<ref>{{ComplexityZoo|Class QP: Quasipolynomial-Time|Q#qp}}</ref>
:<math>\mbox{QP} = \bigcup_{c \in \mathbb{N}} \mbox{DTIME} \left(2^{\log^c n}\right)</math>

=== Relation to NP-complete problems ===

In complexity theory, the unsolved [[P versus NP]] problem asks if all problems in NP have polynomial-time algorithms. All the best-known algorithms for [[NP-complete]] problems like 3SAT etc. take exponential time. Indeed, it is conjectured for many natural NP-complete problems that they do not have sub-exponential time algorithms. Here "sub-exponential time" is taken to mean the second definition presented below. (On the other hand, many graph problems represented in the natural way by adjacency matrices are solvable in subexponential time simply because the size of the input is the square of the number of vertices.) This conjecture (for the k-SAT problem) is known as the [[exponential time hypothesis]].<ref name="ETH">{{cite journal | last1 = Impagliazzo | first1 = Russell | author1-link = Russell Impagliazzo | last2 = Paturi | first2 = Ramamohan | doi = 10.1006/jcss.2000.1727 | issue = 2 | journal = [[Journal of Computer and System Sciences]] | mr = 1820597 | pages = 367–375 | title = On the complexity of {{mvar|k}}-SAT | url = https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_2001_jcss.pdf | volume = 62 | year = 2001| doi-access = free }}</ref> Since it is conjectured that NP-complete problems do not have quasi-polynomial time algorithms, some inapproximability results in the field of [[approximation algorithms]] make the assumption that NP-complete problems do not have quasi-polynomial time algorithms. For example, see the known inapproximability results for the [[set cover]] problem.

== {{anchor|subexponential time}}Sub-exponential time ==
The term '''[[Infra-exponential|sub-exponential]] time''' is used to express that the running time of some algorithm may grow faster than any polynomial but is still significantly smaller than an exponential. In this sense, problems that have sub-exponential time algorithms are somewhat more tractable than those that only have exponential algorithms. The precise definition of "sub-exponential" is not generally agreed upon,<ref>{{Cite web|url=http://scottaaronson.com/blog/?p=394 |title=A not-quite-exponential dilemma |author=Aaronson, Scott |date=5 April 2009 |work=Shtetl-Optimized |access-date=2 December 2009}}</ref> however the two most widely used are below.

===First definition===
<!-- [[SUBEXP]] redirects here -->

A problem is said to be sub-exponential time solvable if it can be solved in running times whose logarithms grow smaller than any given polynomial. More precisely, a problem is in sub-exponential time if for every {{nowrap|''ε'' > 0}} there exists an algorithm which solves the problem in time ''O''(2<sup>''n''<sup>''ε''</sup></sup>). The set of all such problems is the complexity class '''SUBEXP''' which can be defined in terms of [[DTIME]] as follows.<ref name="bpp">{{Cite journal| last1=Babai | first1=László | author1-link = László Babai | last2=Fortnow | first2=Lance | author2-link = Lance Fortnow | last3=Nisan | first3=N. | author3-link = Noam Nisan | last4=Wigderson | first4=Avi | author4-link = Avi Wigderson | title=BPP has subexponential time simulations unless EXPTIME has publishable proofs | publisher=[[Springer-Verlag]] | location=Berlin, New York | year=1993 | journal=Computational Complexity | volume=3 | issue=4 | pages=307–318 | doi=10.1007/BF01275486| s2cid=14802332 }}</ref><ref>{{ComplexityZoo|Class SUBEXP: Deterministic Subexponential-Time|S#subexp}}</ref><ref>{{Cite conference| last1=Moser | first1=P. | contribution=Baire's Categories on Small Complexity Classes | publisher=Springer-Verlag | location=Berlin, New York | year=2003 | series=[[Lecture Notes in Computer Science]] |editor1=Andrzej Lingas |editor2=Bengt J. Nilsson|title=Fundamentals of Computation Theory: 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings| volume=2751 | issn=0302-9743 | pages=333–342| doi=10.1007/978-3-540-45077-1_31 | isbn=978-3-540-40543-6 }}</ref><ref>{{Cite book| last1=Miltersen | first1=P.B. | chapter=Derandomizing Complexity Classes | title=Handbook of Randomized Computing | publisher=Kluwer Academic Pub | year=2001 | volume=9 | page=843| doi=10.1007/978-1-4615-0013-1_19 | series=Combinatorial Optimization | doi-broken-date=1 November 2024 | isbn=978-1-4613-4886-3 }}</ref>

:<math>\textsf{SUBEXP}=\bigcap_{\varepsilon>0} \textsf{DTIME}\left(2^{n^\varepsilon}\right)</math>

This notion of sub-exponential is non-uniform in terms of ''ε'' in the sense that ''ε'' is not part of the input and each ε may have its own algorithm for the problem.

=== Second definition ===
Some authors define sub-exponential time as running times in <math>2^{o(n)}</math>.<ref name="ETH" /><ref>{{Cite journal| last1=Kuperberg | first1=Greg | title=A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem | location=Philadelphia | year=2005 | journal=SIAM Journal on Computing | issn=1095-7111 | volume=35 | issue=1 | page=188 | doi=10.1137/s0097539703436345| arxiv=quant-ph/0302112 | s2cid=15965140 }}</ref><ref>{{cite arXiv|eprint=quant-ph/0406151v1|author1=Oded Regev|title=A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space|year=2004}}</ref> This definition allows larger running times than the first definition of sub-exponential time. An example of such a sub-exponential time algorithm is the best-known classical algorithm for integer factorization, the [[general number field sieve]], which runs in time about {{nowrap|<math>2^{\tilde{O}(n^{1/3})}</math>,}} where the length of the input is {{mvar|n}}. Another example was the [[graph isomorphism problem]], which the best known algorithm from 1982 to 2016 solved in {{nowrap|<math>2^{O\left(\sqrt{n \log n}\right)}</math>.}} However, at [[Symposium on Theory of Computing|STOC]] 2016 a quasi-polynomial time algorithm was presented.<ref>{{cite book
 | last1 = Grohe | first1 = Martin
 | last2 = Neuen | first2 = Daniel
 | editor1-last = Dabrowski | editor1-first = Konrad K.
 | editor2-last = Gadouleau | editor2-first = Maximilien
 | editor3-last = Georgiou | editor3-first = Nicholas
 | editor4-last = Johnson | editor4-first = Matthew
 | editor5-last = Mertzios | editor5-first = George B.
 | editor6-last = Paulusma | editor6-first = Daniël
 | arxiv = 2011.01366
 | contribution = Recent advances on the graph isomorphism problem
 | isbn = 978-1-009-01888-3
 | mr = 4273431
 | pages = 187–234
 | publisher = Cambridge University Press
 | series = London Mathematical Society Lecture Note Series
 | title = Surveys in combinatorics 2021
 | volume = 470
 | year = 2021}}</ref>

It makes a difference whether the algorithm is allowed to be sub-exponential in the size of the instance, the number of vertices, or the number of edges. In [[parameterized complexity]], this difference is made explicit by considering pairs <math>(L,k)</math> of [[decision problem]]s and parameters ''k''. '''SUBEPT''' is the class of all parameterized problems that run in time sub-exponential in ''k'' and polynomial in the input size ''n'':<ref>{{Cite book
 | last1=Flum   | first1=Jörg
 | last2=Grohe | first2=Martin | author2-link = Martin Grohe
 | title = Parameterized Complexity Theory | year = 2006 | publisher = Springer
 | url = https://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0
 | isbn = 978-3-540-29952-3 | page=417}}</ref>

:<math>\textsf{SUBEPT}=\textsf{DTIME}\left(2^{o(k)} \cdot \textsf{poly}(n)\right).</math>

More precisely, SUBEPT is the class of all parameterized problems <math>(L,k)</math> for which there is a [[computable function]] <math>f : \N \to \N</math> with <math>f \in o(k)</math> and an algorithm that decides ''L'' in time <math>2^{f(k)} \cdot \textsf{poly}(n)</math>.

==== Exponential time hypothesis ====
{{Main|Exponential time hypothesis}}

The '''exponential time hypothesis''' ('''ETH''') is that [[3SAT]], the satisfiability problem of Boolean formulas in [[conjunctive normal form]] with at most three literals per clause and with ''n'' variables, cannot be solved in time 2<sup>''o''(''n'')</sup>. More precisely, the hypothesis is that there is some absolute constant {{math|''c'' > 0}} such that 3SAT cannot be decided in time 2<sup>''cn''</sup> by any deterministic Turing machine. With ''m'' denoting the number of clauses, ETH is equivalent to the hypothesis that ''k''SAT cannot be solved in time 2<sup>''o''(''m'')</sup> for any integer {{math|''k'' ≥ 3}}.<ref>{{Cite journal|first1=R.|last1=Impagliazzo|author1-link=Russell Impagliazzo|first2=R.|last2=Paturi|first3=F.|last3=Zane|title=Which problems have strongly exponential complexity?|journal=[[Journal of Computer and System Sciences]]|volume=63|issue=4|year=2001|pages=512–530|doi=10.1006/jcss.2001.1774|doi-access=free}}</ref> The exponential time hypothesis implies [[P ≠ NP]].

== Exponential time ==
An algorithm is said to be '''exponential time''', if ''T''(''n'') is upper bounded by 2<sup>poly(''n'')</sup>, where poly(''n'') is some polynomial in ''n''. More formally, an algorithm is exponential time if ''T''(''n'') is bounded by ''O''(2<sup>''n''<sup>''k''</sup></sup>) for some constant ''k''. Problems which admit exponential time algorithms on a deterministic Turing machine form the complexity class known as '''[[EXP]]'''.
:<math>\textsf{EXP} = \bigcup_{c \in \mathbb{R_+}} \textsf{DTIME}\left(2^{n^c}\right)</math>

Sometimes, exponential time is used to refer to algorithms that have ''T''(''n'') = 2<sup>''O''(''n'')</sup>, where the exponent is at most a linear function of ''n''. This gives rise to the complexity class '''[[E (complexity)|E]]'''.
:<math>\textsf{E} = \bigcup_{c \in \mathbb{N}} \textsf{DTIME}\left(2^{cn}\right)</math>

== Factorial time ==

An algorithm is said to be '''factorial time''' if ''T(n)'' is upper bounded by the [[factorial function]] ''n!''. Factorial time is a subset of exponential time (EXP) because <math> n! \leq n^n = 2^{n \log n}= O \left(2^{n^{1 + \epsilon}} \right)</math> for all <math>\epsilon > 0</math>. However, it is not a subset of E.

An example of an algorithm that runs in factorial time is [[bogosort]], a notoriously inefficient sorting algorithm based on [[trial and error]].  Bogosort sorts a list of ''n'' items by repeatedly [[shuffling]] the list until it is found to be sorted. In the average case, each pass through the bogosort algorithm will examine one of the ''n''! orderings of the ''n'' items.  If the items are distinct, only one such ordering is sorted. Bogosort shares patrimony with the [[infinite monkey theorem]].

== Double exponential time ==
An algorithm is said to be [[double exponential function|double exponential]] time if ''T''(''n'') is upper bounded by 2<sup>2<sup>poly(''n'')</sup></sup>, where poly(''n'') is some polynomial in ''n''. Such algorithms belong to the complexity class [[2-EXPTIME]].
:<math>\textsf{2-EXPTIME} = \bigcup_{c \in \N} \textsf{DTIME}\left( 2^{2^{n^c}}\right)</math>

Well-known double exponential time algorithms include:
* Decision procedures for [[Presburger arithmetic]]
* Computing a [[Gröbner basis]] (in the worst case<ref>{{cite journal | last1 = Mayr | first1 = Ernst W. | author1-link = Ernst Mayr (computer scientist) | last2 = Meyer | first2 = Albert R. | author2-link = Albert R. Meyer | doi = 10.1016/0001-8708(82)90048-2 | issue = 3 | journal = [[Advances in Mathematics]] | mr = 683204 | pages = 305–329 | title = The complexity of the word problems for commutative semigroups and polynomial ideals | volume = 46 | year = 1982| doi-access = free | hdl = 1721.1/149010 | hdl-access = free }}</ref>)
* [[Quantifier elimination]] on [[real closed field]]s takes at least double exponential time,<ref>{{cite journal | last1 = Davenport | first1 = James H. | author1-link = James H. Davenport | last2 = Heintz | first2 = Joos|author2-link=Joos Ulrich Heintz | doi = 10.1016/S0747-7171(88)80004-X | issue = 1–2 | journal = [[Journal of Symbolic Computation]] | mr = 949111 | pages = 29–35 | title = Real quantifier elimination is doubly exponential | volume = 5 | year = 1988| doi-access = free }}</ref> and can be done in this time.<ref>{{cite conference | last = Collins | first = George E. | author-link = George E. Collins| editor-last = Brakhage | editor-first = H. | contribution = Quantifier elimination for real closed fields by cylindrical algebraic decomposition | doi = 10.1007/3-540-07407-4_17 | mr = 0403962 | pages = 134–183 | publisher = Springer | series = Lecture Notes in Computer Science | title = Automata Theory and Formal Languages: 2nd GI Conference, Kaiserslautern, May 20–23, 1975 | volume = 33 | year = 1975| doi-access = free | isbn = 978-3-540-07407-6 }}</ref>

== See also ==
* [[L-notation]]
* [[Space complexity]]

== References ==
{{Reflist|colwidth=33em}}
{{Use dmy dates|date=September 2019}}

[[Category:Analysis of algorithms]]
[[Category:Computational complexity theory]]
[[Category:Computational resources]]
[[Category:Time]]