Linear time

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.^[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.

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	Time complexity ( $O (n)$ )	Examples of running times	Example algorithms
constant time		$O(1)$	10	Finding the median value in a sorted array of numbers. Calculating $(-1) n$
inverse Ackermann time		$O{\bigl (}\alpha (n){\bigr )}$		Amortized time per operation using a disjoint set
iterated logarithmic time		$O(\log ^{*}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(n^{2})$	Binary search
polylogarithmic time		${\text{poly}}(\log n)$	$(\log n)^{2}$
fractional power		$O(n^{c})$ where $0<c<1$	$n^{\frac {1}{2}}$ , $n^{\frac {2}{3}}$	Range searching in a kd-tree
linear time		$O(n)$	$n$ , $2n+5$	Finding the smallest or largest item in an unsorted array. Kadane's algorithm. Linear search
"n log-star n" time		$O(n\log ^{*}n)$		Seidel's polygon triangulation algorithm.
linearithmic time		$O(n\log n)$	$n\log n$ , $\log n!$	Fastest possible comparison sort Fast Fourier transform.
quasilinear time		$n{\text{poly}}(\log n)$	$n\log ^{2}n$	Multipoint polynomial evaluation
quadratic time		$O(n^{2})$	$n^{2}$	Bubble sort, Insertion sort, Direct convolution
cubic time		$O(n^{3})$	$n^{3}$	Naive multiplication of two $n\times n$ matrices Calculating partial correlation.
polynomial time	P	$2^{O(\log n)}={\text{poly}}(n)$	$n^{2}+n$

[1]

[2]