Time complexity

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 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. 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 ${\displaystyle O(n)}$, ${\displaystyle O(n\log n)}$, ${\displaystyle O(n^{\alpha })}$, ${\displaystyle O(2^{n})}$, etc., where n is the 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 ${\displaystyle O(n)}$ is a linear time algorithm and an algorithm with time complexity ${\displaystyle O(n^{\alpha })}$ for some constant ${\displaystyle \alpha >0}$ is a polynomial time algorithm.

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

An algorithm is said to be constant time (also written as ${\textstyle O(1)}$ time) if the value of ${\textstyle T(n)}$ (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 takes constant time as only one 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 in the array is needed in order to determine the minimal value. Hence it is a linear time operation, taking ${\textstyle O(n)}$ 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 a and b if necessary so that ${\textstyle a\leq b}$" is called constant time even though the time may depend on whether or not it is already true that ${\textstyle a\leq b}$. However, there is some constant t such that the time required is always at most t.

An algorithm is said to take logarithmic time when ${\displaystyle T(n)=O(\log n)}$. Since ${\displaystyle \log _{a}n}$ and ${\displaystyle \log _{b}n}$ are related by a constant multiplier, and such a multiplier is irrelevant to big O classification, the standard usage for logarithmic-time algorithms is ${\displaystyle O(\log n)}$ regardless of the base of the logarithm appearing in the expression of T.

Algorithms taking logarithmic time are commonly found in operations on binary trees or when using binary search.