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:
“Your moneys no good here. Orders of the house.”
—Stanley Kubrick (b. 1928)
“What is all wisdom save a collection of platitudes? Take fifty of our current proverbial sayingsthey are so trite, so threadbare, that we can hardly bring our lips to utter them. None the less they embody the concentrated experience of the race and the man who orders his life according to their teaching cannot go far wrong.”
—Norman Douglas (18681952)
“Nothing in the world can take the place of Persistence. Talent will not; nothing is more common than unsuccessful men with talent. Genius will not; unrewarded genius is almost a proverb. Education will not; the world is full of educated derelicts. Persistence and Determination alone are omnipotent. The slogan Press On, has solved and will always solve the problems of the human race.”
—Calvin Coolidge (18721933)
“When Western people train the mind, the focus is generally on the left hemisphere of the cortex, which is the portion of the brain that is concerned with words and numbers. We enhance the logical, bounded, linear functions of the mind. In the East, exercises of this sort are for the purpose of getting in tune with the unconsciousto get rid of boundaries, not to create them.”
—Edward T. Hall (b. 1914)