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 German mathematicians Paul Bachmann, Edmund Landau, 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 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, big O notation is often used to express a bound on the difference between an arithmetical function and a better understood approximation; one well-known example is the remainder term in the prime number theorem. 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 asymptotic growth rate may be represented using the same O notation. The letter O is used because the growth rate of a function is also referred to as the order of the function. A description of a function in terms of big O notation only provides an upper bound on the growth rate of the function.

Associated with big O notation are several related notations, using the symbols ${\displaystyle o}$, ${\displaystyle \Omega }$, ${\displaystyle \omega }$, and ${\displaystyle \Theta }$ to describe other kinds of bounds on asymptotic growth rates.

Let ${\displaystyle f,}$ the function to be estimated, be a real or complex valued function, and let ${\displaystyle g,}$ the comparison function, be a real valued function. Let both functions be defined on some unbounded subset of the positive real numbers, and ${\displaystyle g(x)}$ be non-zero (often, but not necessarily, strictly positive) for all large enough values of ${\displaystyle x.}$ One writes $${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to \infty }$$ and it is read "${\displaystyle f(x)}$ is big O of ${\displaystyle g(x)}$" or more often "${\displaystyle f(x)}$ is of the order of ${\displaystyle g(x)}$" if the absolute value of ${\displaystyle f(x)}$ is at most a positive constant multiple of the absolute value of ${\displaystyle g(x)}$ for all sufficiently large values of ${\displaystyle x.}$ That is, ${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}}$ if there exists a positive real number ${\displaystyle M}$ and a real number ${\displaystyle x_{0}}$ such that $${\displaystyle |f(x)|\leq M\ |g(x)|\quad {\text{ for all }}x\geq x_{0}~.}$$ In many contexts, the assumption that we are interested in the growth rate as the variable ${\displaystyle \ x\ }$ goes to infinity or to zero is left unstated, and one writes more simply that $${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}.}$$ The notation can also be used to describe the behavior of ${\displaystyle f}$ near some real number ${\displaystyle a}$ (often, ${\displaystyle a=0}$): we say $${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}\ x\to a}$$ if there exist positive numbers ${\displaystyle \delta }$ and ${\displaystyle M}$ such that for all defined ${\displaystyle x}$ with ${\displaystyle 0<|x-a|<\delta ,}$ $${\displaystyle |f(x)|\leq M|g(x)|.}$$ As ${\displaystyle g(x)}$ is non-zero for adequately large (or small) values of ${\displaystyle x,}$ both of these definitions can be unified using the limit superior: $${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}\ x\to a}$$ if $${\displaystyle \limsup _{x\to a}{\frac {\left|f(x)\right|}{\left|g(x)\right|}}<\infty .}$$ And in both of these definitions the limit point ${\displaystyle a}$ (whether ${\displaystyle \infty }$ or not) is a cluster point of the domains of ${\displaystyle f}$ and ${\displaystyle g,}$ i. e., in every neighbourhood of ${\displaystyle a}$ there have to be infinitely many points in common. Moreover, as pointed out in the article about the limit inferior and limit superior, the ${\displaystyle \textstyle \limsup _{x\to a}}$ (at least on the extended real number line) always exists.

In computer science, a slightly more restrictive definition is common: ${\displaystyle f}$ and ${\displaystyle g}$ are both required to be functions from some unbounded subset of the positive integers to the nonnegative real numbers; then ${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}}$ if there exist positive integer numbers ${\displaystyle M}$ and ${\displaystyle n_{0}}$ such that ${\displaystyle |f(n)|\leq M|g(n)|}$ for all ${\displaystyle n\geq n_{0}.}$

In typical usage the ${\displaystyle O}$ notation is asymptotical, that is, it refers to very large ${\displaystyle x}$. In this setting, the contribution of the terms that grow "most quickly" will eventually make the other ones irrelevant. As a result, the following simplification rules can be applied:

For example, let ${\displaystyle f(x)=6x^{4}-2x^{3}+5}$, and suppose we wish to simplify this function, using ${\displaystyle O}$ notation, to describe its growth rate as ${\displaystyle x\rightarrow \infty }$. This function is the sum of three terms: ${\displaystyle 6x^{4}}$, ${\displaystyle -2x^{3}}$, and ${\displaystyle 5}$. Of these three terms, the one with the highest growth rate is the one with the largest exponent as a function of ${\displaystyle x}$, namely ${\displaystyle 6x^{4}}$. Now one may apply the second rule: ${\displaystyle 6x^{4}}$is a product of ${\displaystyle 6}$ and ${\displaystyle x^{4}}$ in which the first factor does not depend on ${\displaystyle x}$. Omitting this factor results in the simplified form ${\displaystyle x^{4}}$. Thus, we say that ${\displaystyle f(x)}$ is a "big O" of ${\displaystyle x^{4}}$. Mathematically, we can write ${\displaystyle f(x)=O(x^{4})}$. One may confirm this calculation using the formal definition: let ${\displaystyle f(x)=6x^{4}-2x^{3}+5}$ and ${\displaystyle g(x)=x^{4}}$. Applying the formal definition from above, the statement that ${\displaystyle f(x)=O(x^{4})}$ is equivalent to its expansion, $${\displaystyle |f(x)|\leq Mx^{4}}$$ for some suitable choice of a real number ${\displaystyle x_{0}}$ and a positive real number ${\displaystyle M}$ and for all ${\displaystyle x>x_{0}}$. To prove this, let ${\displaystyle x_{0}=1}$ and ${\displaystyle M=13}$. Then, for all ${\displaystyle x>x_{0}}$: $${\displaystyle {\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|-2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}}$$ so $${\displaystyle |6x^{4}-2x^{3}+5|\leq 13x^{4}.}$$