Table 2 Orders of cost functions for some common algorithms arranged by increasing dominance

O(1)           Algorithms that are independent of problem size. E.g.,
               the time to execute x[0]=0; does not depend on the size
               of the array x.

O(log(n))      Binary search in a sorted list.

O(n)           Algorithms that examine each item in a problem a
               relatively constant number of times. An example is
               linear search.

O(nlog(n))     Quicksort, Heapsort, Mergesort. The most efficient sorts
               based on comparisons are of this order.

O(n2)          Bubble sort, insertion sort, selection sort.

O(nk) for k>2  Multiplication of nxn matrices by the usual method is
               O(n3).

O(2n)          Algorithms that require the brute force examination of
               every possible subset of n items. Some bin packing
               algorithms fall into this class.

O(n!)          Finding the determinant of an nxn matrix by cofactors.
               Algorithms that require the examination of every
               permutation of a set of n objects. The traveling
               salesman problem falls into this class.