= Big O notation
{title2=$O(\mathord\cdot)$}
{wiki}
The statement $f(n)=O(g(n))$ as $n\to\infty$ means there are constants $C>0$ and $N$ such that
$$
\boxed{|f(n)|\le C|g(n)|\qquad\text{for every }n\ge N.}
$$
The same constant must work for all sufficiently large inputs. Near a finite <limit> point $a$, replace $n\ge N$ by $0<|x-a|<\delta$ within the domain. <Absolute values> allow signed or complex-valued <functions>; when discussing nonnegative operation counts they can be omitted.
The notation records an <upper bound>, not an exact leading coefficient or necessarily a tight growth order. For example, $3n^2+7n+4=O(n^2)$ because for $n\ge1$ it is at most $14n^2$. It is also $O(n^3)$, a weaker statement. A tight comparison uses <big theta notation>; a ratio tending to one uses <asymptotic equivalence>. Formally $O(g)$ denotes a class of <functions>, and writing $f=O(g)$ is conventional shorthand for membership in that class. https://live.ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/c6d8f06c6f11e3342633dec85498f551_MIT6_006S20_r01.pdf[MIT 6.006, Demaine, Ku and Solomon, Recitation 1, page 3: asymptotic upper and tight bounds]{ref}
\Image[/asymptotic-growth-constants-and-ratios.png]
{title=Constants affect finite comparisons while normalized ratios expose eventual growth}
The first panel compares stipulated operation counts $A(n)=1000n$ and $B(n)=n^2$. Although $A$ is linear and $B$ quadratic, $B(n)<A(n)$ for $1\le n<1000$; the ordering reverses beyond their crossing. These are mathematical cost models, not measured runtimes. The <time complexity> notation describes the growth of whichever cost function has been specified, whether that function represents a worst-case bound, an average, or another explicit quantity.
The middle panel gives a concrete eventual bound: $n^2+10^5n\le2n^2$ for every $n\ge10^5$. Its normalized ratio approaches one, but the threshold matters. The final panel shows the <asymptotic comparison of exponential functions>, with its geometrically shrinking relative difference.
Constants may depend on fixed parameters. For each fixed $\alpha>0$, $f_\alpha(n)=\alpha n$ is $O(n)$ with $C=\alpha$; one constant cannot cover every positive $\alpha$. A <uniform big O bound> makes this extra quantifier explicit.
The notation was already used in nineteenth-century <number theory>. In his 1976 paper, Donald E. Knuth reports Landau identifying Bachmann's 1894 book as the first appearance of $O$ known to him. Knuth's account gives the earlier mathematical setting of a notation now also common in <time complexity> analysis. https://danluu.com/knuth-big-o.pdf[Knuth, Big Omicron and big Omega and big Theta, 1976, page 19]{ref}
Back to article page
