Orders of Common Functions
Further information: Time complexity#Table of common time complexitiesHere 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  |
|
| 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:
“One cannot be a good historian of the outward, visible world without giving some thought to the hidden, private life of ordinary people; and on the other hand one cannot be a good historian of this inner life without taking into account outward events where these are relevant. They are two orders of fact which reflect each other, which are always linked and which sometimes provoke each other.”
—Victor Hugo (1802–1885)
“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)
“I will not adopt that ungenerous and impolitic custom so common with novel writers, of degrading by their contemptuous censure the very performances, to the number of which they are themselves adding—joining with their greatest enemies in bestowing the harshest epithets on such works, and scarcely ever permitting them to be read by their own heroine, who, if she accidentally take up a novel, is sure to turn over its insipid leaves with disgust.”
—Jane Austen (1775–1817)
“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)