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

In 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.^[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 ${\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 >1}$ 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) = x^O(1), i.e., polynomial in x.

Name	Complexity class	Running time (T(n))	Examples of running times	Example algorithms
constant time		${\displaystyle O(1)}$	10	Finding the median value in a sorted array of numbers Calculating (−1)n
inverse Ackermann time		${\displaystyle O{\bigl (}\alpha (n){\bigr )}}$		Amortized time per operation using a disjoint set
iterated logarithmic time		${\displaystyle O(\log ^{*}n)}$		Distributed coloring of cycles
log-logarithmic		${\displaystyle O(\log \log n)}$		Amortized time per operation using a bounded priority queue[2]
logarithmic time	DLOGTIME	${\displaystyle O(\log n)}$	${\displaystyle \log n}$, ${\displaystyle \log(n^{2})}$	Binary search
polylogarithmic time		${\displaystyle {\text{poly}}(\log n)}$	${\displaystyle (\log n)^{2}}$
fractional power		${\displaystyle O(n^{c})}$ where ${\displaystyle 0<c<1}$	${\displaystyle n^{\frac {1}{2}}}$, ${\displaystyle n^{\frac {2}{3}}}$	Searching in a kd-tree
linear time		${\displaystyle O(n)}$	n, ${\displaystyle 2n+5}$	Finding the smallest or largest item in an unsorted array, Kadane's algorithm, linear search
"n log-star n" time		${\displaystyle O(n\log ^{*}n)}$		Seidel's polygon triangulation algorithm.
linearithmic time		${\displaystyle O(n\log n)}$	${\displaystyle n\log n}$, ${\displaystyle \log n!}$	Fastest possible comparison sort; Fast Fourier transform.
quasilinear time		${\displaystyle n{\text{poly}}(\log n)}$
quadratic time		${\displaystyle O(n^{2})}$	${\displaystyle n^{2}}$	Bubble sort; Insertion sort; Direct convolution
cubic time		${\displaystyle O(n^{3})}$	${\displaystyle n^{3}}$	Naive multiplication of two ${\displaystyle n\times n}$ matrices. Calculating partial correlation.
polynomial time	P	${\displaystyle 2^{O(\log n)}={\text{poly}}(n)}$	${\displaystyle n^{2}+n}$, ${\displaystyle n^{10}}$	Karmarkar's algorithm for linear programming; AKS primality test[3][4]
quasi-polynomial time	QP	${\displaystyle 2^{{\text{poly}}(\log n)}}$	${\displaystyle n^{\log \log n}}$, ${\displaystyle n^{\log n}}$	Best-known O(log2n)-approximation algorithm for the directed Steiner tree problem.
sub-exponential time (first definition)	SUBEXP	${\displaystyle O(2^{n^{\epsilon }})}$ for all ${\displaystyle \epsilon >0}$		Contains BPP unless EXPTIME (see below) equals MA.[5]
sub-exponential time (second definition)		${\displaystyle 2^{o(n)}}$	${\displaystyle {\sqrt{2^{n}}}}$	Best-known algorithm for integer factorization; formerly-best algorithm for graph isomorphism
exponential time (with linear exponent)	E	${\displaystyle 2^{O(n)}}$	${\displaystyle 1.1^{n}}$, ${\displaystyle 10^{n}}$	Solving the traveling salesman problem using dynamic programming
exponential time	EXPTIME	${\displaystyle 2^{{\text{poly}}(n)}}$	${\displaystyle 2^{n}}$, ${\displaystyle 2^{n^{2}}}$	Solving matrix chain multiplication via brute-force search
factorial time		${\displaystyle O(n!)}$	${\displaystyle n!}$	Solving the traveling salesman problem via brute-force search
double exponential time	2-EXPTIME	${\displaystyle 2^{2^{{\text{poly}}(n)}}}$	${\displaystyle 2^{2^{n}}}$	Deciding the truth of a given statement in Presburger arithmetic

Constant time

An algorithm is said to be constant time (also written as ${\textstyle O(1)}$ time) if the value of ${\textstyle T(n)}$^{[further explanation needed]} 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.

Here are some examples of code fragments that run in constant time:

int index = 5;
int item = list;
if (condition true) then
    perform some operation that runs in constant time
else
    perform some other operation that runs in constant time
for i = 1 to 100
    for j = 1 to 200
        perform some operation that runs in constant time

If ${\displaystyle T(n)}$ is ${\displaystyle O(a)}$, where a is any constant value, this is equivalent to and stated in standard notation as ${\displaystyle T(n)}$ being ${\displaystyle O(1)}$.

Logarithmic time

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.

An ${\displaystyle O(\log n)}$ algorithm is considered highly efficient, as the ratio of the number of operations to the size of the input decreases and tends to zero when n increases. An algorithm that must access all elements of its input cannot take logarithmic time, as the time taken for reading an input of size n is of the order of n.

An example of logarithmic time is given by dictionary search. Consider a dictionary D which contains n entries, sorted by alphabetical order. We suppose that, for ${\displaystyle 1\leq k\leq n}$, one may access the kth entry of the dictionary in a constant time. Let ${\displaystyle D(k)}$ denote this kth entry. Under these hypotheses, the test to see if a word w is in the dictionary may be done in logarithmic time: consider ${\displaystyle D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$, where ${\displaystyle \lfloor \;\rfloor }$ denotes the floor function. If ${\displaystyle w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$, then we are done. Else, if Zdroj:https://en.wikipedia.org?pojem=Polynomial-time
>Text je dostupný pod licencí Creative Commons Uveďte autora – Zachovejte licenci, případně za dalších podmínek. Podrobnosti naleznete na stránce Podmínky užití.