Table of common time complexities
The following table summarizes some classes of commonly encountered time complexities. In the table, poly(x) = xO(1), i.e., polynomial in x.
| Name | Complexity class | Running time (T(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(α(n)) | 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 | ||
| logarithmic time | DLOGTIME | O(log n) | log n, log(n2) | Binary search |
| polylogarithmic time | poly(log n) | (log n)2 | ||
| fractional power | O(nc) where 0 < c < 1 | n1/2, n2/3 | 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 poly(log n) | |||
| quadratic time | O(n2) | n2 | Bubble sort; Insertion sort; Direct convolution | |
| cubic time | O(n3) | n3 | Naive multiplication of two n×n matrices. Calculating partial correlation. | |
| polynomial time | P | 2O(log n) = poly(n) | n2 + n, n10 | Karmarkar's algorithm for linear programming; AKS primality test |
| quasi-polynomial time | QP | 2poly(log n) | nlog log n, nlog n | Best-known O(log2 n)-approximation algorithm for the directed Steiner tree problem. |
| sub-exponential time (first definition) |
SUBEXP | O(2nε) for all ε > 0 | Contains BPP unless EXPTIME (see below) equals MA. | |
| sub-exponential time (second definition) |
2o(n) | 2n1/3 | Best-known algorithm for integer factorization; formerly-best algorithm for graph isomorphism | |
| exponential time (with linear exponent) |
E | 2O(n) | 1.1n, 10n | Solving the traveling salesman problem using dynamic programming |
| exponential time | EXPTIME | 2poly(n) | 2n, 2n2 | Solving matrix chain multiplication via brute-force search |
| factorial time | O(n!) | n! | Solving the traveling salesman problem via brute-force search | |
| double exponential time | 2-EXPTIME | 22poly(n) | 22n | Deciding the truth of a given statement in Presburger arithmetic |
Comments
Post a Comment