Time Complexity - Table of Common Time Complexities

Table of Common Time Complexities

Further information: Computational complexity of mathematical operations

The 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 moderate Aristotelian city
    Of darning and the Eight-Fifteen, where Euclid’s geometry
    And Newton’s mechanics would account for our experience,
    And the kitchen table exists because I scrub it.
    —W.H. (Wystan Hugh)

    So neither the one who plants nor the one who waters is anything, but only God who gives the growth. The one who plants and the one who waters have a common purpose, and each will receive wages according to the labor of each. For we are God’s servants, working together; you are God’s field, God’s building.
    Bible: New Testament, 1 Corinthians 3:7-9.

    The life of a creator is not the only life nor perhaps the most interesting which a man leads. There is a time for play and a time for work, a time for creation and a time for lying fallow. And there is a time, glorious too in its own way, when one scarcely exists, when one is a complete void. I mean—when boredom seems the very stuff of life.
    Henry Miller (1891–1980)

    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)