HOME

TheInfoList



OR:

Big ''O'' notation is a mathematical notation that describes the limiting behavior of a
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-oriente ...
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 dialectic ...
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 Leopold ...
, and others, collectively called Bachmann–Landau notation or asymptotic notation. The letter O was chosen by Bachmann to stand for ''
Ordnung The Ordnung is a set of rules for Amish, Old Order Mennonite and Conservative Mennonite living. ''Ordnung'' () is the German word for order, discipline, rule, arrangement, organization, or system. Because the Amish have no central church governme ...
'', 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 English_numerals#Ordi ...
. In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, 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 Diric ...
, big O notation is often used to express a bound on the difference between an
arithmetical function In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function ''f''(''n'') whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their d ...
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 quantifying ...
. 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 In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an element ...
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 Real may refer to: Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Spanish colonial real Music Albums * ''Real'' (L'Arc-en-Ciel album) (2000) * ''Real'' (Bright album) (2010) ...
or
complex Complex commonly refers to: * Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe ** Complex system, a system composed of many components which may interact with each ...
valued function and let g, the comparison function, be a real valued function. Let both functions be defined on some unbounded
subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
of the positive
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s, and g(x) be strictly positive for all large enough values of x. One writes f(x) = O\bigl( g(x)\bigr)\quad\textx\to\infty if the
absolute 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), an ...
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\bigl(g(x)\bigr) if there exists a positive real number M and a real number x_0 such that , f(x), \le M g(x) \quad \text x \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\bigl( g(x) \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\bigl( g(x) \bigr)\quad\textx \to a if there exist positive numbers \delta and M such that for all defined x with , f(x), \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 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 ...
: f(x) = O\bigl( g(x) \bigr) \quad \text x \to a if \limsup_ \frac < \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 contai ...
a (whether \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 \textstyle \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 ...
) 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\bigl(g(x)\bigr) iff there exist positive integer numbers M and n_0 such that f(n) \le M g(n) for all n \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 the
formal 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), \le M x^4 for some suitable choice of and and for all . To prove this, let and . Then, for all : \begin , 6x^4 - 2x^3 + 5, &\le 6x^4 + , 2x^3, + 5\\ &\le 6x^4 + 2x^4 + 5x^4\\ &= 13x^4 \end so , 6x^4 - 2x^3 + 5, \le 13 x^4 .


Usage

Big O notation has two main areas of application: * In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor serie ...
or
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 to ...
* In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, 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 re ...
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 Infinite may refer to: Mathematics *Infinite set, a set that is not a finite set *Infinity, an abstract concept describing something without any limit Music * Infinite (group), a South Korean boy band *''Infinite'' (EP), debut EP of American m ...
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 referr ...
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 Term may refer to: * Terminology, or term, a noun or compound word used in a specific context, in particular: **Technical term, part of the specialized vocabulary of a particular field, specifically: ***Scientific terminology, terms used by scient ...
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, the
coefficient 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 var ...
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) \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 an ...
.


Infinitesimal asymptotics

Big O can also be used to describe the
error term In mathematics and statistics, an error term is an additive type of error. Common examples include: * errors and residuals in statistics, e.g. in linear regression * the error term in numerical integration In analysis, numerical integration ...
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: :\begin e^x &=1+x+\frac+\frac+\frac+\dotsb &\text x\\ pt &=1+x+\frac+O(x^3) &\text x\to 0\\ pt &=1+x+O(x^2) &\text x\to 0 \end The second expression (the one with ''O''(''x''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.


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 \log n + 5 (\log n)^4 + 3n^2 + 2n^3 = O(n^3) \qquad\text n\to\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 for
integer 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 suf ...
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) \text f_2 = O(g_2) \Rightarrow f_1 f_2 = O(g_1 g_2) :f\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(\max(g_1, g_2)). It follows that if f_1 = O(g) and f_2 = O(g) then f_1+f_2 \in O(g) . In other words, this second statement says that O(g) is a
convex 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, \cdot g) = O(g). In other words, if f = O(g), then k \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 \R^n. We say :f(\mathbf)\textO(g(\mathbf))\quad\text\mathbf\to\infty if and only if there exist constants M and C > 0 such that , f(\mathbf), \le C , g(\mathbf), for all \mathbf with x_i \geq M for some i. Equivalently, the condition that x_i \geq M for some i can be written \, \mathbf\, _ \ge M, where \, \mathbf\, _ denotes the Chebyshev norm. For example, the statement :f(n,m) = n^2 + m^3 + O(n+m) \quad\text n,m\to\infty asserts that there exist constants ''C'' and ''M'' such that : , f(n,m) - (n^2 + m^3), \le C , n+m, whenever either m \geq M or n \geq M holds. This definition allows all of the coordinates of \mathbf to increase to infinity. In particular, the statement :f(n,m) = O(n^m) \quad \text n,m\to\infty (i.e., \exists C \,\exists M \,\forall n \,\forall m\,\cdots) is quite different from :\forall m\colon~f(n,m) = O(n^m) \quad\text n\to\infty (i.e., \forall m \, \exists C \, \exists M \, \forall n \, \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
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_an_...
,_since_the_use_of_the_equals_sign_could_be_misleading_as_it_suggests_a_symmetry_that_this_statement_does_not_have._As_ 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_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_De_Bruijn_is_a_Dutch_surname_meaning_"the_brown"._Notable_people_with_the_surname_include: *__(1887–1968),_Dutch_politician *_Brian_de_Bruijn_(b._1954),_Dutch-Canadian_ice_hockey_player *_Chantal_de_Bruijn_(b._1976),_Dutch_field_hockey_defender *_...
_says,__is_true_but__is_not._Donald_Knuth.html" ;"title="Nicolaas_Govert_de_Bruijn.html" "title=",\infty)^2, but not if they are defined on [0,\infty)^2. This is not the only generalization of big O to multivariate functions, and in practice, there is some inconsistency in the choice of definition.


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
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 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 De Bruijn is a Dutch surname meaning "the brown". Notable people with the surname include: * (1887–1968), Dutch politician * Brian de Bruijn (b. 1954), Dutch-Canadian ice hockey player * Chantal de Bruijn (b. 1976), Dutch field hockey defender * ...
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 an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
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''2), and after the subroutine runs the algorithm must take an additional steps before it terminates. Thus the overall time complexity of the algorithm can be expressed as . Here the terms are subsumed within the faster-growing ''O''(''n''2). Again, this usage disregards some of the formal meaning of the "=" symbol, but it does allow one to use the big O notation as a kind of convenient placeholder.


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\to\infty: \begin (n+1)^2 & = n^2 + O(n), \\ (n + O(n^)) \cdot (n + O(\log n))^2 & = n^3 + O(n^), \\ n^ & = O(e^n). \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''''n'') such that ''n''''f''(''n'') = ''g''(''n'')." In terms of the "set notation" above, the meaning is that the class of functions represented by the left side is a subset of the class of functions represented by the right side. In this use the "=" is a formal symbol that unlike the usual use of "=" is not a
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 Tex may refer to: People and fictional characters * Tex (nickname), a list of people and fictional characters with the nickname * Joe Tex (1933–1982), stage name of American soul singer Joseph Arrington Jr. Entertainment * ''Tex'', the Italian ...
, 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 \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\left(n^n\right) to derive simpler formulas for asymptotic complexity. For any k>0 and O(n^c(\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 number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s, such that ''g''(''x'') is strictly positive for all large enough values of ''x''. One writes :f(x) = o(g(x)) \quad \text x \to \infty if for every positive constant there exists a constant x_0 such that :, f(x), \leq \varepsilon g(x) \quad \text x \geq x_0. For example, one has : 2x = o(x^2) and 1/x = o(1),     both as x \to \infty . The difference between the definition of the
big-O notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Land ...
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., 2001
Introduction 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 :\lim_\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 \cdot f = o(g), and : if f = o(F) and g = o(G) then f \cdot g = o(F \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 \Omega, read "big omega". There are two widespread and incompatible definitions of the statement :f(x)=\Omega(g(x)) as x \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 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 Diric ...
, 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 Godfrey Harold Hardy (7 February 1877 – 1 December 1947) was an English mathematician, known for his achievements in number theory and mathematical analysis. In biology, he is known for the Hardy–Weinberg principle, a basic principle of pop ...
and
John 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 Ramanu ...
introduced the new symbol \Omega, which is defined as follows: :f(x) = \Omega(g(x)) as x\to\infty if \limsup_ \left, \frac\ > 0. Thus f(x)=\Omega(g(x)) is the negation of f(x)=o(g(x)). In 1916 the same authors introduced the two new symbols \Omega_R and \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 journ ...
'', vol. 41, 1916.
:f(x)=\Omega_R(g(x)) as x\to\infty if \limsup_ \frac> 0; :f(x)=\Omega_L(g(x)) as x\to\infty if \liminf_ \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 Leopold ...
, 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; \Omega_R became \Omega_+ and \Omega_L became \Omega_-. These three symbols \Omega, \Omega_+, \Omega_-, as well as f(x)=\Omega_\pm(g(x)) (meaning that f(x)=\Omega_+(g(x)) and f(x)=\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 Diric ...
.Aleksandar Ivić. The Riemann zeta-function, chapter 9. John Wiley & Sons 1985.


= Simple examples

= We have :\sin x=\Omega(1) as x\to\infty, and more precisely :\sin x=\Omega_\pm(1) as x\to\infty. We have :\sin x+1=\Omega(1) as x\to\infty, and more precisely :\sin x+1=\Omega_+(1) as x\to\infty; however :\sin x+1\not=\Omega_-(1) as x\to\infty.


The Knuth definition

In 1976
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 ...
published a paper to justify his use of the \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)=\Omega(g(x))\Leftrightarrow g(x)=O(f(x)) with the comment: "Although I have changed Hardy and Littlewood's definition of \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,\Theta,\sim, (Knuth's version of) \Omega, \omega on functions correspond to <,\leq,\approx,=, \geq,> on the real line (the Hardy–Littlewood version of \Omega , however, doesn't correspond to any such description). Computer science uses the big O , big Theta \Theta , little o , little omega \omega and Knuth's big Omega \Omega notations. Analytic number theory often uses the big O , small o , Hardy–Littlewood's big Omega \Omega (with or without the +, − or ± subscripts) and \sim notations. The small omega \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 asymptotic
tight 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''3 + 22''n''2 + 58, all of the following are generally acceptable, but tighter bounds (such as numbers 2 and 3 below) are usually strongly preferred over looser bounds (such as number 1 below). # # # The equivalent English statements are respectively: #''T''(''n'') grows asymptotically no faster than ''n''100 #''T''(''n'') grows asymptotically no faster than ''n''3 #''T''(''n'') grows asymptotically as fast as ''n''3. So 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 ''T''(''n'') represents the running time of a newly developed algorithm for input size ''n'', the inventors and users of the algorithm might be more inclined to put an upper asymptotic bound on how long it will take to run without making an explicit statement about the lower asymptotic bound.


Other notation

In their book ''
Introduction to Algorithms ''Introduction to Algorithms'' is a book on computer programming by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The book has been widely used as the textbook for algorithms courses at many universities and is co ...
'', Cormen, Leiserson, Rivest and
Stein 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 Austr ...
consider the set of functions ''f'' which satisfy : f(n) = O(g(n))\quad(n\to\infty)~. In a correct notation this set can, for instance, be called ''O''(''g''), where :O(g) = \. 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 O* for the same purpose. Essentially, it is big O notation, ignoring logarithmic factors because the growth-rate effects of some other super-logarithmic function indicate a growth-rate explosion for large-sized input parameters that is more important to predicting bad run-time performance than the finer-point effects contributed by the logarithmic-growth factor(s). This notation is often used to obviate the "nitpicking" within growth-rates that are stated as too tightly bounded for the matters at hand (since log''k'' ''n'' is always ''o''(''n''ε) for any constant ''k'' and any ). Also the L notation, defined as :L_n alpha,c= e^ is convenient for functions that are between
polynomial 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 exa ...
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 any
normed 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" i ...
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 In mathematics, topological groups are logically the combination of groups and topological spaces, i.e. they are groups and topological spaces at the same time, such that the continuity condition for the group operations connects these two str ...
is also possible. The "limiting process" ''x'' → ''x''o can also be generalized by introducing an arbitrary
filter base In mathematics, a filter on a set X is a family \mathcal of subsets such that: # X \in \mathcal and \emptyset \notin \mathcal # if A\in \mathcal and B \in \mathcal, then A\cap B\in \mathcal # If A,B\subset X,A\in \mathcal, and A\subset B, then ...
, i.e. to directed nets ''f'' and ''g''. The ''o'' notation can be used to define
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. F ...
s and
differentiability In mathematics, a differentiable function of one real variable is a function whose derivative exists at each point in its domain. In other words, the graph of a differentiable function has a non-vertical tangent line at each interior point in its ...
in quite general spaces, and also (asymptotical) equivalence of functions, : f\sim g \iff (f-g) \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'' ("
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 Diric ...
"). The number theorist
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 Leopold ...
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 \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 \Omega_R ("right") and \Omega_L ("left"), precursors of the modern symbols \Omega_+ ("is not smaller than a small o of") and \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 \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 \preccurlyeq g\iff f \in O(g)   and   f\prec g\iff f\in o(g); (Hardy however never defined or used the notation \prec\!\!\prec, nor \ll, as it has been sometimes reported). Hardy introduced the symbols \preccurlyeq and \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 Ivan Matveevich Vinogradov ( rus, Ива́н Матве́евич Виногра́дов, p=ɪˈvan mɐtˈvʲejɪvʲɪtɕ vʲɪnɐˈɡradəf, a=Ru-Ivan_Matveyevich_Vinogradov.ogg; 14 September 1891 – 20 March 1983) was a Soviet mathematician, ...
introduced his notation \ll, which has been increasingly used in number theory instead of the O notation. We have : f\ll g \iff f \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 contras ...
, 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 0 (zero) is a number representing an empty quantity. In place-value notation Positional notation (or place-value notation, or positional numeral system) usually denotes the extension to any base of the Hindu–Arabic numeral system (or ...
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 to ...
: Approximation of functions generalizing Taylor's formula *
Asymptotically optimal algorithm In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly en ...
: 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 The order in probability notation is used in probability theory and statistical theory in direct parallel to the big-O notation that is standard in mathematics. Where the big-O notation deals with the convergence of sequences or sets of ordinary nu ...
: ''Op'', ''op'' *
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 ...
: 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 app ...
: For analyzing divide-and-conquer recursive algorithms using Big O notation *
Nachbin's theorem In mathematics, in the area of complex analysis, Nachbin's theorem (named after Leopoldo Nachbin) is commonly used to establish a bound on the growth rates for an analytic function. This article provides a brief review of growth rates, including ...
: A precise method of bounding
complex analytic Complex analysis, traditionally known as the theory of functions of a complex variable, is the branch of mathematical analysis that investigates functions of complex numbers. It is helpful in many branches of mathematics, including algebrai ...
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 in ...
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 English_numerals#Ordi ...
*
Computational complexity of mathematical operations The following tables list the computational complexity of various algorithms for common mathematical operations. Here, complexity refers to the time complexity of performing computations on a multitape Turing machine. See big O notation for an ...


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 englishAn 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