This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(December 2017) (Learn how and when to remove this message)

Incomputer science, thecomputational complexity or simplycomplexity of analgorithm is the amount of resources required to run it.^[1] Particular focus is given tocomputation time (generally measured by the number of needed elementary operations) andmemory storage requirements. The complexity of aproblem is the complexity of the best algorithms that allow solving the problem.

The study of the complexity of explicitly given algorithms is calledanalysis of algorithms, while the study of the complexity of problems is calledcomputational complexity theory. Both areas are highly related, as the complexity of an algorithm is always anupper bound on the complexity of the problem solved by this algorithm. Moreover, for designing efficient algorithms, it is often fundamental to compare the complexity of a specific algorithm to the complexity of the problem to be solved. Also, in most cases, the only thing that is known about the complexity of a problem is that it is lower than the complexity of the most efficient known algorithms. Therefore, there is a large overlap between analysis of algorithms and complexity theory.

As the amount of resources required to run an algorithm generally varies with the size of the input, the complexity is typically expressed as a functionn →f(n), wheren is the size of the input andf(n) is either theworst-case complexity (the maximum of the amount of resources that are needed over all inputs of sizen) or theaverage-case complexity (the average of the amount of resources over all inputs of sizen).Time complexity is generally expressed as the number of required elementary operations on an input of sizen, where elementary operations are assumed to take a constant amount of time on a given computer and change only by a constant factor when run on a different computer.Space complexity is generally expressed as the amount ofmemory required by an algorithm on an input of sizen.

The resource that is most commonly considered is time. When "complexity" is used without qualification, this generally means time complexity.

The usual units of time (seconds, minutes etc.) are not used incomplexity theory because they are too dependent on the choice of a specific computer and on the evolution of technology. For instance, a computer today can execute an algorithm significantly faster than a computer from the 1960s; however, this is not an intrinsic feature of the algorithm but rather a consequence of technological advances incomputer hardware. Complexity theory seeks to quantify the intrinsic time requirements of algorithms, that is, the basic time constraints an algorithm would place onany computer. This is achieved by counting the number ofelementary operations that are executed during the computation. These operations are assumed to take constant time (that is, not affected by the size of the input) on a given machine, and are often calledsteps.

Formally, thebit complexity refers to the number of operations onbits that are needed for running an algorithm. With mostmodels of computation, it equals the time complexity up to a constant factor. Oncomputers, the number of operations onmachine words that are needed is also proportional to the bit complexity. So, thetime complexity and thebit complexity are equivalent for realistic models of computation.

Another important resource is the size ofcomputer memory that is needed for running algorithms.

For the class ofdistributed algorithms that are commonly executed by multiple, interacting parties, the resource that is of most interest is the communication complexity. It is the necessary amount of communication between the executing parties.

The number ofarithmetic operations is another resource that is commonly used. In this case, one talks ofarithmetic complexity. If one knows anupper bound on the size of thebinary representation of the numbers that occur during a computation, the time complexity is generally the product of the arithmetic complexity by a constant factor.

For many algorithms the size of the integers that are used during a computation is not bounded, and it is not realistic to consider that arithmetic operations take a constant time. Therefore, the time complexity, generally calledbit complexity in this context, may be much larger than the arithmetic complexity. For example, the arithmetic complexity of the computation of thedeterminant of an×ninteger matrix is${\displaystyle O(n^3)}$ for the usual algorithms (Gaussian elimination). The bit complexity of the same algorithms isexponential inn, because the size of the coefficients may grow exponentially during the computation. On the other hand, if these algorithms are coupled withmulti-modular arithmetic, the bit complexity may be reduced toO^~(n⁴).

Insorting andsearching, the resource that is generally considered is the number of entry comparisons. This is generally a good measure of the time complexity if data are suitably organized.

It is impossible to count the number of steps of an algorithm on all possible inputs. As the complexity generally increases with the size of the input, the complexity is typically expressed as a function of the sizen (inbits) of the input, and therefore, the complexity is a function ofn. However, the complexity of an algorithm may vary dramatically for different inputs of the same size. Therefore, several complexity functions are commonly used.

Theworst-case complexity is the maximum of the complexity over all inputs of sizen, and theaverage-case complexity is the average of the complexity over all inputs of sizen (this makes sense, as the number of possible inputs of a given size is finite). Generally, when "complexity" is used without being further specified, this is the worst-case time complexity that is considered.

It is generally difficult to compute precisely the worst-case and the average-case complexity. In addition, these exact values provide little practical application, as any change of computer or of model of computation would change the complexity somewhat. Moreover, the resource use is not critical for small values ofn, and this makes that, for smalln, the ease of implementation is generally more interesting than a low complexity.

For these reasons, one generally focuses on the behavior of the complexity for largen, that is on itsasymptotic behavior whenn tends to the infinity. Therefore, the complexity is generally expressed by usingbig O notation.

For example, the usual algorithm for integermultiplication has a complexity of${\displaystyle O(n^2),}$ this means that there is a constant${\displaystyle c_u}$ such that the multiplication of two integers of at mostn digits may be done in a time less than${\displaystyle c_u{n}^2.}$ This bound issharp in the sense that the worst-case complexity and the average-case complexity are${\displaystyle \mathrm{\Omega }(n^2),}$ which means that there is a constant${\displaystyle c_l}$ such that these complexities are larger than${\displaystyle c_l{n}^2.}$ Theradix does not appear in these complexity, as changing of radix changes only the constants${\displaystyle c_u}$ and${\displaystyle c_l.}$

The evaluation of the complexity relies on the choice of amodel of computation, which consists in defining the basic operations that are done in a unit of time. When the model of computation is not explicitly specified, it is generally implicitely assumed as being amultitape Turing machine, since several more realistic models of computation, such asrandom-access machines are asymptotically equivalent for most problems. It is only for very specific and difficult problems, such asinteger multiplication in time${\displaystyle O(n\log n),}$ that the explicit definition of the model of computation is required for proofs.

Adeterministic model of computation is a model of computation such that the successive states of the machine and the operations to be performed are completely determined by the preceding state. Historically, the first deterministic models wererecursive functions,lambda calculus, andTuring machines. The model ofrandom-access machines (also called RAM-machines) is also widely used, as a closer counterpart to realcomputers.

When the model of computation is not specified, it is generally assumed to be amultitape Turing machine. For most algorithms, the time complexity is the same on multitape Turing machines as on RAM-machines, although some care may be needed in how data is stored in memory to get this equivalence.

In anon-deterministic model of computation, such asnon-deterministic Turing machines, some choices may be done at some steps of the computation. In complexity theory, one considers all possible choices simultaneously, and the non-deterministic time complexity is the time needed, when the best choices are always done. In other words, one considers that the computation is done simultaneously on as many (identical) processors as needed, and the non-deterministic computation time is the time spent by the first processor that finishes the computation. This parallelism is partly amenable toquantum computing via superposedentangled states in running specificquantum algorithms, like e.g.Shor's factorization of yet only small integers (as of March 2018^[update]: 21 = 3 × 7).

Even when such a computation model is not realistic yet, it has theoretical importance, mostly related to theP = NP problem, which questions the identity of the complexity classes formed by taking "polynomial time" and "non-deterministic polynomial time" as least upper bounds. Simulating an NP-algorithm on a deterministic computer usually takes "exponential time". A problem is in the complexity classNP, if it may be solved inpolynomial time on a non-deterministic machine. A problem isNP-complete if, roughly speaking, it is in NP and is not easier than any other NP problem. Manycombinatorial problems, such as theKnapsack problem, thetravelling salesman problem, and theBoolean satisfiability problem are NP-complete. For all these problems, the best known algorithm has exponential complexity. If any one of these problems could be solved in polynomial time on a deterministic machine, then all NP problems could also be solved in polynomial time, and one would have P = NP. As of 2017^[update] it is generally conjectured thatP ≠ NP, with the practical implication that the worst cases of NP problems are intrinsically difficult to solve, i.e., take longer than any reasonable time span (decades!) for interesting lengths of input.

Parallel and distributed computing consist of splitting computation on several processors, which work simultaneously. The difference between the different model lies mainly in the way of transmitting information between processors. Typically, in parallel computing the data transmission between processors is very fast, while, in distributed computing, the data transmission is done through anetwork and is therefore much slower.

The time needed for a computation onN processors is at least the quotient byN of the time needed by a single processor. In fact this theoretically optimal bound can never be reached, because some subtasks cannot be parallelized, and some processors may have to wait a result from another processor.

The main complexity problem is thus to design algorithms such that the product of the computation time by the number of processors is as close as possible to the time needed for the same computation on a single processor.

Aquantum computer is a computer whose model of computation is based onquantum mechanics. TheChurch–Turing thesis applies to quantum computers; that is, every problem that can be solved by a quantum computer can also be solved by a Turing machine. However, some problems may theoretically be solved with a much lowertime complexity using a quantum computer rather than a classical computer. This is, for the moment, purely theoretical, as no one knows how to build an efficient quantum computer.

Quantum complexity theory has been developed to study thecomplexity classes of problems solved using quantum computers. It is used inpost-quantum cryptography, which consists of designingcryptographic protocols that are resistant to attacks by quantum computers.

The complexity of a problem is theinfimum of the complexities of the algorithms that may solve the problem^{[citation needed]}, including unknown algorithms. Thus the complexity of a problem is not greater than the complexity of any algorithm that solves the problems.

It follows that every complexity of an algorithm, that is expressed withbig O notation, is also an upper bound on the complexity of the corresponding problem.

On the other hand, it is generally hard to obtain nontrivial lower bounds for problem complexity, and there are few methods for obtaining such lower bounds.

For solving most problems, it is required to read all input data, which, normally, needs a time proportional to the size of the data. Thus, such problems have a complexity that is at leastlinear, that is, usingbig omega notation, a complexity${\displaystyle \mathrm{\Omega }(n).}$

The solution of some problems, typically incomputer algebra andcomputational algebraic geometry, may be very large. In such a case, the complexity is lower bounded by the maximal size of the output, since the output must be written. For example, asystem ofn polynomial equations of degreed inn indeterminates may have up to${\displaystyle d^n}$complex solutions, if the number of solutions is finite (this isBézout's theorem). As these solutions must be written down, the complexity of this problem is${\displaystyle \mathrm{\Omega }(d^n).}$ For this problem, an algorithm of complexity${\displaystyle d^{O(n)}}$ is known, which may thus be considered as asymptotically quasi-optimal.

A nonlinear lower bound of${\displaystyle \mathrm{\Omega }(n\log n)}$ is known for the number of comparisons needed for asorting algorithm. Thus the best sorting algorithms are optimal, as their complexity is${\displaystyle O(n\log n).}$ This lower bound results from the fact that there aren! ways of orderingn objects. As each comparison splits in two parts this set ofn! orders, the number ofN of comparisons that are needed for distinguishing all orders must verify${\displaystyle 2^N>n!,}$ which implies${\displaystyle N=\mathrm{\Omega }(n\log n),}$ byStirling's formula.

A standard method for getting lower bounds of complexity consists ofreducing a problem to another problem. More precisely, suppose that one may encode a problemA of sizen into a subproblem of sizef(n) of a problemB, and that the complexity ofA is${\displaystyle \mathrm{\Omega }(g(n)).}$ Without loss of generality, one may suppose that the functionf increases withn and has aninverse functionh. Then the complexity of the problemB is${\displaystyle \mathrm{\Omega }(g(h(n))).}$ This is the method that is used to prove that, ifP ≠ NP (an unsolved conjecture), the complexity of everyNP-complete problem is${\displaystyle \mathrm{\Omega }(n^k),}$ for every positive integerk.

Evaluating the complexity of an algorithm is an important part ofalgorithm design, as this gives useful information on the performance that may be expected.

It is a common misconception that the evaluation of the complexity of algorithms will become less important as a result ofMoore's law, which posits theexponential growth of the power of moderncomputers. This is wrong because this power increase allows working with large input data (big data). For example, when one wants to sort alphabetically a list of a few hundreds of entries, such as thebibliography of a book, any algorithm should work well in less than a second. On the other hand, for a list of a million of entries (the phone numbers of a large town, for example), the elementary algorithms that require${\displaystyle O(n^2)}$ comparisons would have to do a trillion of comparisons, which would need around three hours at the speed of 10 million of comparisons per second. On the other hand, thequicksort andmerge sort require only${\displaystyle n{\log }_{2}n}$ comparisons (as average-case complexity for the former, as worst-case complexity for the latter). Forn = 1,000,000, this gives approximately 30,000,000 comparisons, which would only take 3 seconds at 10 million comparisons per second.

Thus the evaluation of the complexity may allow eliminating many inefficient algorithms before any implementation. This may also be used for tuning complex algorithms without testing all variants. By determining the most costly steps of a complex algorithm, the study of complexity allows also focusing on these steps the effort for improving the efficiency of an implementation.

• Computational complexity of mathematical operations
• Chinese Postman Problem Complexity List
• Master theorem (analysis of algorithms)

• Arora, Sanjeev; Barak, Boaz (2009),Computational Complexity: A Modern Approach,Cambridge,ISBN 978-0-521-42426-4,Zbl 1193.68112
• Calude, Cristian (1988),Theories of Computational Complexity,Elsevier, p. 487,ISBN 9780444703569
• Du, Ding-Zhu; Ko, Ker-I (2000),Theory of Computational Complexity,John Wiley & Sons,ISBN 978-0-471-34506-0,ISSN 0167-5060
• Garey, Michael R.;Johnson, David S. (1979),Computers and Intractability: A Guide to the Theory of NP-Completeness, Series of Books in the Mathematical Sciences (1st ed.), New York:W. H. Freeman and Company,ISBN 9780716710455,MR 0519066,OCLC 247570676
• Goldreich, Oded (2008),Computational Complexity: A Conceptual Perspective, Cambridge University Press
• van Leeuwen, Jan, ed. (1990),Handbook of theoretical computer science (vol. A): algorithms and complexity,MIT Press,ISBN 978-0-444-88071-0
• Papadimitriou, Christos (1994),Computational Complexity (1st ed.), Addison Wesley,ISBN 0-201-53082-1
• Sipser, Michael (2006),Introduction to the Theory of Computation (2nd ed.), USA:Thomson Course Technology,ISBN 0-534-95097-3

• Analysis of algorithms
• Computational complexity theory
• Computational resources

• Articles with short description
• Short description is different from Wikidata
• Articles lacking in-text citations from December 2017
• All articles lacking in-text citations
• Articles containing potentially dated statements from March 2018
• All articles containing potentially dated statements
• Articles containing potentially dated statements from 2017
• All articles with unsourced statements
• Articles with unsourced statements from May 2023