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:

    A man who can dominate a London dinner table can dominate the world. The future belongs to the dandy. It is the exquisites who are going to rule.
    Oscar Wilde (1854–1900)

    The most common error made in matters of appearance is the belief that one should disdain the superficial and let the true beauty of one’s soul shine through. If there are places on your body where this is a possibility, you are not attractive—you are leaking.
    Fran Lebowitz (b. 1951)

    Boys finding for the first time their loins filled with heart’s
    blood
    Widowed farmers whose hands float under light covers to find
    themselves
    Arisen at sunrise
    James Dickey (b. 1923)

    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)