# Problem Solving: Order of complexity

 ← Maths for big-O notation Order of complexity Limits of computation →

## Order of Complexity

Notation Name Example
${\displaystyle O(1)\,}$  constant Determining if a number is even or odd; using a constant-size lookup table
${\displaystyle O(\log n)\,}$  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.
${\displaystyle O(n)\,}$  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.
${\displaystyle O(n\log n)=O(\log n!)\,}$  linearithmic, loglinear, or quasilinear Performing a Fast Fourier transform; heapsort, quicksort (best and average case), or merge sort
${\displaystyle O(n^{2})\,}$  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
${\displaystyle O(n^{c}),\;c>1}$  polynomial or algebraic Tree-adjoining grammar parsing; maximum matching for bipartite graphs
${\displaystyle O(c^{n}),\;c>1}$  exponential Finding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search
${\displaystyle O(n!)\,}$  factorial Solving the travelling salesman problem via brute-force search; generating all unrestricted permutations of a poset; finding the determinant with expansion by minors.