Big O Notation - Orders of Common Functions

Orders of Common Functions

Further information: Time complexity#Table of common time complexities

Here is a list of classes of functions that are commonly encountered when analyzing the running time of an algorithm. In each case, c is a constant and n increases without bound. The slower-growing functions are generally listed first.

Notation Name Example
constant Determining if a number is even or odd; using a constant-size lookup table
double logarithmic Finding an item using interpolation search in a sorted array of uniformly distributed values.
logarithmic Finding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a Binomial heap.
fractional power Searching in a kd-tree
linear Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array; Adding two n-bit integers by ripple carry.
n log-star n Performing triangulation of a simple polygon using Seidel's algorithm. (Note log^*(n) = \begin{cases} 0, & \text{if }n \leq 1 \\ 1 + \log^*(\log n), & \text{if }n>1 \end{cases}
linearithmic, loglinear, or quasilinear Performing a Fast Fourier transform; heapsort, quicksort (best and average case), or merge sort
quadratic Multiplying two n-digit numbers by a simple algorithm; bubble sort (worst case or naive implementation), Shell sort, quicksort (worst case), selection sort or insertion sort
polynomial or algebraic Tree-adjoining grammar parsing; maximum matching for bipartite graphs

L-notation or sub-exponential Factoring a number using the quadratic sieve or number field sieve
exponential Finding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search
factorial Solving the traveling salesman problem via brute-force search; generating all unrestricted permutations of a poset; finding the determinant with expansion by minors.

The statement is sometimes weakened to to derive simpler formulas for asymptotic complexity. For any and, is a subset of for any, so may be considered as a polynomial with some bigger order.

Read more about this topic:  Big O Notation

Famous quotes containing the words orders of, orders, common and/or functions:

    “There are nine orders of angels, to wit, angels, archangels, virtues, powers, principalities, dominations, thrones, cherubim, and seraphim.”
    —Gregory the Great, Pope (c. 540–604)

    “The receipt to make a speaker, and an applauded one too, is short and easy.—Take of common sense quantum sufficit, add a little application to the rules and orders of the House, throw obvious thoughts in a new light, and make up the whole with a large quantity of purity, correctness, and elegancy of style.”
    —Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)

    “There were none of the small deer up there; they are more common about the settlements. One ran into the city of Bangor two years before, and jumped through a window of costly plate glass, and then into a mirror, where it thought it recognized one of its kind.... This the inhabitants speak of as the deer that went a-shopping.”
    —Henry David Thoreau (1817–1862)

    “Adolescents, for all their self-involvement, are emerging from the self-centeredness of childhood. Their perception of other people has more depth. They are better equipped at appreciating others’ reasons for action, or the basis of others’ emotions. But this maturity functions in a piecemeal fashion. They show more understanding of their friends, but not of their teachers.”
    —Terri Apter (20th century)