|This article does not cite any sources. (September 2017) (Learn how and when to remove this template message)|
In computer science, the computational complexity, or simply complexity of an algorithm is the amount of resources required for running it. The computational complexity of a problem is the minimum of the complexities of all possible algorithms for this problem (including the unknown algorithms).
As the amount of needed resources varies with the input, the complexity is generally expressed as a function n → f(n), where n is the size of the input, and f(n) is either the worst-case complexity, that is the maximum of the amount of resources that are needed for all input of size n, or the average-case complexity, that is average of the amount of resources over all input of size n.
When the nature of the resources is not explicitly given, this is usually the time needed for running the algorithm, and one talks of time complexity. However, this depends on the computer that is used, and the time is generally expressed as the number of needed elementary operations, which are supposed to take a constant time on a given computer, and to change by a constant factor when one changes of computer.
Otherwise, the resource that is considered is the size of the memory that is needed, and one talks of space complexity.
The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems ia called computational complexity theory. Clearly, both areas are strongly related, as the complexity of an algorithm is always an upper bound of the complexity of the problem solved by this algorithm.
||The present disambiguation page holds the title of a primary topic, and an article needs to be written about it. It is believed to qualify as a broad-concept article. It may be written directly at this page or drafted elsewhere and then moved over here. Related titles should be described in Computational complexity, while unrelated titles should be moved to Computational complexity (disambiguation).||