constant | Determining if a binary number is even or odd; Calculating ; Using a constant-size | |
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 |
https://en.wikipedia.org/wiki/Big_O_notation