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)

    “There is nothing on earth more exquisite than a bonny book, with well-placed columns of rich black writing in beautiful borders, and illuminated pictures cunningly inset. But nowadays, instead of looking at books, people read them. A book might as well be one of those orders for bacon and bran.”
    —George Bernard Shaw (1856–1950)

    “In all conversation between two persons, tacit reference is made, as to a third party, to a common nature. That third party or common nature is not social; it is impersonal; is God.”
    —Ralph Waldo Emerson (1803–1882)

    “Mark the babe
    Not long accustomed to this breathing world;
    One that hath barely learned to shape a smile,
    Though yet irrational of soul, to grasp
    With tiny finger—to let fall a tear;
    And, as the heavy cloud of sleep dissolves,
    To stretch his limbs, bemocking, as might seem,
    The outward functions of intelligent man.”
    —William Wordsworth (1770–1850)