Time complexity |
In
Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the
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.
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 | Running time (T(n)) | Examples of running times | Example algorithms | |
---|---|---|---|---|
constant time | O(1) | 10 | Finding the median value in a list of sorted numbers | |
O(α(n)) | ||||
O( |
||||
log-logarithmic | O(log log n) | Amortized time per operation using a bounded | ||
logarithmic time | O(log n) | log n, log(n^{2}) | ||
polylogarithmic time | poly(log n) | (log n)^{2} | ||
fractional power | O(n^{c}) where 0 < c < 1 | n^{1/2}, n^{2/3} | Searching in a | |
linear time | O(n) | n, 2n + 5 | Finding the smallest or largest item in an unsorted | |
"n log-star n" time | O(n |
|||
quasilinear time | O(n log n) | n log n, log n! | Fastest possible | |
quadratic time | O(n^{2}) | n^{2} | ||
cubic time | O(n^{3}) | n^{3} | Naive multiplication of two n×n matrices. Calculating | |
polynomial time | 2^{O(log n)} = poly(n) | n^{2} + n, n^{10} | ||
quasi-polynomial time | QP | 2^{poly(log n)} | n^{log log n}, n^{log n} | Best-known O(log^{2} n)- |
sub-exponential time (first definition) |
SUBEXP | O(2^{nε}) for all ε > 0 | O(2^{log nlog log n}) | Contains |
sub-exponential time (second definition) |
2^{o(n)} | 2^{n1/3} | Best-known algorithm for | |
exponential time (with linear exponent) |
2^{O(n)} | 1.1^{n}, 10^{n} | Solving the | |
exponential time | 2^{poly(n)} | 2^{n}, 2^{n2} | Solving | |
factorial time | O(n!) | n! | Solving the | |
double exponential time | 2^{2poly(n)} | 2^{2n} | Deciding the truth of a given statement in |