Table of Common Time Complexities
Further information: Computational complexity of mathematical operationsThe following table summarises 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 | Determining if an integer (represented in binary) is even or odd | |
| 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 | Finding the smallest item in an unsorted array | |
| "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 | |
| quadratic time | O(n2) | n2 | Bubble sort; Insertion sort | |
| cubic time | O(n3) | n3 | Naive multiplication of two n×n matrices. Calculating partial correlation. | |
| polynomial time | P | 2O(log n) = poly(n) | n, n log 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 | O(2log nlog log n) | Assuming complexity theoretic conjectures, BPP is contained in SUBEXP. |
| sub-exponential time (second definition) |
2o(n) | 2n1/3 | Best-known algorithm for integer factorization and graph isomorphism | |
| exponential time | E | 2O(n) | 1.1n, 10n | Solving the traveling salesman problem using dynamic programming |
| factorial time | O(n!) | n! | Solving the traveling salesman problem via brute-force search | |
| exponential time | EXPTIME | 2poly(n) | 2n, 2n2 | |
| double exponential time | 2-EXPTIME | 22poly(n) | 22n | Deciding the truth of a given statement in Presburger arithmetic |
Read more about this topic: Time Complexity
Famous quotes containing the words table, common, time and/or complexities:
“The best thing about Sassy Seats is that grandmothers cannot figure out how they work and are in constant fear of the child’s falling. This often makes them forget to comment on other aspects of the child’s development, like why he is not yet talking or is still wearing diapers. Some grandmothers will spend an entire meal peering beneath the table and saying, “Is that thing steady?” rather than, “Have you had a doctor look at that left hand?””
—Anna Quindlen (20th century)
“Farmers in overalls and wide-brimmed straw hats lounge about the store on hot summer days, when the most common sound is the thump-thump-thump of a hound’s leg on the floor as he scratches contentedly. Oldtime hunters say that fleas are a hound’s salvation: his constant twisting and clawing in pursuit of the tormentors keeps his joints supple.”
—Administration in the State of Arka, U.S. public relief program (1935-1943)
“Everyone nowadays lives through too much and thinks through too little: they have a ravenous appetite and colic at the same time so that they keep getting thinner and thinner no matter how much they eat.—Whoever says nowadays, “I have not experienced anything”—is a simpleton.”
—Friedrich Nietzsche (1844–1900)
“From infancy, a growing girl creates a tapestry of ever-deepening and ever- enlarging relationships, with her self at the center. . . . The feminine personality comes to define itself within relationship and connection, where growth includes greater and greater complexities of interaction.”
—Jeanne Elium (20th century)