Time complexity

Graphs of functions commonly used in the analysis of algorithms, showing the number of operations N versus input size n for each function

In computer science, the time complexity is the computational complexity that describes the amount of 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 differ by at most a constant factor.

Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the 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 of the size of the input.[1]: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 behavior of the complexity. Therefore, the time complexity is commonly expressed using big O notation, typically etc., where n is the input size in units of bits 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 is a linear time algorithm and an algorithm with time complexity for some constant is a polynomial time algorithm.

Table of common time complexities

The following table summarizes some classes of commonly encountered time complexities. In the table, poly(x) = xO(1), i.e., polynomial in x.

Name Complexity class Running time (T(n)) Examples of running times Example algorithms
constant time O(1) 10 Determining if an integer (represented in binary) is even or odd
inverse Ackermann time O(α(n)) Amortized time per operation using a disjoint set
iterated logarithmic time O(* n) Distributed coloring of cycles
log-logarithmic O(log log n) Amortized time per operation using a bounded priority queue[2]
logarithmic time DLOGTIME O(log n) log n, log(n2) Binary search
polylogarithmic time poly(log n) (log n)2
fractional power O(nc) where 0 < c < 1 n1/2, n2/3 Searching in a kd-tree
linear time O(n) n Finding the smallest or largest item in an unsorted array, Kadane's algorithm
"n log star n" time O(n * n) Seidel's polygon triangulation algorithm.
quasilinear time O(n log n) n log n, log n! Fastest possible comparison sort; Fast Fourier transform.
quadratic time O(n2) n2 Bubble sort; Insertion sort; Direct convolution
cubic time O(n3) n3 Naive multiplication of two n×n matrices. Calculating partial correlation.
polynomial time P 2O(log n) = poly(n) n, n log n, n10 Karmarkar's algorithm for linear programming; AKS primality test
quasi-polynomial time QP 2poly(log n) nlog log n, nlog n Best-known O(log2 n)-approximation algorithm for the directed Steiner tree problem.
sub-exponential time
(first definition)
SUBEXP O(2nε) for all ε > 0 O(2log nlog log n) Assuming complexity theoretic conjectures, BPP is contained in SUBEXP.[3]
sub-exponential time
(second definition)
2o(n) 2n1/3 Best-known algorithm for integer factorization and graph isomorphism
exponential time
(with linear exponent)
E 2O(n) 1.1n, 10n Solving the traveling salesman problem using dynamic programming
exponential time EXPTIME 2poly(n) 2n, 2n2 Solving matrix chain multiplication via brute-force search
factorial time O(n!) n! Solving the traveling salesman problem via brute-force search
double exponential time 2-EXPTIME 22poly(n) 22n Deciding the truth of a given statement in Presburger arithmetic
Other Languages