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 of, table, common, time and/or complexities:
“Remember thee?
Ay, thou poor ghost, whiles memory holds a seat
In this distracted globe. Remember thee?
Yea, from the table of my memory
I’ll wipe away all trivial fond records,
All saws of books, all forms, all pressures past
That youth and observation copied there,
And thy commandment all alone shall live
Within the book and volume of my brain,”
—William Shakespeare (1564–1616)
“I talk with the authority of failure—Ernest with the authority of success. We could never sit across the same table again.”
—F. Scott Fitzgerald (1896–1940)
“Unpretending mediocrity is good, and genius is glorious; but a weak flavor of genius in an essentially common person is detestable. It spoils the grand neutrality of a commonplace character, as the rinsings of an unwashed wine-glass spoil a draught of fair water.”
—Oliver Wendell Holmes, Sr. (1809–1894)
“I’ve been cursed for delving into the mysteries of life. Perhaps death is sacred, and I’ve profaned it. Oh, what a wonderful vision it was. I dreamed of being the first to give to the world the secret that God is so jealous of, the formula for life. Think of the power, to create a man. And I did, I did it, I created a man. And who knows, in time I could have trained him to do my will. I could have bred a race, I might even have found the secret of eternal life.”
—William Hurlbut (1883–?)
“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)