Editing Big O notation (section)

== Orders of common functions ==
{{Further|Time complexity#Table of common time complexities}}
{{redirect|O(1)|the quasicoherent sheaf|Proj construction#The twisting sheaf of Serre}}

Here is a list of classes of functions that are commonly encountered when analyzing the running time of an algorithm.  In each case, ''c'' is a positive constant and ''n'' increases without bound. The slower-growing functions are generally listed first.

{| class="wikitable"
|-
!Notation !! Name !! Example
|-
|<math>O(1)</math> || [[Constant time|constant]] || Finding the median value for a sorted array of numbers; Calculating <math>(-1)^n</math>; Using a constant-size [[lookup table]]
|-
|<math>O(\alpha (n))</math> || [[inverse Ackermann function]] || Amortized complexity per operation for the [[Disjoint-set data structure]]
|-


|<math>O(\log \log n)</math> || double logarithmic || Average number of comparisons spent finding an item using [[interpolation search]] in a sorted array of uniformly distributed values
|-
|<math>O(\log n)</math> || [[Logarithmic time|logarithmic]] || Finding an item in a sorted array with a [[Binary search algorithm|binary search]] or a balanced search [[Tree data structure|tree]] as well as all operations in a [[binomial heap]]
|-
|<math>O((\log n)^c)</math><br /><math display=inline> c>1</math> || [[Polylogarithmic time|polylogarithmic]] || Matrix chain ordering can be solved in polylogarithmic time on a [[parallel random-access machine]].
|-
|<math>O(n^c)</math><br /><math display=inline> 0<c<1</math> || fractional power || Searching in a [[k-d tree]]
|-
|<math>O(n)</math> || [[linear time|linear]] || Finding an item in an unsorted list or in an unsorted array; adding two ''n''-bit integers by [[Ripple carry adder|ripple carry]]
|-
|<math>O(n\log^* n)</math> || ''n'' [[log-star]] ''n'' || Performing [[Polygon triangulation|triangulation]] of a simple polygon using Seidel's algorithm,<ref>{{Citation |last=Seidel |first=Raimund |title=A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons |journal=[[Computational Geometry (journal)|Computational Geometry]] |volume=1 |pages=51–64 |year=1991 |citeseerx=10.1.1.55.5877 |doi=10.1016/0925-7721(91)90012-4 |author-link=Raimund Seidel |doi-access=free}}</ref> where <math>\log^*(n) =
\begin{cases}
 0, & \text{if }n \leq 1 \\
 1 + \log^*(\log n), & \text{if }n>1
\end{cases}</math>
|-
|<math>O(n\log n) = O(\log n!)</math> || [[Linearithmic time|linearithmic]], loglinear, quasilinear, or "''n'' log ''n''" || Performing a [[fast Fourier transform]]; fastest possible [[comparison sort]]; [[heapsort]] and [[merge sort]]
|-
|<math>O(n^2)</math> || [[quadratic time|quadratic]] || Multiplying two ''n''-digit numbers by [[Multiplication algorithm#Long multiplication|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]]
|-
|<math>O(n^c)</math> || [[polynomial time|polynomial]] or algebraic || [[Tree-adjoining grammar]] parsing; maximum [[Matching (graph theory)|matching]] for [[bipartite graph]]s; finding the [[determinant]] with [[LU decomposition]]
|-
|<math>L_n[\alpha,c] = e^{(c + o(1)) (\ln n)^\alpha (\ln \ln n)^{1-\alpha}}</math><br /><math display=inline> 0 < \alpha < 1</math> || [[L-notation]] or [[sub-exponential time|sub-exponential]] || Factoring a number using the [[quadratic sieve]] or [[General number field sieve|number field sieve]]
|-
|<math>O(c^n)</math><br/><math display=inline> c>1</math> || [[exponential time|exponential]] || Finding the (exact) solution to the [[travelling salesman problem]] using [[dynamic programming]]; determining if two logical statements are equivalent using [[brute-force search]]
|-
|<math>O(n!)</math> || [[factorial]] || Solving the [[travelling salesman problem]] via brute-force search; generating all unrestricted permutations of a [[Partially ordered set|poset]]; finding the [[determinant]] with [[Laplace expansion]]; enumerating [[Bell number|all partitions of a set]]
|}
The statement <math>f(n) = O(n!)</math> is sometimes weakened to <math>f(n) = O\left(n^n\right)</math> to derive simpler formulas for asymptotic complexity. For any <math>k>0</math> and {{nowrap|<math>c > 0</math>,}} <math>O(n^c(\log n)^k)</math> is a subset of <math>O(n^{c+\varepsilon})</math> for any {{nowrap|<math> \varepsilon > 0</math>,}} so may be considered as a polynomial with some bigger order.