## ::Time complexity

### ::concepts

''n''::first    Input::problem    Which::constant    ''T''::number    Problems::journal    Machine::class

{{#invoke:redirect hatnote|redirect}} In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input<ref name=Sipser />:226. The time complexity of an algorithm is commonly expressed using big O notation, which excludes coefficients and lower order terms. When expressed this way, the time complexity is said to be described asymptotically, i.e., as the input size goes to infinity. For example, if the time required by an algorithm on all inputs of size n is at most 5n3 + 3n for any n (bigger than some n0), the asymptotic time complexity is O(n3).

Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an 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 differ by at most a constant factor.

Since an algorithm's performance time may vary with different inputs of the same size, one commonly uses the worst-case time complexity of an algorithm, denoted as T(n), which is defined as the maximum amount of time taken on any input of size n. Less common, and usually specified explicitly, is the measure of average-case complexity. Time complexities are classified by the nature of the function T(n). For instance, an algorithm with T(n) = O(n) is called a linear time algorithm, and an algorithm with T(n) = O(Mn) and mn= O(T(n)) for some Mm > 1 is said to be an exponential time algorithm.

Time complexity sections
Intro  Table of common time complexities  Constant time  Logarithmic time  Polylogarithmic time  Sub-linear time  Linear time  Quasilinear time  Sub-quadratic time  Polynomial time  Superpolynomial time  Quasi-polynomial time  [[Time_complexity?section={{safesubst:#invoke:anchor|main}}Sub-exponential_time|{{safesubst:#invoke:anchor|main}}Sub-exponential time]]  Exponential time  Double exponential time  See also  References

 PREVIOUS: Intro NEXT: Table of common time complexities << >>