Big O notation is a mathematical notation that describes the approximate size of a function on a domain. Big O is a member of a family of notations invented by the German mathematicians Paul Bachmann and expanded by others, collectively called Bachmann–Landau notation. The letter O stands for Ordnung, that is, the order of approximation.
In computer science, big O notation is used to classify algorithms by how their run time or space requirements grow with the input. In analytic number theory, big O notation expresses bounds on the growth of an arithmetical function, as for the remainder term in the prime number theorem. especially in computer science.
When restricted to functions which are eventually positive, the notation
: <math display="block">f(x) =O\bigl(g(x)\bigr) \qquad ~ \mathsf{ as } \quad x \to \infty</math>
means that for some real number <math display="inline">a,</math> <math display="inline">f(x) = O\bigl(g(x)\bigr)</math> in the domain <math display="inline">\left[a,\infty\right).</math> Here, the expression <math display="inline">x \to \infty</math> does not indicate a limit, but the notion that the inequality holds for large enough <math display="inline">x.</math> The expression <math display="inline">x \to \infty</math> often is omitted. the Russian number theorist introduced the notation <math>\ll,</math> which has been increasingly used in number theory Knuth's big <math> \Omega </math> enjoys widespread use today
in computer science and combinatorics.
Hardy's ≍ and Knuth's big Θ
In analytic number theory, where <math>\log^*(n) =
\begin{cases}
0, & \text{if }n \leq 1 \\
1 + \log^*(\log n), & \text{if }n>1
\end{cases}</math>
|-
|<math>O(n\log n) = O(\log n!)</math> || linearithmic, loglinear, quasilinear, or "<math>n\log n</math>" || Performing a fast Fourier transform; fastest possible comparison sort; heapsort and merge sort
|-
|<math>O(n^2)</math> || quadratic || Multiplying two <math>n</math>-digit numbers by schoolbook multiplication; simple sorting algorithms, such as bubble sort, selection sort and insertion sort; (worst-case) bound on some usually faster sorting algorithms such as quicksort, Shellsort, and tree sort
|-
|<math>O(n^c)</math> || polynomial or algebraic || Tree-adjoining grammar parsing; maximum matching for bipartite graphs; finding the determinant with LU decomposition
|-
|<math>L_n[\alpha,c] = e^{(c + o(1)) (\ln n)^\alpha (\ln \ln n)^{1-\alpha</math><br /><math display=inline> 0 < \alpha < 1</math> || L-notation or sub-exponential || Factoring a number using the quadratic sieve or number field sieve
|-
|<math>O(c^n)</math><br/><math display=inline> c>1</math> || exponential || Finding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search
|-
|<math>O(n!)</math> || factorial || Solving the travelling salesman problem via brute-force search; generating all unrestricted permutations of a poset; finding the determinant with Laplace expansion; enumerating all partitions of a set
|}
The statement <math>f(n) = O(n!)</math> is sometimes weakened to <math>f(n) = O\left(n^n\right)</math> to derive simpler formulas for asymptotic complexity.
In many of these examples, the running time is
actually <math> \Theta(g(n)) </math>, which conveys more
precision.
==Little-o notation== <!-- Little-o notation redirects here -->
For real or complex-valued functions of a real variable
<math>x</math> with <math>g(x)>0</math> for sufficiently large <math>x</math>, one writes
which is defined as follows:
:<math> f(x) = \Omega(g(x)) \quad </math> as <math>\quad x \to \infty \quad</math> if <math>\quad \limsup_{x \to \infty}\ \left|\frac{\ f(x)\ }{ g(x) }\right| > 0 ~.</math>
Thus <math>~ f(x) = \Omega(g(x)) ~</math> is the negation of <math>~ f(x) = o(g(x)) ~.</math>
In 1916 the same authors introduced the two new symbols <math>\ \Omega_R\ </math> and <math>\ \Omega_L\ ,</math> defined as:
:<math> f(x) = \Omega_R(g(x)) \quad</math> as <math>\quad x \to \infty \quad</math> if <math>\quad \limsup_{x \to \infty}\ \frac{\ f(x)\ }{ g(x) } > 0\ ;</math>
:<math> f(x)=\Omega_L(g(x)) \quad</math> as <math>\quad x \to \infty \quad</math> if <math>\quad ~ \liminf_{x \to \infty}\ \frac{\ f(x)\ }{ g(x) }< 0 ~.</math>
These symbols were used by E. Landau, with the same meanings, in 1924. Authors that followed Landau, however, use a different notation for the same definitions:
|-
| <math>f(n) = O(g(n))</math> or
<math>f(n) \ll g(n) </math> (Vinogradov's notation)
| Big O; Big Oh; Big Omicron
The small omega <math>\omega </math> notation is not used as often in analysis or in number theory.
Quality of approximations using different notation
Informally, especially in computer science, the big <math>O</math> notation often can be used somewhat differently to describe an asymptotic tight bound where using big Theta <math>\Theta</math> notation might be more factually appropriate in a given context
.
For example, when considering a function <math>T(n)=73n^3+22n^2+58</math>, all of the following are generally acceptable, but tighter bounds (such as numbers 2,3 and 4 below) are usually strongly preferred over looser bounds (such as number 1 below).
- <math>T(n)=O(n^{100})</math>
- <math>T(n)=O(n^{3})</math>
- <math>T(n)=\Theta(n^3)</math>
- <math>T(n)\sim 73n^3</math> as <math>n\to\infty</math>.
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 <math>T(n)</math> represents the running time of a newly developed algorithm for input size <math>n</math>, the inventors and users of the algorithm might be more inclined to put an upper bound on how long it will take to run without making an explicit statement about the lower bound or asymptotic behavior.
Extensions to the Bachmann–Landau notations
Another notation sometimes used in computer science is <math>\tilde{O}</math> (read soft-O), which hides polylogarithmic factors. There are two definitions in use: some authors use <math> f(n) = \tilde{O}(g(n))</math> as shorthand for <math> f(n)=O(g(n)\log^k n) </math> for some <math>k</math>, while others use it as shorthand for <math> f(n)=O(g(n)\log^k g(n)) </math>
.
When <math>g(n)</math> is polynomial in <math>n</math>, there is no difference; however, the latter definition allows one to say, e.g. that <math>n2^n = \tilde O(2^n)</math> while the former definition allows for <math>\log^k n = \tilde O(1)</math> for any constant <math>k</math>. Some authors write O<sup>*</sup> for the same purpose as the latter definition. Essentially, it is less precise version of the big O notation, ignoring logarithmic factors in the growth-rate of the function. Since <math> \log^k n = o(n^\varepsilon)</math>
for any constant <math>k</math> and any
<math>\varepsilon>0</math>, logarithmic factors are far less significant than powers of <math> n </math> and even more insignificant compared with exponentials.
Also, the L notation, defined as
:<math>L_n[\alpha,c] = e^{(c + o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha,</math>
is convenient for functions that are between polynomial and exponential in terms of <math>\log n</math>.
Generalizations and related usages
The generalization to functions taking values in any normed vector space is straightforward (replacing absolute values by norms), where <math>f</math> and <math>g</math> need not take their values in the same space. A generalization to functions <math>g</math> taking values in any topological group is also possible.
The "limiting process" <math>x\to x_0</math> can also be generalized by introducing an arbitrary filter base, i.e. to directed nets <math>f</math> and <math>g</math>. The <math>o</math> notation can be used to define derivatives and differentiability in quite general spaces, and also (asymptotical) equivalence of functions,
:<math> f\sim g \iff (f-g) \in o(g) </math>
which is an equivalence relation and a more restrictive notion than the relationship "<math>f</math> is <math>\Theta(g)</math>" from above. (It reduces to <math>\lim f/g = 1</math> if <math>f</math> and <math>g</math> are positive real valued functions.) For example, <math>2x=\Theta(x)</math> is, but
<math> 2x-x \ne o(x) </math>.
History
In 1870, Paul du Bois-Reymond
defined <math> f(x) \succ \phi(x) </math>, <math> f(x) \sim \phi(x) </math> and <math> f(x) \prec \phi(x)</math>
to mean, respectively,
<math display="block">
\lim_{x\to\infty}\frac{f(x)}{\phi(x)}=\infty, \quad
\lim_{x\to\infty}\frac{f(x)}{\phi(x)}>0, \quad
\lim_{x\to\infty}\frac{f(x)}{\phi(x)}=0.
</math>
These were not widely adopted and are not used today.
The first and third are symmetric: <math> f(x) \prec \phi(x)</math> means the same as <math> \phi(x) \succ f(x)</math>. Landau later adopted <math> \sim </math> with the narrower definition that the limit of <math> f(x)/\phi(x)</math> equals 1.
The symbol O was first introduced by the number theorist Paul Bachmann in 1894, in the second volume of his book Analytische Zahlentheorie ("analytic number theory"). The number theorist Edmund Landau adopted it, and was thus inspired to introduce in 1909 the notation o;
The symbol <math>\Omega</math> (in the sense "is not little o of") was introduced in 1914 by Hardy and Littlewood.
Hardy introduced the symbols <math>\preccurlyeq </math> and advocated for Bois-Reymond's <math>\prec </math> (as well as the already mentioned other symbols) in his 1910 tract "Orders of Infinity",
Hardy's symbols <math>\preccurlyeq</math> and <math>\mathbin{\,\asymp\;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-}</math> are not used any more.
The symbol <math>\sim</math>, although it had been used before with different meanings,
Knuth describes such statements as "one-way equalities", since if the sides could be reversed, "we could deduce ridiculous things like
<math>n=n^2</math> from the identities <math>n=O(n^2)</math> and <math> n^2=O(n^2) </math>. In another letter, Knuth also pointed out that
For these reasons, some advocate for using set notation and write <math> f(x) \in O(g(x)) </math>,
read as "<math>f(x)</math> is an element of
<math>O(g(x))</math>", or "<math>f(x)</math> is in the set
<math>O(g(x))</math>" thinking of
<math>O(g(x))</math> as the class of all functions
<math>h(x)</math> such that <math>h(x)=O(g(x))</math>. In TeX, it is produced by simply typing 'O' inside math mode. Unlike Greek-named Bachmann–Landau notations, it needs no special symbol. However, some authors use the calligraphic variant <math>\mathcal{O}</math> instead.
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,