Big O notation: Orders of common functions

constant Determining if a binary number is even or odd; Calculating 

; Using a constant-size lookup table

double logarithmic Number of comparisons spent 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

polylogarithmic Matrix chain ordering can be solved in polylogarithmic time on a parallel random-access machine.

fractional power Searching in a k-d tree
linear Finding an item in an unsorted list 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, or the union–find algorithm. Note that 

linearithmic, loglinear, quasilinear, or “n log n Performing a fast Fourier transform; Fastest possible comparison sort; heapsort and merge sort
quadratic Multiplying two n-digit numbers by a simple algorithm; simple sorting algorithms, such as bubble sort, selection sort and insertion sort; (worst case) bound on some usually faster sorting algorithms such as quicksort, Shellsort, and tree sort
polynomial or algebraic Tree-adjoining grammar parsing; maximum matching for bipartite graphs; finding the determinant with LU decomposition

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 travelling salesman problem via brute-force search; generating all unrestricted permutations of a poset; finding the determinant with Laplace expansion; enumerating all partitions of a set

Leave a Comment

Your email address will not be published.

7 + 16 =