Big ''O'' notation is a mathematical notation that describes the limiting behavior of a

^{3})) means the absolute-value of the error ''e''^{''x''} − (1 + ''x'' + ''x''^{2}/2) is at most some constant times ''x''^{3} when ''x'' is close enough to 0.

,_since_the_use_of_the_equals_sign_could_be_misleading_as_it_suggests_a_symmetry_that_this_statement_does_not_have._As_ ,_but_not_if_they_are_defined_on_.
This_is_not_the_only_generalization_of_big_O_to_multivariate_functions,_and_in_practice,_there_is_some_inconsistency_in_the_choice_of_definition.
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-orien ...

when the argument
An argument is a statement or group of statements called premises intended to determine the degree of truth or acceptability of another statement called conclusion. Arguments can be studied from three main perspectives: the logical, the dialec ...

tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Landau
Edmund Georg Hermann Landau (14 February 1877 – 19 February 1938) was a German mathematician who worked in the fields of number theory and complex analysis.
Biography
Edmund Landau was born to a Jewish family in Berlin. His father was Leopol ...

, and others, collectively called Bachmann–Landau notation or asymptotic notation. The letter O was chosen by Bachmann to stand for '' Ordnung'', meaning the order of approximation
In science, engineering, and other quantitative disciplines, order of approximation refers to formal or informal expressions for how accurate an approximation is.
Usage in science and engineering
In formal expressions, the ordinal number used b ...

.
In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows. In analytic number theory
In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Peter Gustav Lejeune Dirichlet's 1837 introduction of Di ...

, big O notation is often used to express a bound on the difference between an arithmetical function and a better understood approximation; a famous example of such a difference is the remainder term in the prime number theorem
In mathematics, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifyin ...

. Big O notation is also used in many other fields to provide similar estimates.
Big O notation characterizes functions according to their growth rates: different functions with the same 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 usually only provides an upper bound on the growth rate of the function.
Associated with big O notation are several related notations, using the symbols , and , to describe other kinds of bounds on asymptotic growth rates.
Formal definition

Let $f$, the function to be estimated, be a real or complex valued function and let $g$, the comparison function, be a real valued function. Let both functions be defined on some unbounded subset of the positive real numbers, and $g(x)$ be strictly positive for all large enough values of $x$. One writes $$f(x)\; =\; O\backslash bigl(\; g(x)\backslash bigr)\backslash quad\backslash textx\backslash to\backslash infty$$ if theabsolute value
In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), and ...

of $f(x)$ is at most a positive constant multiple of $g(x)$ for all sufficiently large values of $x$. That is, $f(x)\; =O\backslash bigl(g(x)\backslash bigr)$ if there exists a positive real number $M$ and a real number $x\_0$ such that
$$,\; f(x),\; \backslash le\; M\; g(x)\; \backslash quad\; \backslash text\; x\; \backslash ge\; x\_0.$$
In many contexts, the assumption that we are interested in the growth rate as the variable $x$ goes to infinity is left unstated, and one writes more simply that
$$f(x)\; =\; O\backslash bigl(\; g(x)\; \backslash bigr).$$
The notation can also be used to describe the behavior of $f$ near some real number $a$ (often, $a=0$): we say
$$f(x)\; =\; O\backslash bigl(\; g(x)\; \backslash bigr)\backslash quad\backslash textx\; \backslash to\; a$$
if there exist positive numbers $\backslash delta$ and $M$ such that for all defined $x$ with
$$,\; f(x),\; \backslash le\; M\; g(x).$$
As $g(x)$ is chosen to be strictly positive for such values of $x$, both of these definitions can be unified using the limit superior:
$$f(x)\; =\; O\backslash bigl(\; g(x)\; \backslash bigr)\; \backslash quad\; \backslash text\; x\; \backslash to\; a$$
if
$$\backslash limsup\_\; \backslash frac\; <\; \backslash infty.$$
And in both of these definitions the limit point
In mathematics, a limit point, accumulation point, or cluster point of a set S in a topological space X is a point x that can be "approximated" by points of S in the sense that every neighbourhood of x with respect to the topology on X also conta ...

$a$ (whether $\backslash infty$ or not) is a cluster point
In mathematics, a limit point, accumulation point, or cluster point of a set S in a topological space X is a point x that can be "approximated" by points of S in the sense that every neighbourhood of x with respect to the topology on X also contai ...

of the domains of $f$ and $g$, i. e., in every neighbourhood of $a$ there have to be infinitely many points in common. Moreover, as pointed out in the article about the limit inferior and limit superior
In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting (that is, eventual and extreme) bounds on the sequence. They can be thought of in a similar fashion for a function (see limit of a function). For a ...

, the $\backslash textstyle\; \backslash limsup\_$ (at least on the extended real number line
In mathematics, the affinely extended real number system is obtained from the real number system \R by adding two infinity elements: +\infty and -\infty, where the infinities are treated as actual numbers. It is useful in describing the algebra on ...

) always exists.
In computer science, a slightly more restrictive definition is common: $f$ and $g$ are both required to be functions from some unbounded subset of the positive integers
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal n ...

to the nonnegative real numbers; then $f(x)\; =\; O\backslash bigl(g(x)\backslash bigr)$ iff there exist positive integer numbers $M$ and $n\_0$ such that $f(n)\; \backslash le\; M\; g(n)$ for all $n\; \backslash ge\; n\_0$.
Example

In typical usage the notation is asymptotical, that is, it refers to very large . 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 is a sum of several terms, if there is one with largest growth rate, it can be kept, and all others omitted. *If is a product of several factors, any constants (terms in the product that do not depend on ) can be omitted. For example, let , and suppose we wish to simplify this function, using notation, to describe its growth rate as approaches infinity. This function is the sum of three terms: , , and . Of these three terms, the one with the highest growth rate is the one with the largest exponent as a function of , namely . Now one may apply the second rule: is a product of and in which the first factor does not depend on . Omitting this factor results in the simplified form . Thus, we say that is a "big O" of . Mathematically, we can write . One may confirm this calculation using the formal definition: let and . Applying theformal definition
Formal, formality, informal or informality imply the complying with, or not complying with, some set of requirements (forms, in Ancient Greek). They may refer to:
Dress code and events
* Formal wear, attire for formal events
* Semi-formal attire ...

from above, the statement that is equivalent to its expansion,
$$,\; f(x),\; \backslash le\; M\; x^4$$
for some suitable choice of and and for all . To prove this, let and . Then, for all :
$$\backslash begin\; ,\; 6x^4\; -\; 2x^3\; +\; 5,\; \&\backslash le\; 6x^4\; +\; ,\; 2x^3,\; +\; 5\backslash \backslash \; \&\backslash le\; 6x^4\; +\; 2x^4\; +\; 5x^4\backslash \backslash \; \&=\; 13x^4\; \backslash end$$
so
$$,\; 6x^4\; -\; 2x^3\; +\; 5,\; \backslash le\; 13\; x^4\; .$$
Usage

Big O notation has two main areas of application: * In mathematics, it is commonly used to describe how closely a finite series approximates a given function, especially in the case of a truncated Taylor series orasymptotic expansion In mathematics, an asymptotic expansion, asymptotic series or Poincaré expansion (after Henri Poincaré) is a formal series of functions which has the property that truncating the series after a finite number of terms provides an approximation t ...

* In computer science, it is useful in the analysis of algorithms
In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that ...

In both applications, the function appearing within the is typically chosen to be as simple as possible, omitting constant factors and lower order terms.
There are two formally close, but noticeably different, usages of this notation:
* infinite asymptotics
* infinitesimal
In mathematics, an infinitesimal number is a quantity that is closer to zero than any standard real number, but that is not zero. The word ''infinitesimal'' comes from a 17th-century Modern Latin coinage ''infinitesimus'', which originally refer ...

asymptotics.
This distinction is only in application and not in principle, however—the formal definition for the "big O" is the same for both cases, only with different limits for the function argument.
Infinite asymptotics

Big O notation is useful when analyzing algorithms for efficiency. For example, the time (or the number of steps) it takes to complete a problem of size might be found to be . As grows large, the term will come to dominate, so that all other terms can be neglected—for instance when , the term is 1000 times as large as the term. Ignoring the latter would have negligible effect on the expression's value for most purposes. Further, thecoefficient
In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves v ...

s become irrelevant if we compare to any other order of expression, such as an expression containing a term or . Even if , if , the latter will always exceed the former once grows larger than (). Additionally, the number of steps depends on the details of the machine model on which the algorithm runs, but different types of machines typically vary by only a constant factor in the number of steps needed to execute an algorithm. So the big O notation captures what remains: we write either
:$T(n)=\; O(n^2)$
or
:$T(n)\; \backslash in\; O(n^2)$
and say that the algorithm has ''order of '' time complexity. The sign "" is not meant to express "is equal to" in its normal mathematical sense, but rather a more colloquial "is", so the second expression is sometimes considered more accurate (see the "Equals sign
The equals sign (British English, Unicode) or equal sign (American English), also known as the equality sign, is the mathematical symbol , which is used to indicate equality in some well-defined sense. In an equation, it is placed between two ...

" discussion below) while the first is considered by some as an abuse of notation
In mathematics, abuse of notation occurs when an author uses a mathematical notation in a way that is not entirely formally correct, but which might help simplify the exposition or suggest the correct intuition (while possibly minimizing errors a ...

.
Infinitesimal asymptotics

Big O can also be used to describe the error term in an approximation to a mathematical function. 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 is small: :$\backslash begin\; e^x\; \&=1+x+\backslash frac+\backslash frac+\backslash frac+\backslash dotsb\; \&\backslash text\; x\backslash \backslash ;\; href="/html/ALL/s/pt.html"\; ;"title="pt">pt$ The second expression (the one with ''O''(''x''Properties

If the function can be written as a finite sum of other functions, then the fastest growing one determines the order of . For example, :$f(n)\; =\; 9\; \backslash log\; n\; +\; 5\; (\backslash log\; n)^4\; +\; 3n^2\; +\; 2n^3\; =\; O(n^3)\; \backslash qquad\backslash text\; n\backslash to\backslash infty\; .$ In particular, if a function may be bounded by a polynomial in , then as tends to ''infinity'', one may disregard ''lower-order'' terms of the polynomial. The sets and are very different. If is greater than one, then the latter grows much faster. A function that grows faster than for any is called ''superpolynomial''. One that grows more slowly than any exponential function of the form is called ''subexponential''. An algorithm can require time that is both superpolynomial and subexponential; examples of this include the fastest known algorithms forinteger factorization
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.
When the numbers are su ...

and the function .
We may ignore any powers of inside of the logarithms. The set is exactly the same as . The logarithms differ only by a constant factor (since ) and thus the big O notation ignores that. Similarly, logs with different constant bases are equivalent. On the other hand, exponentials with different bases are not of the same order. For example, and are not of the same order.
Changing units may or may not affect the order of the resulting algorithm. Changing units is equivalent to multiplying the appropriate variable by a constant wherever it appears. For example, if an algorithm runs in the order of , replacing by means the algorithm runs in the order of , and the big O notation ignores the constant . This can be written as . If, however, an algorithm runs in the order of , replacing with gives . This is not equivalent to in general. Changing variables may also affect the order of the resulting algorithm. For example, if an algorithm's run time is when measured in terms of the number of ''digits'' of an input number , then its run time is when measured as a function of the input number itself, because .
Product

:$f\_1\; =\; O(g\_1)\; \backslash text\; f\_2\; =\; O(g\_2)\; \backslash Rightarrow\; f\_1\; f\_2\; =\; O(g\_1\; g\_2)$ :$f\backslash cdot\; O(g)\; =\; O(f\; g)$Sum

If $f\_1\; =\; O(g\_1)$ and $f\_2=\; O(g\_2)$ then $f\_1\; +\; f\_2\; =\; O(\backslash max(g\_1,\; g\_2))$. It follows that if $f\_1\; =\; O(g)$ and $f\_2\; =\; O(g)$ then $f\_1+f\_2\; \backslash in\; O(g)$. In other words, this second statement says that $O(g)$ is aconvex cone
In linear algebra, a ''cone''—sometimes called a linear cone for distinguishing it from other sorts of cones—is a subset of a vector space that is closed under scalar multiplication; that is, is a cone if x\in C implies sx\in C for every .
...

.
Multiplication by a constant

Let be a nonzero constant. Then $O(,\; k,\; \backslash cdot\; g)\; =\; O(g)$. In other words, if $f\; =\; O(g)$, then $k\; \backslash cdot\; f\; =\; O(g).$Multiple variables

Big ''O'' (and little o, Ω, etc.) can also be used with multiple variables. To define big ''O'' formally for multiple variables, suppose $f$ and $g$ are two functions defined on some subset of $\backslash R^n$. We say :$f(\backslash mathbf)\backslash textO(g(\backslash mathbf))\backslash quad\backslash text\backslash mathbf\backslash to\backslash infty$ if and only if there exist constants $M$ and $C\; >\; 0$ such that $,\; f(\backslash mathbf),\; \backslash le\; C\; ,\; g(\backslash mathbf),$ for all $\backslash mathbf$ with $x\_i\; \backslash geq\; M$ for some $i.$ Equivalently, the condition that $x\_i\; \backslash geq\; M$ for some $i$ can be written $\backslash ,\; \backslash mathbf\backslash ,\; \_\; \backslash ge\; M$, where $\backslash ,\; \backslash mathbf\backslash ,\; \_$ denotes the Chebyshev norm. For example, the statement :$f(n,m)\; =\; n^2\; +\; m^3\; +\; O(n+m)\; \backslash quad\backslash text\; n,m\backslash to\backslash infty$ asserts that there exist constants ''C'' and ''M'' such that :$,\; f(n,m)\; -\; (n^2\; +\; m^3),\; \backslash le\; C\; ,\; n+m,$ whenever either $m\; \backslash geq\; M$ or $n\; \backslash geq\; M$ holds. This definition allows all of the coordinates of $\backslash mathbf$ to increase to infinity. In particular, the statement :$f(n,m)\; =\; O(n^m)\; \backslash quad\; \backslash text\; n,m\backslash to\backslash infty$ (i.e., $\backslash exists\; C\; \backslash ,\backslash exists\; M\; \backslash ,\backslash forall\; n\; \backslash ,\backslash forall\; m\backslash ,\backslash cdots$) is quite different from :$\backslash forall\; m\backslash colon~f(n,m)\; =\; O(n^m)\; \backslash quad\backslash text\; n\backslash to\backslash infty$ (i.e., $\backslash forall\; m\; \backslash ,\; \backslash exists\; C\; \backslash ,\; \backslash exists\; M\; \backslash ,\; \backslash forall\; n\; \backslash ,\; \backslash cdots$). Under this definition, the subset on which a function is defined is significant when generalizing statements from the univariate setting to the multivariate setting. For example, if $f(n,m)=1$ and $g(n,m)=n$, then $f(n,m)\; =\; O(g(n,m))$ if we restrict $f$ and $g$ to $;\; href="/html/ALL/s/,\backslash infty)^2$__Matters_of_notation_

__Equals_sign_

The_statement_" ''f''(''x'')_is_''o''(''g''(''x''))"_as_defined_above_is_usually_written_as_._some_consider_this_to_be_an_,_since_the_use_of_the_equals_sign_could_be_misleading_as_it_suggests_a_symmetry_that_this_statement_does_not_have._As_Nicolaas_Govert_de_Bruijn">de_Bruijn_says,__is_true_but__is_not.

Matters of notation

Equals sign

The statement "''f''(''x'') is ''O''(''g''(''x''))" as defined above is usually written as . Some consider this to be anabuse of notation
In mathematics, abuse of notation occurs when an author uses a mathematical notation in a way that is not entirely formally correct, but which might help simplify the exposition or suggest the correct intuition (while possibly minimizing errors a ...

, since the use of the equals sign could be misleading as it suggests a symmetry that this statement does not have. As Nicolaas Govert de Bruijn">de Bruijn says, is true but is not. Donald Knuth">Knuth describes such statements as "one-way equalities", since if the sides could be reversed, "we could deduce ridiculous things like from the identities and ." In another letter, Knuth also pointed out that "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, it would be more precise to use set notation and write (read as: "''f''(''x'') ''Element (mathematics)#Notation and terminology, is an element of'' ''O''(''g''(''x''))", or "''f''(''x'') ''is in the set'' ''O''(''g''(''x''))"), thinking of ''O''(''g''(''x'')) as the class of all functions ''h''(''x'') such that , ''h''(''x''), ≤ ''C'', ''g''(''x''), for some constant ''C''. However, the use of the equals sign is customary.
Other arithmetic operators

Big O notation can also be used in conjunction with other arithmetic operators in more complicated equations. For example, denotes the collection of functions having the growth of ''h''(''x'') plus a part whose growth is limited to that of ''f''(''x''). Thus, :$g(x)\; =\; h(x)\; +\; O(f(x))$ expresses the same as :$g(x)\; -\; h(x)\; =\; O(f(x)).$Example

Suppose analgorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

is being developed to operate on a set of ''n'' elements. Its developers are interested in finding a function ''T''(''n'') that will express how long the algorithm will take to run (in some arbitrary measurement of time) in terms of the number of elements in the input set. The algorithm works by first calling a subroutine to sort the elements in the set and then perform its own operations. The sort has a known time complexity of ''O''(''n''Multiple uses

In more complicated usage, ''O''(·) can appear in different places in an equation, even several times on each side. For example, the following are true for $n\backslash to\backslash infty$: $$\backslash begin\; (n+1)^2\; \&\; =\; n^2\; +\; O(n),\; \backslash \backslash \; (n\; +\; O(n^))\; \backslash cdot\; (n\; +\; O(\backslash log\; n))^2\; \&\; =\; n^3\; +\; O(n^),\; \backslash \backslash \; n^\; \&\; =\; O(e^n).\; \backslash end$$ The meaning of such statements is as follows: for ''any'' functions which satisfy each ''O''(·) on the left side, there are ''some'' functions satisfying each ''O''(·) 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 ''f''(''n'') = ''O''(1), there is some function ''g''(''n'') = ''O''(''e''symmetric relation
A symmetric relation is a type of binary relation. An example is the relation "is equal to", because if ''a'' = ''b'' is true then ''b'' = ''a'' is also true. Formally, a binary relation ''R'' over a set ''X'' is symmetric if:
:\forall a, b \in X( ...

. Thus for example does not imply the false statement .
Typesetting

Big O is typeset as an italicized uppercase "O", as in the following example: $O(n^2)$.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. In TeX, it is produced by simply typing O inside math mode. Unlike Greek-named Bachmann–Landau notations, it needs no special symbol. Yet, some authors use the calligraphic variant $\backslash mathcal$ instead.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. The statement $f(n)\; =\; O(n!)$ is sometimes weakened to $f(n)\; =\; O\backslash left(n^n\backslash right)$ to derive simpler formulas for asymptotic complexity. For any $k>0$ and $O(n^c(\backslash log\; n)^k)$ is a subset of $O(n^)$ for any so may be considered as a polynomial with some bigger order.Related asymptotic notations

Big ''O'' is widely used in computer science. Together with some other related notations it forms the family of Bachmann–Landau notations.Little-o notation

Intuitively, the assertion " is " (read " is little-o of ") means that grows much faster than . As before, let ''f'' be a real or complex valued function and ''g'' a real valued function, both defined on some unbounded subset of the positive real numbers, such that ''g''(''x'') is strictly positive for all large enough values of ''x''. One writes :$f(x)\; =\; o(g(x))\; \backslash quad\; \backslash text\; x\; \backslash to\; \backslash infty$ if for every positive constant there exists a constant $x\_0$ such that :$,\; f(x),\; \backslash leq\; \backslash varepsilon\; g(x)\; \backslash quad\; \backslash text\; x\; \backslash geq\; x\_0.$ For example, one has : $2x\; =\; o(x^2)$ and $1/x\; =\; o(1),$ both as $x\; \backslash to\; \backslash infty\; .$ The difference between the definition of the big-O notation and the definition of little-o is that while the former has to be true for ''at least one'' constant ''M'', the latter must hold for ''every'' positive constant , however small.Thomas H. Cormen et al., 2001Introduction to Algorithms, Second Edition, Ch. 3.1

/ref> In this way, little-o notation makes a ''stronger statement'' than the corresponding big-O notation: every function that is little-o of ''g'' is also big-O of ''g'', but not every function that is big-O of ''g'' is also little-o of ''g''. For example, $2x^2\; =\; O(x^2)$ but As ''g''(''x'') is nonzero, or at least becomes nonzero beyond a certain point, the relation $f(x)\; =\; o(g(x))$ is equivalent to :$\backslash lim\_\backslash frac\; =\; 0$ (and this is in fact how Landau originally defined the little-o notation). Little-o respects a number of arithmetic operations. For example, : if is a nonzero constant and $f\; =\; o(g)$ then $c\; \backslash cdot\; f\; =\; o(g)$, and : if $f\; =\; o(F)$ and $g\; =\; o(G)$ then $f\; \backslash cdot\; g\; =\; o(F\; \backslash cdot\; G).$ It also satisfies a transitivity relation: : if $f\; =\; o(g)$ and $g\; =\; o(h)$ then $f\; =\; o(h).$

Big Omega notation

Another asymptotic notation is $\backslash Omega$, read "big omega". There are two widespread and incompatible definitions of the statement :$f(x)=\backslash Omega(g(x))$ as $x\; \backslash to\; a$, where ''a'' is some real number, ∞, or −∞, where ''f'' and ''g'' are real functions defined in a neighbourhood of ''a'', and where ''g'' is positive in this neighbourhood. The Hardy–Littlewood definition is used mainly inanalytic number theory
In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Peter Gustav Lejeune Dirichlet's 1837 introduction of Di ...

, and the Knuth definition mainly in computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...

; the definitions are not equivalent.
The Hardy–Littlewood definition

In 1914 Godfrey Harold Hardy andJohn Edensor Littlewood
John Edensor Littlewood (9 June 1885 – 6 September 1977) was a British mathematician. He worked on topics relating to analysis, number theory, and differential equations, and had lengthy collaborations with G. H. Hardy, Srinivasa Rama ...

introduced the new symbol $\backslash Omega$, which is defined as follows:
:$f(x)\; =\; \backslash Omega(g(x))$ as $x\backslash to\backslash infty$ if $\backslash limsup\_\; \backslash left,\; \backslash frac\backslash \; >\; 0.$
Thus $f(x)=\backslash Omega(g(x))$ is the negation of $f(x)=o(g(x))$.
In 1916 the same authors introduced the two new symbols $\backslash Omega\_R$ and $\backslash Omega\_L$, defined as:G. H. Hardy and J. E. Littlewood, « Contribution to the theory of the Riemann zeta-function and the theory of the distribution of primes », ''Acta Mathematica
''Acta Mathematica'' is a peer-reviewed open-access scientific journal covering research in all fields of mathematics.
According to Cédric Villani, this journal is "considered by many to be the most prestigious of all mathematical research jour ...

'', vol. 41, 1916.
:$f(x)=\backslash Omega\_R(g(x))$ as $x\backslash to\backslash infty$ if $\backslash limsup\_\; \backslash frac>\; 0$;
:$f(x)=\backslash Omega\_L(g(x))$ as $x\backslash to\backslash infty$ if $\backslash liminf\_\; \backslash frac<\; 0.$
These symbols were used by Edmund Landau
Edmund Georg Hermann Landau (14 February 1877 – 19 February 1938) was a German mathematician who worked in the fields of number theory and complex analysis.
Biography
Edmund Landau was born to a Jewish family in Berlin. His father was Leopol ...

, with the same meanings, in 1924.E. Landau, "Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV." Nachr. Gesell. Wiss. Gött. Math-phys. Kl. 1924, 137–150. After Landau, the notations were never used again exactly thus; $\backslash Omega\_R$ became $\backslash Omega\_+$ and $\backslash Omega\_L$ became $\backslash Omega\_-$.
These three symbols $\backslash Omega,\; \backslash Omega\_+,\; \backslash Omega\_-$, as well as $f(x)=\backslash Omega\_\backslash pm(g(x))$ (meaning that $f(x)=\backslash Omega\_+(g(x))$ and $f(x)=\backslash Omega\_-(g(x))$ are both satisfied), are now currently used in analytic number theory
In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Peter Gustav Lejeune Dirichlet's 1837 introduction of Di ...

.Aleksandar Ivić. The Riemann zeta-function, chapter 9. John Wiley & Sons 1985.
= Simple examples

= We have :$\backslash sin\; x=\backslash Omega(1)$ as $x\backslash to\backslash infty,$ and more precisely :$\backslash sin\; x=\backslash Omega\_\backslash pm(1)$ as $x\backslash to\backslash infty.$ We have :$\backslash sin\; x+1=\backslash Omega(1)$ as $x\backslash to\backslash infty,$ and more precisely :$\backslash sin\; x+1=\backslash Omega\_+(1)$ as $x\backslash to\backslash infty;$ however :$\backslash sin\; x+1\backslash not=\backslash Omega\_-(1)$ as $x\backslash to\backslash infty.$The Knuth definition

In 1976Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...

published a paper to justify his use of the $\backslash Omega$-symbol to describe a stronger property. Knuth wrote: "For all the applications I have seen so far in computer science, a stronger requirement ... is much more appropriate". He defined
:$f(x)=\backslash Omega(g(x))\backslash Leftrightarrow\; g(x)=O(f(x))$
with the comment: "Although I have changed Hardy and Littlewood's definition of $\backslash 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."
Family of Bachmann–Landau notations

The limit definitions assume $g(n)\; >\; 0$ for sufficiently large $n$. The table is (partly) sorted from smallest to largest, in the sense that $o,O,\backslash Theta,\backslash sim,$ (Knuth's version of) $\backslash Omega,\; \backslash omega$ on functions correspond to $<,\backslash leq,\backslash approx,=,$$\backslash geq,>$ on the real line (the Hardy–Littlewood version of $\backslash Omega$, however, doesn't correspond to any such description). Computer science uses the big $O$, big Theta $\backslash Theta$, little $o$, little omega $\backslash omega$ and Knuth's big Omega $\backslash Omega$ notations. Analytic number theory often uses the big $O$, small $o$, Hardy–Littlewood's big Omega $\backslash Omega$ (with or without the +, − or ± subscripts) and $\backslash sim$ notations. The small omega $\backslash omega$ notation is not used as often in analysis.Use in computer science

Informally, especially in computer science, the big ''O'' notation often can be used somewhat differently to describe an asymptotictight
Tight may refer to:
Clothing
* Skin-tight garment, a garment that is held to the skin by elastic tension
* Tights, a type of leg coverings fabric extending from the waist to feet
* Tightlacing, the practice of wearing a tightly-laced corset
* ...

bound where using big Theta Θ notation might be more factually appropriate in a given context. For example, when considering a function ''T''(''n'') = 73''n''Other notation

In their book '' Introduction to Algorithms'', Cormen, Leiserson, Rivest andStein
Stein is a German, Yiddish and Norwegian word meaning "stone" and "pip" or "kernel". It stems from the same Germanic root as the English word stone. It may refer to:
Places In Austria
* Stein, a neighbourhood of Krems an der Donau, Lower Aust ...

consider the set of functions ''f'' which satisfy
:$f(n)\; =\; O(g(n))\backslash quad(n\backslash to\backslash infty)~.$
In a correct notation this set can, for instance, be called ''O''(''g''), where
:$O(g)\; =\; \backslash .$
The authors state that the use of equality operator (=) to denote set membership rather than the set membership operator (∈) is an abuse of notation, but that doing so has advantages. Inside an equation or inequality, the use of asymptotic notation stands for an anonymous function in the set ''O''(''g''), which eliminates lower-order terms, and helps to reduce inessential clutter in equations, for example:
:$2n^2\; +\; 3n\; +\; 1=2n^2\; +\; O(n).$
Extensions to the Bachmann–Landau notations

Another notation sometimes used in computer science is Õ (read ''soft-O''): ''f''(''n'') = ''Õ''(''g''(''n'')) is shorthand for for some ''k''. Some authors write Opolynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An examp ...

and exponential
Exponential may refer to any of several mathematical topics related to exponentiation, including:
*Exponential function, also:
**Matrix exponential, the matrix analogue to the above
*Exponential decay, decrease at a rate proportional to value
* Exp ...

in terms of
Generalizations and related usages

The generalization to functions taking values in anynormed vector space
In mathematics, a normed vector space or normed space is a vector space over the real or complex numbers, on which a norm is defined. A norm is the formalization and the generalization to real vector spaces of the intuitive notion of "length ...

is straightforward (replacing absolute values by norms), where ''f'' and ''g'' need not take their values in the same space. A generalization to functions ''g'' taking values in any topological group is also possible.
The "limiting process" ''x'' → ''x''derivative
In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value). Derivatives are a fundamental tool of calculus. ...

s and differentiability in quite general spaces, and also (asymptotical) equivalence of functions,
:$f\backslash sim\; g\; \backslash iff\; (f-g)\; \backslash in\; o(g)$
which is an equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...

and a more restrictive notion than the relationship "''f'' is Θ(''g'')" from above. (It reduces to lim ''f'' / ''g'' = 1 if ''f'' and ''g'' are positive real valued functions.) For example, 2''x'' is Θ(''x''), but is not ''o''(''x'').
History (Bachmann–Landau, Hardy, and Vinogradov notations)

The symbol O was first introduced by number theorist Paul Bachmann in 1894, in the second volume of his book ''Analytische Zahlentheorie'' ("Edmund Landau
Edmund Georg Hermann Landau (14 February 1877 – 19 February 1938) was a German mathematician who worked in the fields of number theory and complex analysis.
Biography
Edmund Landau was born to a Jewish family in Berlin. His father was Leopol ...

adopted it, and was thus inspired to introduce in 1909 the notation o; hence both are now called Landau symbols. These notations were used in applied mathematics during the 1950s for asymptotic analysis.
The symbol $\backslash Omega$ (in the sense "is not an ''o'' of") was introduced in 1914 by Hardy and Littlewood. Hardy and Littlewood also introduced in 1916 the symbols $\backslash Omega\_R$ ("right") and $\backslash Omega\_L$ ("left"), precursors of the modern symbols $\backslash Omega\_+$ ("is not smaller than a small o of") and $\backslash Omega\_-$ ("is not larger than a small o of"). Thus the Omega symbols (with their original meanings) are sometimes also referred to as "Landau symbols". This notation $\backslash Omega$ became commonly used in number theory at least since the 1950s.E. C. Titchmarsh, The Theory of the Riemann Zeta-Function (Oxford; Clarendon Press, 1951)
In the 1970s the big O was popularized in computer science by Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...

, who introduced the related Theta notation, and proposed a different definition for the Omega notation.
Landau never used the big Theta and small omega symbols.
Hardy's symbols were (in terms of the modern ''O'' notation)
:$f\; \backslash preccurlyeq\; g\backslash iff\; f\; \backslash in\; O(g)$ and $f\backslash prec\; g\backslash iff\; f\backslash in\; o(g);$
(Hardy however never defined or used the notation $\backslash prec\backslash !\backslash !\backslash prec$, nor $\backslash ll$, as it has been sometimes reported).
Hardy introduced the symbols $\backslash preccurlyeq$ and $\backslash prec$ (as well as some other symbols) in his 1910 tract "Orders of Infinity", and 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.
Hardy's notation is not used anymore. On the other hand, in the 1930s,See for instance "A new estimate for ''G''(''n'') in Waring's problem" (Russian). Doklady Akademii Nauk SSSR 5, No 5-6 (1934), 249–253. Translated in English in: 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, 1985. the Russian number theorist Ivan Matveyevich Vinogradov introduced his notation $\backslash ll$, which has been increasingly used in number theory instead of the $O$ notation. We have
:$f\backslash ll\; g\; \backslash iff\; f\; \backslash in\; O(g),$
and frequently both notations are used in the same paper.
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
Omicron (; uppercase Ο, lowercase ο, ell, όμικρον) is the 15th letter of the Greek alphabet. This letter is derived from the Phoenician letter ayin: . In classical Greek, omicron represented the close-mid back rounded vowel in contr ...

, probably in reference to his definition of the symbol Omega
Omega (; capital: Ω, lowercase: ω; Ancient Greek ὦ, later ὦ μέγα, Modern Greek ωμέγα) is the twenty-fourth and final letter in the Greek alphabet. In the Greek numeric system/isopsephy (gematria), it has a value of 800. The wo ...

. The digit zero should not be used.
See also

*Asymptotic expansion In mathematics, an asymptotic expansion, asymptotic series or Poincaré expansion (after Henri Poincaré) is a formal series of functions which has the property that truncating the series after a finite number of terms provides an approximation t ...

: Approximation of functions generalizing Taylor's formula
* Asymptotically optimal algorithm: A phrase frequently used to describe an algorithm that has an upper bound asymptotically within a constant of a lower bound for the problem
* Big O in probability notation: ''OLimit inferior and limit superior
In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting (that is, eventual and extreme) bounds on the sequence. They can be thought of in a similar fashion for a function (see limit of a function). For a ...

: An explanation of some of the limit notation used in this article
* Master theorem (analysis of algorithms)
In the analysis of algorithms, the master theorem for divide-and-conquer recurrences provides an asymptotic analysis (using Big O notation) for recurrence relations of types that occur in the analysis of many divide and conquer algorithms. The ap ...

: For analyzing divide-and-conquer recursive algorithms using Big O notation
* Nachbin's theorem: A precise method of bounding complex analytic functions so that the domain of convergence of integral transform
In mathematics, an integral transform maps a function from its original function space into another function space via integration, where some of the properties of the original function might be more easily characterized and manipulated than i ...

s can be stated
* Order of approximation
In science, engineering, and other quantitative disciplines, order of approximation refers to formal or informal expressions for how accurate an approximation is.
Usage in science and engineering
In formal expressions, the ordinal number used b ...

* Computational complexity of mathematical operations
References and notes

Further reading

* * * * * * * * * *External links

Growth of sequences — OEIS (Online Encyclopedia of Integer Sequences) Wiki

Introduction to Asymptotic Notations

Big-O Notation – What is it good for

Big O Notation explained in plain english

An example of Big O in accuracy of central divided difference scheme for first derivative

{{Webarchive, url=https://web.archive.org/web/20181007223123/https://autarkaw.org/2013/01/30/making-sense-of-the-big-oh/ , date=2018-10-07

A Gentle Introduction to Algorithm Complexity Analysis

Mathematical notation Asymptotic analysis Analysis of algorithms