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:

    “Your money’s no good here. Orders of the house.”
    —Stanley Kubrick (b. 1928)

    “Really, if the lower orders don’t set us a good example, what on earth is the use of them? They seem, as a class, to have absolutely no sense of moral responsibility.”
    —Oscar Wilde (1854–1900)

    “... a nation to be strong, must be united; to be united, must be equal in condition; to be equal in condition, must be similar in habits and feeling; to be similar in habits and feeling, must be raised in national institutions as the children of a common family, and citizens of a common country.”
    —Frances Wright (1795–1852)

    “Nobody is so constituted as to be able to live everywhere and anywhere; and he who has great duties to perform, which lay claim to all his strength, has, in this respect, a very limited choice. The influence of climate upon the bodily functions ... extends so far, that a blunder in the choice of locality and climate is able not only to alienate a man from his actual duty, but also to withhold it from him altogether, so that he never even comes face to face with it.”
    —Friedrich Nietzsche (1844–1900)