Big O notation

Template:Order-of-approx Big O notation is a mathematical notation that describes the approximate size of a function on a domain. Big O is a member of a family of notations invented by the German mathematicians Paul Bachmann^[1] and Edmund Landau^[2] and expanded by others, collectively called Bachmann–Landau notation. The letter O stands for Ordnung, that is, the order of approximation.

In computer science, big O notation is used to classify algorithms by how their run time or space requirements^{[lower-alpha 1]} grow with the input.^[3] In analytic number theory, big O notation expresses bounds on the growth of an arithmetical function, as for the remainder term in the prime number theorem.^[4] In mathematical analysis, including calculus, Big O notation bounds the error when truncating a power series and expresses the quality of approximation of a real or complex valued function by a simpler function.

Often, big O notation characterizes functions according to their growth rates as the variable becomes large: different functions with the same asymptotic growth rate may be represented using the same O notation. The letter O is used because the growth rate of a function is also referred to as the order of the function. A description of a function in terms of big O notation only provides an upper bound on the growth rate of the function.

Associated with big O notation are several related notations, using the symbols Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle o} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sim} , $\Omega$ , $\ll$ , $\gg$ , $\asymp$ , $\omega$ , and $\Theta$ to describe other kinds of bounds on growth rates.^[5]^[6]^[7]^[8]

Bachmann proposed the notation in 1894 and Landau extended it in 1909. An earlier notation was proposed by Paul du Bois-Reymond in 1870.^[9]

Formal definition

Let ${\textstyle f,}$ the function to be estimated, be either a real or complex valued function defined on a domain ${\textstyle D,}$ and let ${\textstyle g,}$ the comparison function, be a non-negative real valued function defined on the same set ${\textstyle D.}$ Common choices for the domain are intervals of real numbers, bounded or unbounded, the set of positive integers, the set of complex numbers and tuples of real/complex numbers. With the domain written explicitly or understood implicitly, one writes

f(x)=O{\bigl (}g(x){\bigr )}\

which is read as " ${\textstyle f(x)}$ is big ${\textstyle O}$ of ${\textstyle g(x)}$ " if there exists a positive real number ${\textstyle M}$ such that

\left|f(x)\right|\leq M\ g(x)\qquad ~{\mathsf {\ for\ all\ }}~\quad x\in D.

If $g(x)>0$ (i.e. $g$ is also never zero) throughout the domain $D,$ an equivalent definition is that the ratio ${\textstyle {\frac {f(x)}{g(x)}}}$ is bounded, i.e. there is a positive real number $M$ so that ${\textstyle {\Big |}{\frac {f(x)}{g(x)}}{\Big |}\leq M}$ for all $x\in D.$ These encompass all the uses of big ${\textstyle O}$ in computer science and mathematics, including its use where the domain is finite, infinite, real, complex, single variate, or multivariate. In most applications, one chooses the function $g(x)$ appearing within the argument of ${\textstyle O{\bigl (}\cdot {\bigr )}}$ to be as simple a form as possible, omitting constant factors and lower order terms. The number ${\textstyle M}$ is called the implied constant because it is normally not specified. When using big ${\textstyle O}$ notation, what matters is that some finite $M$ exists, not its specific value. This simplifies the presentation of many analytic inequalities.

For functions defined on positive real numbers or positive integers, a more restrictive and somewhat conflicting definition is still in common use,^[3]^[10] especially in computer science. When restricted to functions which are eventually positive, the notation

f(x)=O{\bigl (}g(x){\bigr )}\qquad ~{\mathsf {as}}\quad x\to \infty

means that for some real number ${\textstyle a,}$ ${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$ in the domain ${\textstyle \left[a,\infty \right).}$ Here, the expression ${\textstyle x\to \infty }$ does not indicate a limit, but the notion that the inequality holds for large enough ${\textstyle x.}$ The expression ${\textstyle x\to \infty }$ often is omitted.^[3]

Similarly, for a real number ${\textstyle a,}$ the notation

f(x)=O{\bigl (}g(x){\bigr )}\qquad ~{\text{ as }}\ x\to a

means that for some constant ${\textstyle c>0,}$ ${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$ on the interval $\left[a-c,a+c\right];$ that is, in a small neighborhood of $a.$ In addition, the notation $\ f(x)=h(x)+O{\bigl (}g(x){\bigr )}\$ means ${\textstyle f(x)-h(x)=O{\bigl (}g(x){\bigr )}.}$ More complicated expressions are also possible.

Despite the presence of the equal sign ( $=$ ) as written, the expression ${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$ does not refer to an equality, but rather to an inequality relating ${\textstyle f}$ and ${\textstyle g.}$

In the 1930s,^[6] the Russian number theorist I.M. Vinogradov introduced the notation $\ll ,$ which has been increasingly used in number theory^[4]^[11]^[12] and other branches of mathematics, as an alternative to the ${\textstyle O}$ notation. We have

\ f\ll g\iff f=O{\bigl (}g{\bigr )}.

Frequently both notations are used in the same work.

Set version of big O

In computer science^[3] it is common to define big ${\textstyle O}$ as also defining a set of functions. With the positive (or non-negative) function $g(x)$ specified, one interprets ${\textstyle O{\bigl (}g(x){\bigr )}}$ as representing the set of all functions ${\textstyle {\tilde {f}}}$ that satisfy ${\textstyle {\tilde {f}}(x)=O{\bigl (}g(x){\bigr )}.}$ One can then equivalently write ${\textstyle f(x)\in O{\bigl (}g(x){\bigr )},}$ read as "the function ${\textstyle \ f(x)\ }$ is among the set of all functions of order at most ${\textstyle g(x).}$ "

Examples with an infinite domain

In typical usage the $O$ notation is applied to an infinite interval of real numbers $[a,\infty )$ and captures the behavior of the function for very large $x$ . In this setting, the contribution of the terms that grow "most quickly" will eventually make the other ones irrelevant. As a result, the following simplification rules can be applied:

If $f(x)$ is a sum of several terms, if there is one with largest growth rate, it can be kept, and all others omitted.
If $f(x)$ is a product of several factors, any constants (factors in the product that do not depend on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x } ) can be omitted.

For example, let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=6x^4-2x^3+5 } , and suppose we wish to simplify this function, using Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O } notation, to describe its growth rate for large Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x } . This function is the sum of three terms: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 6x^4 } , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -2x^3 } , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5 } . Of these three terms, the one with the highest growth rate is the one with the largest exponent as a function of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x } , namely Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 6x^4 } . Now one may apply the second rule: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 6x^4 } is a product of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 6 } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^4 } in which the first factor does not depend on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x } . Omitting this factor results in the simplified form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^4 } . Thus, we say that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) } is a "big O" of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^4 } . Mathematically, we can write Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=O(x^4) } for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\ge 1} . One may confirm this calculation using the formal definition: let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=6x^4-2x^3+5 } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x)=x^4 } . Applying the formal definition from above, the statement that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=O(x^4) } is equivalent to its expansion, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |f(x)| \le M x^4 } for some suitable choice of a positive real number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M } and for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \ge 1 } . To prove this, let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M=13 } . Then, for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\ge 1 } : Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} |6x^4 - 2x^3 + 5| &\le 6x^4 + |-2x^3| + 5\\ &\le 6x^4 + 2x^4 + 5x^4\\ &= 13x^4 \end{align}} so Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |6x^4 - 2x^3 + 5| \le 13 x^4 .} While it is also true, by the same argument, that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=O(x^{10})} , this is a less precise approximation of the function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} . On the other hand, the statement Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=O(x^3)} is false, because the term Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 6x^4} causes Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)/x^3 } to be unbounded.

When a function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(n) } describes the number of steps required in an algorithm with input Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , an expression such as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(n)=O(n^2) } with the implied domain being the set of positive integers, may be interpreted as saying that the algorithm has at most the order of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2} time complexity.

Example with a finite domain

Big O can also be used to describe the error term in an approximation to a mathematical function on a finite interval. The most significant terms are written explicitly, and then the least-significant terms are summarized in a single big O term. Consider, for example, the exponential series and two expressions of it that are valid when Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} is small: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} e^x &= 1 + x + \frac{\; x^2\ } {2! }+\frac{\; x^3\ }{3!}+\frac{\; x^4\ }{4!} + \dotsb && \text{ for all finite } x\\[4pt] &= 1 + x + \frac{\; x^2\ }{ 2 }+O(|x|^3) && \text{ for all } |x|\le 1 \\[4pt] &= 1 + x + O(x^2) && \text{ for all } |x|\le 1. \end{align}} The middle expression (the line with "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(|x^3|)} ") means the absolute-value of the error Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ e^x- (1 + x + \frac{\; x^2\ }{2} )\ } is at most some constant times Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ~ |x^3|\ } when Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x ~} is small. This is an example of the use of Taylor's theorem.

The behavior of a given function may be very different on finite domains than on infinite domains, for example, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x+1)^8 = x^8 + O(x^7) \quad \text{ for } x\ge 1 } while Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x+1)^8 = 1 + 8x + O(x^2) \quad \text{ for } |x|\le 1. }

Multivariate examples

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \sin y = O(x) \quad \text{ for }x\ge 1,y\text{ any real number} }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3a^2+7ab+2b^2+a+3b+14 \ll a^2+b^2 \ll a^2 \quad \text{ for all } a\ge b\ge 1 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{xy}{x^2+y^2} = O(1) \quad \text{ for all real } x,y \text{ that are not both } 0 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{it} = O(1) \quad \text{ for } x\ne 0,t\in \mathbb{R}. }

Here we have a complex variable function of two variables. In general, any bounded function is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1) } .

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x+y)^{10} = O(x^{10}) \quad \text{ for }x\ge 1, -2\le y\le 2. }

The last example illustrates a mixing of finite and infinite domains on the different variables.

In all of these examples, the bound is uniform in both variables. Sometimes in a multivariate expression, one variable is more important than others, and one may express that the implied constant Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} depends on one or more of the variables using subscripts to the big O symbol or the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ll} symbol. For example, consider the expression

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1+x)^b = 1 + O_b(x) \quad \text{ for } 0 \le x\le 1, b\text{ any real number.} }

This means that for each real number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} , there is a constant Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_b} , which depends on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} , so that for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0\le x\le 1} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |(1+x)^b-1| \le M_b \cdot x. } This particular statement follows from the general binomial theorem.

Another example, common in the theory of Taylor series, is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e^x = 1 + x + O_r(x^2) \quad \text{ for all } |x|\le r, r\text{ being any real number.} } Here the implied constant depends on the size of the domain.

The subscript convention applies to all of the other notations in this page.

Properties

Product

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_1 = O(g_1) \text{ and } f_2 = O(g_2) \Rightarrow f_1 f_2 = O(g_1 g_2)}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\cdot O(g) = O(|f| g)}

Sum

If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_1 = O(g_1)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_2= O(g_2) } then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_1 + f_2 = O(\max(g_1, g_2))} . It follows that if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_1 = O(g) } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_2 = O(g)} then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_1+f_2 = O(g) } .

Multiplication by a constant

Let $k$ be a nonzero constant. Then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(|k| \cdot g) = O(g)} . In other words, if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f = O(g)} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \cdot f = O(g). }

Transitive property

If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f=O(g)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g=O(h) } then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f=O(h) } .

If the function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} of a positive integer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} can be written as a finite sum of other functions, then the fastest growing one determines the order of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)} . For example,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = 9 \log n + 5 (\log n)^4 + 3n^2 + 2n^3 = O(n^3) \qquad\text{for } n\ge 1 .}

Some general rules about growth toward infinity; the 2nd and 3rd property below can be proved rigorously using L'Hôpital's rule:

Large powers dominate small powers

For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b\ge a} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^a = O(n^b) } as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \to \infty } .

Powers dominate logarithms

For any positive Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a,b, } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\log n)^a = O_{a,b}(n^b), } no matter how large Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} is and how small $b$ is. Here, the implied constant depends on both $a$ and $b$ .

Exponentials dominate powers

For any positive $a,b,$ $n^{a}=O_{a,b}(e^{bn}),$ no matter how large $a$ is and how small $b$ is.

A function that grows faster than $n^{c}$ for any $c$ is called superpolynomial. One that grows more slowly than any exponential function of the form $c^{n}$ with $c>1$ is called subexponential. An algorithm can require time that is both superpolynomial and subexponential; examples of this include the fastest known algorithms for integer factorization and the function $n^{\log n}$ .

We may ignore any powers of $n$ inside of the logarithms. For any positive $c$ , the notation $O(\log n)$ means exactly the same thing as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\log (n^c))} , since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log(n^c)=c\log n} . Similarly, logs with different constant bases are equivalent with respect to Big O notation. On the other hand, exponentials with different bases are not of the same order. For example, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^n } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3^n } are not of the same order.

More complicated expressions

In more complicated usage, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\cdot) } can appear in different places in an equation, even several times on each side. For example, the following are true for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } a positive integer: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} (n+1)^2 & = n^2 + O(n), \\ (n + O(n^{1/2})) \cdot (n + O(\log n))^2 & = n^3 + O(n^{5/2}), \\ n^{O(1)} & = O(e^n). \end{align}} The meaning of such statements is as follows: for any functions which satisfy each Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\cdot) } on the left side, there are some functions satisfying each Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\cdot) } on the right side, such that substituting all these functions into the equation makes the two sides equal. For example, the third equation above means: "For any function satisfying Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)=O(1)} , there is some function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(n)=O(e^n) } such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{f(n)}=g(n) } ". The implied constant in the statement "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(n)=O(e^n) } " may depend on the implied constant in the expression "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)=O(1)} ".

Some further examples: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} f=O(g)\; &\Rightarrow\; \int_a^b f = O\bigg( \int_a^b g \bigg) \\ f(x)=g(x)+O(1)\; &\Rightarrow\; e^{f(x)}=O(e^{g(x)}) \\ (1+O(1/x))^{O(x)} &= O(1) \quad \text{ for } x>0\\ \sin x &= O(|x|) \quad \text{ for all real } x. \end{align} }

Vinogradov's ≫ and Knuth's big Ω

When Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f, g} are both positive functions, Vinogradov^[6] introduced the notation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) \gg g(x) } , which means the same as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x) = O(f(x)) } . Vinogradov's two notations enjoy visual symmetry, as for positive functions Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f,g } , we have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) \ll g(x) \Longleftrightarrow g(x) \gg f(x). }

In 1976, Donald Knuth^[8] defined

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=\Omega(g(x))\Longleftrightarrow g(x)=O(f(x))}

which has the same meaning as Vinogradov's Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) \gg g(x) } .

However, much earlier, Hardy and Littlewood^[7] had defined Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega } differently, and their notation enjoys widespread use today in analytic number theory.^[13]^[11]^[12] Justifying his use of the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega} -symbol to describe a stronger property,^[8] Knuth wrote: "For all the applications I have seen so far in computer science, a stronger requirement ... is much more appropriate". Knuth further wrote, "Although I have changed Hardy and Littlewood's definition of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega} , I feel justified in doing so because their definition is by no means in wide use, and because there are other ways to say what they want to say in the comparatively rare cases when their definition applies."^[8] Knuth's big Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega } enjoys widespread use today in computer science and combinatorics.

Hardy's ≍ and Knuth's big Θ

In analytic number theory,^[12] the notation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) \asymp g(x) } means both Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=O(g(x)) } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x)=O(f(x)) } . This notation is originally due to Hardy.^[5] Knuth's notation for the same notion is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = \Theta(g(x)) } .^[8] Roughly speaking, these statements assert that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x) } have the same order. These notations mean that there are positive constants Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M,N } so that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N g(x) \le f(x) \le M g(x) } for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x } in the common domain of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f,g } . When the functions are defined on the positive integers or positive real numbers, as with big O, writers oftentimes interpret statements Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = \Omega(g(x)) } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=\Theta(g(x)) } as holding for all sufficiently large Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x } , that is, for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} beyond some point Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0 } . Sometimes this is indicated by appending Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\to\infty } to the statement. For example, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2n^2 - 10n = \Theta(n^2) } is true for the domain Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\ge 6 } but false if the domain is all positive integers, since the function is zero at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=5 } .

Further examples

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^3 + 20n^2 +n+12 \asymp n^3 \quad \text{ for all } n\ge 1. }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1+x)^8 = x^8 + \Theta(x^7) \quad \text{ for all } x\ge 1. }

The notation

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = e^{\Omega(n)} \quad \text{ for all } n\ge 1, } means that there is a positive constant Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M } so that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) \ge e^{Mn} } for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\ge 1} . By contrast, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = e^{-O(n)} \quad \text{ for all } n\ge 1, } means that there is a positive constant Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M } so that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) \ge e^{-Mn} } for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\ge 1} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = e^{\Theta(n)} \quad \text{ for all } n\ge 1, } means that there are positive constants Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M,N } so that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e^{M n} \le f(n) \le e^{N n} } for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\ge 1} .

For any domain Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = g(x)+O(1) \Longleftrightarrow e^{f(x)} \asymp e^{g(x)}, } each statement being for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} .

Orders of common functions

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.

Notation	Name	Example
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)}	constant	Finding the median value for a sorted array of numbers; Calculating Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (-1)^n} ; Using a constant-size lookup table
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\alpha (n))}	inverse Ackermann function	Amortized complexity per operation for the Disjoint-set data structure
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\log \log n)}	double logarithmic	Average number of comparisons spent finding an item using interpolation search in a sorted array of uniformly distributed values
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O((\log n)^c)} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle c>1}	polylogarithmic	Matrix chain ordering can be solved in polylogarithmic time on a parallel random-access machine.
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^c)} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 0<c<1}	fractional power	Searching in a k-d tree Trial division naive primality testing (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\sqrt{n})} )
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)}	linear	Finding an item in an unsorted list or in an unsorted array; adding two n-bit integers by ripple carry
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n\log^* n)}	n log-star n	Performing triangulation of a simple polygon using Seidel's algorithm,^[14] where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log^(n) = \begin{cases} 0, & \text{if }n \leq 1 \\ 1 + \log^(\log n), & \text{if }n>1 \end{cases}}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n\log n) = O(\log n!)}	linearithmic, loglinear, quasilinear, or "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\log n} "	Performing a fast Fourier transform; fastest possible comparison sort; heapsort and merge sort
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^2)}	quadratic	Multiplying two Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} -digit numbers by 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
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^c)}	polynomial or algebraic	Tree-adjoining grammar parsing; maximum matching for bipartite graphs; finding the determinant with LU decomposition
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_n[\alpha,c] = e^{(c + o(1)) (\ln n)^\alpha (\ln \ln n)^{1-\alpha}}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 0 < \alpha < 1}	L-notation or sub-exponential	Factoring a number using the quadratic sieve or number field sieve
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(c^n)} ${\textstyle 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!)$	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

The statement $f(n)=O(n!)$ is sometimes weakened to $f(n)=O\left(n^{n}\right)$ to derive simpler formulas for asymptotic complexity. In many of these examples, the running time is actually $\Theta (g(n))$ , which conveys more precision.

Little-o notation

For real or complex-valued functions of a real variable $x$ with $g(x)>0$ for sufficiently large $x$ , one writes ^[2]

f(x)=o(g(x))\quad {\text{ as }}x\to \infty

if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{x\to\infty} \frac{f(x)}{g(x)} = 0. } That is, for every positive constant $ε$ there exists a constant Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0} such that

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |f(x)| \leq \varepsilon g(x) \quad \text{ for all } x \geq x_0.}

Intuitively, this means that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x)} grows much faster than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} , or equivalently Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} grows much slower than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x)} . For example, one has

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 200x = o(x^2)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/x = o(1),} both as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \to \infty .}

When one is interested in the behavior of a function for large values of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} , little-o notation makes a stronger statement than the corresponding big-O notation: every function that is little-o of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} is also big-O of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} on some interval Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [a,\infty)} , but not every function that is big-O of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} is little-o of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} . For example, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2x^2 = O(x^2) } but Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2x^2 \neq o(x^2)} for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\ge 1} .

Little-o respects a number of arithmetic operations. For example,

if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} is a nonzero constant and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f = o(g)} then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c \cdot f = o(g)} , and

if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f = o(F)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g = o(G)} then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f \cdot g = o(F \cdot G).}

if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f = o(F)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g = o(G)} then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f+g=o(F+G)}

It also satisfies a transitivity relation:

if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f = o(g)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g = o(h)} then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f = o(h).}

Little-o can also be generalized to the finite case:^[2] Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = o(g(x)) \quad \text{ as } x \to x_0} if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{x\to x_0} \frac{f(x)}{g(x)} = 0. } In other words, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = \alpha(x)g(x)} for some Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha(x)} with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{x\to x_0} \alpha(x) = 0} .

This definition is especially useful in the computation of limits using Taylor series. For example:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sin x = x - \frac{x^3}{3!} + \ldots = x + o(x^2) \text{ as } x\to 0} , so Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{x\to 0}\frac{\sin x}x = \lim_{x\to 0} \frac{x + o(x^2)}{x} = \lim_{x\to 0} 1 + o(x) = 1}

Asymptotic notation

A relation related to little-o is the asymptotic notation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sim} . For real valued functions Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f,g} , the expression Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) \sim g(x)\quad \text{ as }x\to\infty} means Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{x\to\infty} \frac{f(x)}{g(x)}=1.} One can connect this to little-o by observing that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) \sim g(x) } is also equivalent to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = (1+o(1)) g(x) } . Here Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle o(1)} refers to a function tending to zero as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\to\infty} . One reads this as "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} is asymptotic to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x)} ". For nonzero functions on the same (finite or infinite) domain, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sim } forms an equivalence relation.

One of the most famous theorems using the notation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sim} is Stirling's formula Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n! \sim \bigg(\frac{n}{e}\bigg)^n \sqrt{2\pi n} \quad \text{ as }n\to\infty. } In number theory, the famous prime number theorem states that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi(x) \sim \frac{x}{\log x} \quad \text{ as }x\to\infty, } where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi(x)} is the number of primes which are at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log} is the natural logarithm of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} .

As with little-o, there is a version with finite limits (two-sided or one-sided) as well, for example Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sin x \sim x \quad \text{ as }x\to 0. }

Further examples: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^a=o_{a,b} (e^{bx}) \quad \text{ as }x\to\infty, \text{ for any positive constants }a,b, } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=g(x)+o(1) \quad \Longleftrightarrow\quad e^{f(x)}\sim e^{g(x)} \quad (x\to\infty). } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{n=1}^\infty \frac{1}{n^s} \sim \frac{1}{s-1}\quad (s\to1^+). } The last asymptotic is a basic property of the Riemann zeta function.

Knuth's little 𝜔

For eventually positive, real valued functions Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f, g,} the notation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = \omega(g(x)) \quad \text{ as } x\to\infty } means Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{x\to\infty} \frac{f(x)}{g(x)} = \infty. } In other words, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x)=o(f(x)) } . Roughly speaking, this means that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} grows much faster than does Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x)} .

The Hardy–Littlewood Ω notation

In 1914 G. H. Hardy and J. E. Littlewood introduced the new symbol Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \Omega,} ^[7] which is defined as follows:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = \Omega(g(x)) \quad } as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \quad x \to \infty \quad} if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \quad \limsup_{x \to \infty}\ \left|\frac{\ f(x)\ }{ g(x) }\right| > 0 ~.}

Thus Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ~ f(x) = \Omega(g(x)) ~} is the negation of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ~ f(x) = o(g(x)) ~.}

In 1916 the same authors introduced the two new symbols Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \Omega_R\ } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \Omega_L\ ,} defined as:^[15]

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = \Omega_R(g(x)) \quad} as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \quad x \to \infty \quad} if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \quad \limsup_{x \to \infty}\ \frac{\ f(x)\ }{ g(x) } > 0\ ;}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=\Omega_L(g(x)) \quad} as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \quad x \to \infty \quad} if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \quad ~ \liminf_{x \to \infty}\ \frac{\ f(x)\ }{ g(x) }< 0 ~.}

These symbols were used by E. Landau, with the same meanings, in 1924.^[16] Authors that followed Landau, however, use a different notation for the same definitions:^[11] The symbol Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \Omega_R\ } has been replaced by the current notation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \Omega_{+}\ } with the same definition, and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \Omega_L\ } became Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \Omega_{-} ~.}

These three symbols Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \Omega\ , \Omega_{+}\ , \Omega_{-}\ ,} as well as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(x) = \Omega_{\pm}(g(x))\ } (meaning that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(x) = \Omega_{+}(g(x))\ } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(x) = \Omega_{-}(g(x))\ } are both satisfied), are now currently used in analytic number theory.^[11]^[12]

Simple examples

We have

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sin x = \Omega(1) \quad} as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \quad x \to \infty\ ,}

and more precisely

\sin x=\Omega _{\pm }(1)\quad

as

\quad x\to \infty ,~

where $\Omega _{\pm }$ means that the left side is both $\Omega _{+}(1)$ and $\Omega _{-}(1)$ ,

We have

1+\sin x=\Omega (1)\quad

as

\quad x\to \infty \ ,

and more precisely

1+\sin x=\Omega _{+}(1)\quad

as

\quad x\to \infty \ ;

however

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 + \sin x \ne \Omega_{-}(1) \quad} as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \quad x \to \infty ~.}

Family of Bachmann–Landau notations

For understanding the formal definitions, consult the list of logic symbols used in mathematics.

Notation	Name^[8]	Description	Formal definition	Compact definition ^[4] ^[5] ^[8] ^[7] ^[17]^[18]
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = O(g(n))} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) \ll g(n) } (Vinogradov's notation)	Big O; Big Oh; Big Omicron^[8]^{[lower-alpha 2]}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \|f\|} is bounded above by $g$ (up to constant factor Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} )	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \exists k > 0 \, \forall n\in D\colon \|f(n)\| \leq k\, g(n)}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sup_{n \in D} \frac{\left\|f(n)\right\|}{g(n)} < \infty}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = o(g(n))}	Small O; Small Oh; Little O; Little Oh	$f$ is dominated by $g$ asymptotically (for any constant factor Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} )	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall k>0 \, \exists n_0 \, \forall n > n_0\colon \|f(n)\| \leq k\, g(n)}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = \Omega(g(n))}	Big Omega in number theory (Hardy–Littlewood)	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \|f\|} is not dominated by $g$ asymptotically	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \exists k>0 \, \forall n_0 \, \exists n > n_0\colon \|f(n)\| \geq k\, g(n)}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \limsup_{n \to \infty} \frac{\|f(n)\|}{g(n)} > 0 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = \Omega_+(g(n))}	Omega plus (Hardy–Littlewood)	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} is not dominated by $g$ asymptotically	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \exists k>0 \, \forall n_0 \, \exists n > n_0\colon f(n) \geq k\, g(n)}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \limsup_{n \to \infty} \frac{f(n)}{g(n)} > 0 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = \Omega_-(g(n))}	Omega minus (Hardy–Littlewood)	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -f} is not dominated by $g$ asymptotically	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \exists k>0 \, \forall n_0 \, \exists n > n_0\colon -f(n) \geq k\, g(n)}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \limsup_{n \to \infty} \frac{-f(n)}{g(n)} > 0 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = \Omega_\pm(g(n))}	Omega plus and minus	neither Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} nor Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -f} is dominated by $g$ asymptotically	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)=\Omega_+(g(n))} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)=\Omega_-(g(n))}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) \asymp g(n)} (Hardy's notation) or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = \Theta(g(n))} (Knuth notation)	Of the same order as (Hardy); Big Theta (Knuth)	$f$ is bounded by $g$ both above (with constant factor Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k_2} ) and below (with constant factor Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k_1} )	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \exists k_1 > 0 \, \exists k_2>0 \, \forall n\in D\colon} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k_1 \, g(n) \leq f(n) \leq k_2 \, g(n)}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = O(g(n))} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(n) = O(f(n))}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)\sim g(n)} as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\to a } , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a } is finite, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \infty} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -\infty }	Asymptotic equivalence	$f$ is equal to $g$ asymptotically	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall \varepsilon > 0 \, \exists n_0 \, \forall n > n_0\colon \left\| \frac{f(n)}{g(n)} - 1 \right\| < \varepsilon} (in the case Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a=\infty} )	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{n \to a} \frac{f(n)}{g(n)} = 1}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = \Omega(g(n))} (Knuth's notation), or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) \gg g(n) } (Vinogradov's notation)	Big Omega in complexity theory (Knuth)	$f$ is bounded below by $g$ , up to a constant factor	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \exists k > 0 \, \forall n\in D\colon f(n) \geq k\, g(n)}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \inf_{n \in D} \frac{f(n)}{g(n)} > 0 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = \omega(g(n))} as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\to a} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} can be finite, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \infty} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -\infty}	Small Omega; Little Omega	$f$ dominates $g$ asymptotically	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall k > 0 \, \exists n_0 \, \forall n > n_0 \colon f(n) > k\, g(n)} (for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a=\infty} )	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{n \to a} \frac{f(n)}{g(n)} = \infty}

The limit definitions assume Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(n) > 0} for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} in a neighborhood of the limit; when the limit is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \infty} , this means that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(n)>0} for sufficiently large Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .

Computer science and combinatorics use the big Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O } , big Theta Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Theta } , little Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle o } , little omega Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega } and Knuth's big Omega Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega } notations. ^[3] Analytic number theory often uses the big Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O } , small Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle o } , Hardy's Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \asymp} , Hardy–Littlewood's big Omega Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega } (with or without the +, − or ± subscripts), Vinogradov's Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ll} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gg} notations and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sim} notations. ^[11] ^[4] ^[12] The small omega Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega } notation is not used as often in analysis or in number theory. ^[19]

Quality of approximations using different notation

Informally, especially in computer science, the big Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O} notation often can be used somewhat differently to describe an asymptotic tight bound where using big Theta Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Theta} notation might be more factually appropriate in a given context .^[20] For example, when considering a function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(n)=73n^3+22n^2+58} , all of the following are generally acceptable, but tighter bounds (such as numbers 2,3 and 4 below) are usually strongly preferred over looser bounds (such as number 1 below).

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(n)=O(n^{100})}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(n)=O(n^{3})}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(n)=\Theta(n^3)}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(n)\sim 73n^3} as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\to\infty} .

While all three statements are true, progressively more information is contained in each. In some fields, however, the big O notation (number 2 in the lists above) would be used more commonly than the big Theta notation (items numbered 3 in the lists above). For example, if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(n)} represents the running time of a newly developed algorithm for input size Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , the inventors and users of the algorithm might be more inclined to put an upper bound on how long it will take to run without making an explicit statement about the lower bound or asymptotic behavior.

Extensions to the Bachmann–Landau notations

Another notation sometimes used in computer science is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde{O}} (read soft-O), which hides polylogarithmic factors. There are two definitions in use: some authors use Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = \tilde{O}(g(n))} as shorthand for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)=O(g(n)\log^k n) } for some Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} ^{[citation needed]}, while others use it as shorthand for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)=O(g(n)\log^k g(n)) } .^[21] When $g(n)$ is polynomial in $n$ , there is no difference; however, the latter definition allows one to say, e.g. that $n2^{n}={\tilde {O}}(2^{n})$ while the former definition allows for $\log ^{k}n={\tilde {O}}(1)$ for any constant $k$ . Some authors write O^* for the same purpose as the latter definition.^[22] Essentially, it is less precise version of the big O notation, ignoring logarithmic factors in the growth-rate of the function. Since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log^k n = o(n^\varepsilon)} for any constant Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} and any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varepsilon>0} , logarithmic factors are far less significant than powers of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } and even more insignificant compared with exponentials.

Also, the L notation, defined as

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_n[\alpha,c] = e^{(c + o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}},}

is convenient for functions that are between polynomial and exponential in terms of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log n} .

Generalizations and related usages

The generalization to functions taking values in any normed vector space is straightforward (replacing absolute values by norms), where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} need not take their values in the same space. A generalization to functions Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} taking values in any topological group is also possible^{[citation needed]}. The "limiting process" Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\to x_0} can also be generalized by introducing an arbitrary filter base, i.e. to directed nets Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} . The Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle o} notation can be used to define derivatives and differentiability in quite general spaces, and also (asymptotical) equivalence of functions,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\sim g \iff (f-g) \in o(g) }

which is an equivalence relation and a more restrictive notion than the relationship "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Theta(g)} " from above. (It reduces to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim f/g = 1} if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} are positive real valued functions.) For example, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2x=\Theta(x)} is, but Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2x-x \ne o(x) } .

History

In 1870, Paul du Bois-Reymond ^[9] defined Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) \succ \phi(x) } , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) \sim \phi(x) } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) \prec \phi(x)} to mean, respectively, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{x\to\infty}\frac{f(x)}{\phi(x)}=\infty, \quad \lim_{x\to\infty}\frac{f(x)}{\phi(x)}>0, \quad \lim_{x\to\infty}\frac{f(x)}{\phi(x)}=0. } These were not widely adopted and are not used today. The first and third are symmetric: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) \prec \phi(x)} means the same as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(x) \succ f(x)} . Landau later adopted Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sim } with the narrower definition that the limit of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)/\phi(x)} equals 1.

The symbol O was first introduced by the number theorist Paul Bachmann in 1894, in the second volume of his book Analytische Zahlentheorie ("analytic number theory").^[1] The number theorist Edmund Landau adopted it, and was thus inspired to introduce in 1909 the notation o;^[2] hence both are now called Landau symbols. These notations were used in applied mathematics during the 1950s for asymptotic analysis.^[23] The symbol Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega} (in the sense "is not little o of") was introduced in 1914 by Hardy and Littlewood.^[7] Hardy and Littlewood also introduced in 1916 the left and right Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega} symbols Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega_R} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega_L} (now commonly denoted Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega_+, \Omega_-} ).^[15] This Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega} notation has been commonly used in number theory since the 1950s.^[13]

Hardy introduced the symbols Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \preccurlyeq } and advocated for Bois-Reymond's Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \prec } (as well as the already mentioned other symbols) in his 1910 tract "Orders of Infinity",^[5] but made use of them only in three papers (1910–1913). In his nearly 400 remaining papers and books he consistently used the Landau symbols O and o.^[24] Hardy's symbols Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \preccurlyeq} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbin{\,\asymp\;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-}} are not used any more.

The symbol Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sim} , although it had been used before with different meanings,^[9] was given its modern definition by Landau in 1909^[2] and by Hardy in 1910.^[5] On the same page, Hardy defined the symbol Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \asymp} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)\asymp g(x)} means that both Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=O(g(x))} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x)=O(f(x))} are satisfied. The notation is still used in analytic number theory.^[25] ^[12] Hardy also proposed the symbol Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbin{\,\asymp\;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-}} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f \mathbin{\,\asymp\;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} g} means that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\sim Kg } for some constant Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K\not=0} (this corresponds to Bois-Reymond's notation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\sim g} ).

In the 1930s, Vinogradov^[6] popularized the notation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) \ll g(x) } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x) \gg f(x)} , both of which mean Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=O(g(x)) } . This notation became standard in analytic number theory.^[4]

In the 1970s, big O was popularized in computer science by Donald Knuth, who proposed the different notation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=\Theta(g(x))} for Hardy's Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)\asymp g(x)} , and proposed a different definition for the Hardy and Littlewood Omega notation.^[8]

Matters of notation

Arrows

In mathematics, an expression such as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\to\infty } indicates the presence of a limit. In big-O notation and related notations Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega, \Theta, \gg, \ll, \asymp} , there is no implied limit, in contrast with little-o, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sim} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega} notations. Notation such as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=O(g(x)) \;\; (x\to\infty)} can be considered an abuse of notation.

Equals sign

Some consider Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=O(g(x))} to also be an abuse of notation, since the use of the equals sign could be misleading as it suggests a symmetry that this statement does not have. As de Bruijn says, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(x)=O(x^2)} is true but Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(x^2)=O(x)} is not.^[26] Knuth describes such statements as "one-way equalities", since if the sides could be reversed, "we could deduce ridiculous things like Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=n^2} from the identities Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=O(n^2)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2=O(n^2) } .^[27] In another letter, Knuth also pointed out that^[28]

the equality sign is not symmetric with respect to such notations [as, in this notation,] mathematicians customarily use the '=' sign as they use the word 'is' in English: Aristotle is a man, but a man isn't necessarily Aristotle.

For these reasons, some advocate for using set notation and write Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) \in O(g(x)) } , read as "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} is an element of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(g(x))} ", or "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} is in the set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(g(x))} " – thinking of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(g(x))} as the class of all functions Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h(x)} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h(x)=O(g(x))} .^[27] However, the use of the equals sign is customary.^[26]^[27] and is more convenient in more complex expressions of the form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = g(x) + O(h(x)) = O(k(x)). }

The Vinogradov notations Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ll} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gg} , which are widely used in number theory ^[11] ^[4] ^[12] do not suffer from this defect, as they more clearly indicate that big-O indicates an inequality rather than an equality. They also enjoy a symmetry that big-O notation lacks: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)\ll g(x)} means the same as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x)\gg f(x)} . In combinatorics and computer science, these notations are rarely seen.^[3]

Typesetting

Big O is typeset as an italicized uppercase " $O$ ", as in the following example: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^2)} .^[29]^[30] In TeX, it is produced by simply typing 'O' inside math mode. Unlike Greek-named Bachmann–Landau notations, it needs no special symbol. However, some authors use the calligraphic variant Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{O}} instead.^[31]^[32]

The big-O originally stands for "order of" ("Ordnung", Bachmann 1894), and is thus a Latin letter. Neither Bachmann nor Landau ever call it "Omicron". The symbol was much later on (1976) viewed by Knuth as a capital omicron,^[8] probably in reference to his definition of the symbol Omega. The digit zero should not be used.

References and notes

↑ ^1.0 ^1.1 Bachmann, Paul (1894). Analytische Zahlentheorie [Analytic Number Theory] (in German). 2. Leipzig: Teubner.
↑ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 Landau, Edmund (1909). Handbuch der Lehre von der Verteilung der Primzahlen [Handbook on the theory of the distribution of the primes] (in German). Leipzig: B.G. Teubner; reprinted as two volumes in one by Chelsea, 1974, with an appendix by Dr. Paul T. Bateman. pp. 59–63.
↑ ^3.0 ^3.1 ^3.2 ^3.3 ^3.4 ^3.5 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). "Characterizing running times". Introduction to Algorithms (4th ed.). MIT Press and McGraw-Hill. ISBN 978-0-262-53091-0.
↑ ^4.0 ^4.1 ^4.2 ^4.3 ^4.4 ^4.5 Iwaniec, Henryk; Kowalski, Emmanuel (2004). Analytic Number Theory. American Mathematical Society.
↑ ^5.0 ^5.1 ^5.2 ^5.3 ^5.4 Hardy, G. H. (1910). Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond. Cambridge University Press. p. 2.
↑ ^6.0 ^6.1 ^6.2 ^6.3 Vinogradov, Matveevič (1934). "A new estimate for $G (n)$ in Waring's problem". Doklady Akademii Nauk SSSR (in Russian). 5 (5–6): 249–253.
Translated in English in:
Vinogradov, Matveevič (1985). Selected works / Ivan Matveevič Vinogradov; prepared by the Steklov Mathematical Institute of the Academy of Sciences of the USSR on the occasion of his 90th birthday. Springer-Verlag.
↑ ^7.0 ^7.1 ^7.2 ^7.3 ^7.4 Hardy, G. H.; Littlewood, J. E. (1914). "Some problems of diophantine approximation: Part II. The trigonometrical series associated with the elliptic $θ$ functions". Acta Mathematica. 37: 225. doi:10.1007/BF02401834. Archived from the original on 2018-12-12. Retrieved 2017-03-14.
↑ ^8.00 ^8.01 ^8.02 ^8.03 ^8.04 ^8.05 ^8.06 ^8.07 ^8.08 ^8.09 Knuth, Donald (April–June 1976). "Big Omicron and big Omega and big Theta". SIGACT News. 8 (2): 18–24. doi:10.1145/1008328.1008329. S2CID 5230246.
↑ ^9.0 ^9.1 ^9.2 Bois-Reymond, Paul du (1870). "Sur la grandeur relative des infinis des fonctions". Annali di Matematica. Series 2. 4: 338–353. doi:10.1007/BF02420041.
↑ Sipser, Michael (2012). Introduction to the Theory of Computation (3 ed.). Boston, MA: PWS Publishin.
↑ ^11.0 ^11.1 ^11.2 ^11.3 ^11.4 ^11.5 Ivić, A. (1985). The Riemann Zeta-Function. John Wiley & Sons. chapter 9.
↑ ^12.0 ^12.1 ^12.2 ^12.3 ^12.4 ^12.5 ^12.6 Gérald Tenenbaum, Introduction to analytic and probabilistic number theory, « Notation », page xxiii. American Mathematical Society, Providence RI, 2015.
↑ ^13.0 ^13.1 E. C. Titchmarsh, The Theory of the Riemann Zeta-Function (Oxford; Clarendon Press, 1951)
↑ Seidel, Raimund (1991), "A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons", Computational Geometry, 1: 51–64, CiteSeerX 10.1.1.55.5877, doi:10.1016/0925-7721(91)90012-4
↑ ^15.0 ^15.1 Hardy, G. H.; Littlewood, J. E. (1916). "Contribution to the theory of the Riemann zeta-function and the theory of the distribution of primes". Acta Mathematica. 41: 119–196. doi:10.1007/BF02422942.
↑ Landau, E. (1924). "Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV" [On the number of grid points in known regions]. Nachr. Gesell. Wiss. Gött. Math-phys. (in German): 137–150.
↑ Balcázar, José L.; Gabarró, Joaquim. "Nonuniform complexity classes specified by lower and upper bounds" (PDF). RAIRO – Theoretical Informatics and Applications – Informatique Théorique et Applications. 23 (2): 180. ISSN 0988-3754. Archived (PDF) from the original on 14 March 2017. Retrieved 14 March 2017 – via Numdam.
↑ Cucker, Felipe; Bürgisser, Peter (2013). "A.1 Big Oh, Little Oh, and Other Comparisons". Condition: The Geometry of Numerical Algorithms. Berlin, Heidelberg: Springer. pp. 467–468. doi:10.1007/978-3-642-38896-5. ISBN 978-3-642-38896-5.
↑ for example it is omitted in: Hildebrand, A.J. "Asymptotic Notations" (PDF). Department of Mathematics. Asymptotic Methods in Analysis. Math 595, Fall 2009. Urbana, IL: University of Illinois. Archived (PDF) from the original on 14 March 2017. Retrieved 14 March 2017.
↑ Cormen et al. 2022, p. 57.
↑ Cormen et al. 2022, p. 74–75.
↑ Andreas Björklund and Thore Husfeldt and Mikko Koivisto (2009). "Set partitioning via inclusion-exclusion" (PDF). SIAM Journal on Computing. 39 (2): 546–563. doi:10.1137/070683933. Archived (PDF) from the original on 2022-02-03. Retrieved 2022-02-03. See sect.2.3, p.551.
↑ Erdelyi, A. (1956). Asymptotic Expansions. Courier Corporation. ISBN 978-0-486-60318-6..
↑ Hardy, G. H. (1966–1979). Collected papers of G. H. Hardy (Including Joint papers with J. E. Littlewood and others), 7 vols. Clarendon Press, Oxford.
↑ Hardy, G. H.; Wright, E. M. (2008) [1st ed. 1938]. "1.6. Some notations". An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman, with a foreword by Andrew Wiles (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921985-8.
↑ ^26.0 ^26.1 de Bruijn, N.G. (1958). Asymptotic Methods in Analysis. Amsterdam: North-Holland. pp. 5–7. ISBN 978-0-486-64221-5. Archived from the original on 2023-01-17. Retrieved 2021-09-15.
↑ ^27.0 ^27.1 ^27.2 Graham, Ronald; Knuth, Donald; Patashnik, Oren (1994). Concrete Mathematics (2 ed.). Reading, Massachusetts: Addison–Wesley. p. 446. ISBN 978-0-201-55802-9. Archived from the original on 2023-01-17. Retrieved 2016-09-23.
↑ Donald Knuth (June–July 1998). "Teach Calculus with Big O" (PDF). Notices of the American Mathematical Society. 45 (6): 687. Archived (PDF) from the original on 2021-10-14. Retrieved 2021-09-05. (Unabridged version Archived 2008-05-13 at the Wayback Machine)
↑ Donald E. Knuth, The art of computer programming. Vol. 1. Fundamental algorithms, third edition, Addison Wesley Longman, 1997. Section 1.2.11.1.
↑ Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science (2nd ed.), Addison-Wesley, 1994. Section 9.2, p. 443.
↑ Sivaram Ambikasaran and Eric Darve, An Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal O (N \log N)} Fast Direct Solver for Partial Hierarchically Semi-Separable Matrices, J. Scientific Computing 57 (2013), no. 3, 477–501.
↑ Saket Saurabh and Meirav Zehavi, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (k,n-k)} -Max-Cut: An Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{O}^*(2^p)} -Time Algorithm and a Polynomial Kernel, Algorithmica 80 (2018), no. 12, 3844–3860.

Notes

↑ Note that the "size" of the input is typically used as an indication of how challenging a given instance is, of the problem to be solved. The amount of [execution] time, and the amount of [memory] space required to compute the answer, (or to "solve' the problem), are seen as indicating the difficulty of that instance of the problem. For purposes of Computational complexity theory, Big Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O} notation is used for an upper bound on [the "order of magnitude" of] all 3 of those: the size of the input [data stream], the amount of [execution] time required, and the amount of [memory] space required.
↑ This name is suggested in the title of a paper of Knuth in 1976, and is found nowhere else in the rest of the paper. It is seldom or never used.

External links

[Bachmann-1] 1.0 ^1.1 Bachmann, Paul (1894). Analytische Zahlentheorie [Analytic Number Theory] (in German). 2. Leipzig: Teubner.

[Landau-2] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 Landau, Edmund (1909). Handbuch der Lehre von der Verteilung der Primzahlen [Handbook on the theory of the distribution of the primes] (in German). Leipzig: B.G. Teubner; reprinted as two volumes in one by Chelsea, 1974, with an appendix by Dr. Paul T. Bateman. pp. 59–63.

[:0-4] 3.0 ^3.1 ^3.2 ^3.3 ^3.4 ^3.5 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). "Characterizing running times". Introduction to Algorithms (4th ed.). MIT Press and McGraw-Hill. ISBN 978-0-262-53091-0.

[iwaniec-kowalski-5] 4.0 ^4.1 ^4.2 ^4.3 ^4.4 ^4.5 Iwaniec, Henryk; Kowalski, Emmanuel (2004). Analytic Number Theory. American Mathematical Society.

[Hardy-6] 5.0 ^5.1 ^5.2 ^5.3 ^5.4 Hardy, G. H. (1910). Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond. Cambridge University Press. p. 2.

[vinogradov-7] 6.0 ^6.1 ^6.2 ^6.3 Vinogradov, Matveevič (1934). "A new estimate for $G (n)$ in Waring's problem". Doklady Akademii Nauk SSSR (in Russian). 5 (5–6): 249–253.
Translated in English in:
Vinogradov, Matveevič (1985). Selected works / Ivan Matveevič Vinogradov; prepared by the Steklov Mathematical Institute of the Academy of Sciences of the USSR on the occasion of his 90th birthday. Springer-Verlag.

[HL-8] 7.0 ^7.1 ^7.2 ^7.3 ^7.4 Hardy, G. H.; Littlewood, J. E. (1914). "Some problems of diophantine approximation: Part II. The trigonometrical series associated with the elliptic $θ$ functions". Acta Mathematica. 37: 225. doi:10.1007/BF02401834. Archived from the original on 2018-12-12. Retrieved 2017-03-14.

[knuth-9] 8.00 ^8.01 ^8.02 ^8.03 ^8.04 ^8.05 ^8.06 ^8.07 ^8.08 ^8.09 Knuth, Donald (April–June 1976). "Big Omicron and big Omega and big Theta". SIGACT News. 8 (2): 18–24. doi:10.1145/1008328.1008329. S2CID 5230246.

[Bois-Reymond-10] 9.0 ^9.1 ^9.2 Bois-Reymond, Paul du (1870). "Sur la grandeur relative des infinis des fonctions". Annali di Matematica. Series 2. 4: 338–353. doi:10.1007/BF02420041.

[11] Sipser, Michael (2012). Introduction to the Theory of Computation (3 ed.). Boston, MA: PWS Publishin.

[Ivic-12] 11.0 ^11.1 ^11.2 ^11.3 ^11.4 ^11.5 Ivić, A. (1985). The Riemann Zeta-Function. John Wiley & Sons. chapter 9.

[tenenbaum-13] 12.0 ^12.1 ^12.2 ^12.3 ^12.4 ^12.5 ^12.6 Gérald Tenenbaum, Introduction to analytic and probabilistic number theory, « Notation », page xxiii. American Mathematical Society, Providence RI, 2015.

[titchmarsh-14] 13.0 ^13.1 E. C. Titchmarsh, The Theory of the Riemann Zeta-Function (Oxford; Clarendon Press, 1951)

[15] Seidel, Raimund (1991), "A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons", Computational Geometry, 1: 51–64, CiteSeerX 10.1.1.55.5877, doi:10.1016/0925-7721(91)90012-4

[HL2-16] 15.0 ^15.1 Hardy, G. H.; Littlewood, J. E. (1916). "Contribution to the theory of the Riemann zeta-function and the theory of the distribution of primes". Acta Mathematica. 41: 119–196. doi:10.1007/BF02422942.

[landau-17] Landau, E. (1924). "Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV" [On the number of grid points in known regions]. Nachr. Gesell. Wiss. Gött. Math-phys. (in German): 137–150.

[Balcázar-18] Balcázar, José L.; Gabarró, Joaquim. "Nonuniform complexity classes specified by lower and upper bounds" (PDF). RAIRO – Theoretical Informatics and Applications – Informatique Théorique et Applications. 23 (2): 180. ISSN 0988-3754. Archived (PDF) from the original on 14 March 2017. Retrieved 14 March 2017 – via Numdam.

[Cucker-19] Cucker, Felipe; Bürgisser, Peter (2013). "A.1 Big Oh, Little Oh, and Other Comparisons". Condition: The Geometry of Numerical Algorithms. Berlin, Heidelberg: Springer. pp. 467–468. doi:10.1007/978-3-642-38896-5. ISBN 978-3-642-38896-5.

[21] r example it is omitted in: Hildebrand, A.J. "Asymptotic Notations" (PDF). Department of Mathematics. Asymptotic Methods in Analysis. Math 595, Fall 2009. Urbana, IL: University of Illinois. Archived (PDF) from the original on 14 March 2017. Retrieved 14 March 2017.

[FOOTNOTECormenLeisersonRivestStein202257-22] Cormen et al. 2022, p. 57.

[FOOTNOTECormenLeisersonRivestStein202274–75-23] Cormen et al. 2022, p. 74–75.

[24] Andreas Björklund and Thore Husfeldt and Mikko Koivisto (2009). "Set partitioning via inclusion-exclusion" (PDF). SIAM Journal on Computing. 39 (2): 546–563. doi:10.1137/070683933. Archived (PDF) from the original on 2022-02-03. Retrieved 2022-02-03. See sect.2.3, p.551.

[25] Erdelyi, A. (1956). Asymptotic Expansions. Courier Corporation. ISBN 978-0-486-60318-6..

[26] Hardy, G. H. (1966–1979). Collected papers of G. H. Hardy (Including Joint papers with J. E. Littlewood and others), 7 vols. Clarendon Press, Oxford.

[27] Hardy, G. H.; Wright, E. M. (2008) [1st ed. 1938]. "1.6. Some notations". An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman, with a foreword by Andrew Wiles (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921985-8.

[deBruijn-28] 26.0 ^26.1 de Bruijn, N.G. (1958). Asymptotic Methods in Analysis. Amsterdam: North-Holland. pp. 5–7. ISBN 978-0-486-64221-5. Archived from the original on 2023-01-17. Retrieved 2021-09-15.

[Concrete_Mathematics-29] 27.0 ^27.1 ^27.2 Graham, Ronald; Knuth, Donald; Patashnik, Oren (1994). Concrete Mathematics (2 ed.). Reading, Massachusetts: Addison–Wesley. p. 446. ISBN 978-0-201-55802-9. Archived from the original on 2023-01-17. Retrieved 2016-09-23.

[30] Donald Knuth (June–July 1998). "Teach Calculus with Big O" (PDF). Notices of the American Mathematical Society. 45 (6): 687. Archived (PDF) from the original on 2021-10-14. Retrieved 2021-09-05. (Unabridged version Archived 2008-05-13 at the Wayback Machine)

[KnuthArt-31] Donald E. Knuth, The art of computer programming. Vol. 1. Fundamental algorithms, third edition, Addison Wesley Longman, 1997. Section 1.2.11.1.

[ConcreteMath-32] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science (2nd ed.), Addison-Wesley, 1994. Section 9.2, p. 443.

[33] Sivaram Ambikasaran and Eric Darve, An Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal O (N \log N)} Fast Direct Solver for Partial Hierarchically Semi-Separable Matrices, J. Scientific Computing 57 (2013), no. 3, 477–501.

[34] Saket Saurabh and Meirav Zehavi, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (k,n-k)} -Max-Cut: An Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{O}^*(2^p)} -Time Algorithm and a Polynomial Kernel, Algorithmica 80 (2018), no. 12, 3844–3860.

[3] Note that the "size" of the input is typically used as an indication of how challenging a given instance is, of the problem to be solved. The amount of [execution] time, and the amount of [memory] space required to compute the answer, (or to "solve' the problem), are seen as indicating the difficulty of that instance of the problem. For purposes of Computational complexity theory, Big Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O} notation is used for an upper bound on [the "order of magnitude" of] all 3 of those: the size of the input [data stream], the amount of [execution] time required, and the amount of [memory] space required.

[20] This name is suggested in the title of a paper of Knuth in 1976, and is found nowhere else in the rest of the paper. It is seldom or never used.

[1]

[2]

[lower-alpha 1]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[lower-alpha 2]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]