Notation
Name
Example
O
(
1
)
{\displaystyle O(1)\,}
constant Determining if a number is even or odd; using a constant-size lookup table
O
(
log
n
)
{\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 .
O
(
n
)
{\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 .
O
(
n
log
n
)
=
O
(
log
n
!
)
{\displaystyle O(n\log n)=O(\log n!)\,}
linearithmic , loglinear, or quasilinearPerforming a Fast Fourier transform ; heapsort , quicksort (best and average case), or merge sort
O
(
n
2
)
{\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
O
(
n
c
)
,
c
>
1
{\displaystyle O(n^{c}),\;c>1}
polynomial or algebraicTree-adjoining grammar parsing; maximum matching for bipartite graphs
O
(
c
n
)
,
c
>
1
{\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
O
(
n
!
)
{\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 .
