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.

"Running time" redirects here. For the film, see Running Time (film).

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

Polylogarithmic time[edit]

An algorithm is said to run in polylogarithmic time if its time $T(n)$ is $O{\bigl (}(\log n)^{k}{\bigr )}$ for some constant $k$ . Another way to write this is $O(\log ^{k}n)$ .

For example, matrix chain ordering can be solved in polylogarithmic time on a parallel random-access machine,^[7] and a graph can be determined to be planar in a fully dynamic way in $O(\log ^{3}n)$ time per insert/delete operation.^[8]

that have linear or greater total work (allowing them to read the entire input), but sub-linear depth.

Parallel algorithms

Algorithms that have on the input structure. An important example are operations on data structures, e.g. binary search in a sorted array.

guaranteed assumptions

Algorithms that search for local structure in the input, for example finding a local minimum in a 1-D array (can be solved in $O(\log(n))$ time using a variant of binary search). A closely related notion is that of where the algorithm receives a large input and queries to local information about some valid large output.^[10]

Local Computation Algorithms (LCA)

An algorithm is said to run in sub-linear time (often spelled sublinear time) if $T(n)=o(n)$ . In particular this includes algorithms with the time complexities defined above.

The specific term sublinear time algorithm commonly refers to randomized algorithms that sample a small fraction of their inputs and process them efficiently to approximately infer properties of the entire instance.^[9] This type of sublinear time algorithm is closely related to property testing and statistics.

Other settings where algorithms can run in sublinear time include:

Linear time[edit]

An algorithm is said to take linear time, or $O(n)$ time, if its time complexity is $O(n)$ . Informally, this means that the running time increases at most linearly with the size of the input. More precisely, this means that there is a constant $c$ such that the running time is at most $cn$ for every input of size $n$ . For example, a procedure that adds up all elements of a list requires time proportional to the length of the list, if the adding time is constant, or, at least, bounded by a constant.

Linear time is the best possible time complexity in situations where the algorithm has to sequentially read its entire input. Therefore, much research has been invested into discovering algorithms exhibiting linear time or, at least, nearly linear time. This research includes both software and hardware methods. There are several hardware technologies which exploit parallelism to provide this. An example is content-addressable memory. This concept of linear time is used in string matching algorithms such as the Boyer–Moore string-search algorithm and Ukkonen's algorithm.

$O(n\log ^{2}n)$

In-place merge sort

$O(n\log n)$ , in its randomized version, has a running time that is $O(n\log n)$ in expectation on the worst-case input. Its non-randomized version has an $O(n\log n)$ running time only when considering average case complexity.

Quicksort

$O(n\log n)$ , merge sort, introsort, binary tree sort, smoothsort, patience sorting, etc. in the worst case

Heapsort

$O(n\log n)$

Fast Fourier transforms

calculation, $O(n\log n)$

Monge array

An algorithm is said to run in quasilinear time (also referred to as log-linear time) if $T(n)=O(n\log ^{k}n)$ for some positive constant $k$ ;^[11] linearithmic time is the case $k=1$ .^[12] Using soft O notation these algorithms are ${\tilde {O}}(n)$ . Quasilinear time algorithms are also $O(n^{1+\varepsilon })$ for every constant $\varepsilon >0$ and thus run faster than any polynomial time algorithm whose time bound includes a term $n^{c}$ for any $c>1$ .

Algorithms which run in quasilinear time include:

In many cases, the $O(n\log n)$ running time is simply the result of performing a $\Theta (\log n)$ operation $n$ times (for the notation, see Big O notation § Family of Bachmann–Landau notations). For example, binary tree sort creates a binary tree by inserting each element of the $n$ -sized array one by one. Since the insert operation on a self-balancing binary search tree takes $O(\log n)$ time, the entire algorithm takes $O(n\log n)$ time.

Comparison sorts require at least $\Omega (n\log n)$ comparisons in the worst case because $\log(n!)=\Theta (n\log n)$ , by Stirling's approximation. They also frequently arise from the recurrence relation ${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$ .

Sub-quadratic time[edit]

An algorithm is said to be subquadratic time if $T(n)=o(n^{2})$ .

For example, simple, comparison-based sorting algorithms are quadratic (e.g. insertion sort), but more advanced algorithms can be found that are subquadratic (e.g. shell sort). No general-purpose sorts run in linear time, but the change from quadratic to sub-quadratic is of great practical importance.

The sorting algorithm on n integers performs $An^{2}$ operations for some constant A. Thus it runs in time $O(n^{2})$ and is a polynomial-time algorithm.

selection sort

All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) can be done in polynomial time.

in graphs can be found in polynomial time. In some contexts, especially in optimization, one differentiates between strongly polynomial time and weakly polynomial time algorithms.

Maximum matchings

Superpolynomial time[edit]

An algorithm is defined to take superpolynomial time if T(n) is not bounded above by any polynomial. Using little omega notation, it is ω(n^c) time for all constants c, where n is the input parameter, typically the number of bits in the input.

For example, an algorithm that runs for 2ⁿ steps on an input of size n requires superpolynomial time (more specifically, exponential time).

An algorithm that uses exponential resources is clearly superpolynomial, but some algorithms are only very weakly superpolynomial. For example, the Adleman–Pomerance–Rumely primality test runs for n^{O(log log n)} time on n-bit inputs; this grows faster than any polynomial for large enough n, but the input size must become impractically large before it cannot be dominated by a polynomial with small degree.

An algorithm that requires superpolynomial time lies outside the complexity class P. Cobham's thesis posits that these algorithms are impractical, and in many cases they are. Since the P versus NP problem is unresolved, it is unknown whether NP-complete problems require superpolynomial time.

Factorial time[edit]

An algorithm is said to be factorial time if T(n) is upper bounded by the factorial function n!. Factorial time is a subset of exponential time (EXP) because $n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }}\right)$ for all $\epsilon >0$ . However, it is not a subset of E.

An example of an algorithm that runs in factorial time is bogosort, a notoriously inefficient sorting algorithm based on trial and error. Bogosort sorts a list of n items by repeatedly shuffling the list until it is found to be sorted. In the average case, each pass through the bogosort algorithm will examine one of the n! orderings of the n items. If the items are distinct, only one such ordering is sorted. Bogosort shares patrimony with the infinite monkey theorem.

Decision procedures for

Presburger arithmetic

Computing a (in the worst case^[27])

Gröbner basis

on real closed fields takes at least double exponential time,^[28] and can be done in this time.^[29]

Quantifier elimination

An algorithm is said to be double exponential time if T(n) is upper bounded by 2^{2^poly(n)}, where poly(n) is some polynomial in n. Such algorithms belong to the complexity class 2-EXPTIME.

Well-known double exponential time algorithms include: