Notation Name Example constant Finding the median value for a sorted array of numbers; Calculating ; Using a constant-size lookup table inverse Ackermann function Amortized complexity per operation for the Disjoint-set data structure double logarithmic Average 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, where 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 schoolbook multiplication; 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 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.
Notation Name Example constant Finding the median value for a sorted array of numbers; Calculating ; Using a constant-size lookup table inverse Ackermann function Amortized complexity per operation for the Disjoint-set data structure double logarithmic Average 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 where 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 schoolbook multiplication; 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 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