Big-O Notation · aiwiki.page

Big-O notation is a notation in mathematics that bounds the magnitude of a function by a constant multiple of another function as its argument approaches a specified limit. In computer science, it commonly describes how the running time or memory requirements of an algorithm increase with input size. It expresses an asymptotic upper bound, not necessarily an exact growth rate, and disregards constant factors and behavior outside the relevant limiting region. (xlinux.nist.gov)

Formal definition

For functions $f$ and $g$ defined on sufficiently large positive integers, with $g(n)>0$ eventually, the statement

f(n)=O(g(n))\qquad(n\to\infty)

means that there exist constants $C>0$ and $n_0$ such that

|f(n)|\le Cg(n) \quad\text{for every }n\ge n_0.

The constants must not depend on $n$ . For nonnegative resource-counting functions, the absolute-value signs can be omitted. The threshold allows the inequality to fail for finitely many small inputs without invalidating the bound. (xlinux.nist.gov)

More generally, in mathematical analysis, $f(x)=O(g(x))$ as $x\to a$ means that $|f(x)/g(x)|$ remains bounded near the relevant limit, wherever the ratio is defined. The argument may approach infinity, zero, or another point; it need not represent input size. (dlmf.nist.gov)

Strictly, $O(g)$ denotes a set of functions satisfying the bound, so $f\in O(g)$ makes its meaning explicit. The conventional equals sign in $f=O(g)$ does not express ordinary symmetric equality: one cannot reverse the statement and infer $g=O(f)$ . (ocw.mit.edu)

Examples and calculation rules

Consider the polynomial

f(n)=3n^2+5n+7.

For $n\ge1$ , $f(n)\le15n^2$ , establishing $f(n)=O(n^2)$ . It is also $O(n^3)$ , demonstrating that a valid upper bound need not be the most informative one. Constant factors and lower-degree terms do not change the polynomial’s leading growth order. (xlinux.nist.gov)

For eventually nonnegative comparison functions, the definition gives useful rules:

If $f=O(g)$ and $h=O(k)$ , then $f+h=O(g+k)$ .
Under the same assumptions, $fh=O(gk)$ .
If $f=O(g)$ and $g=O(h)$ , then $f=O(h)$ .
Multiplication by a fixed nonzero constant leaves the Big-O class unchanged. (cs.yale.edu)

These rules must be applied to actual operation counts. Nested loops do not automatically imply quadratic time: their iteration limits and the cost of their bodies determine the total work. (introcs.cs.princeton.edu)

Algorithm analysis and growth classes

Within computational complexity, Big-O notation describes resource usage relative to a stated input-size measure and computational model. Time complexity counts operations, while space complexity measures storage. The same data structure or algorithm may therefore have different time and space bounds. (xlinux.nist.gov)

Common bounds include the following, assuming constant-cost elementary operations:

Bound	Conventional description	Example
$O(1)$	Constant	Accessing an array element by index
$O(\log n)$	Logarithmic	[[binary-search
$O(n)$	Linear	Scanning all elements
$O(n\log n)$	Linearithmic	[[merge-sort
$O(n^2)$	Quadratic	Examining every pair of elements
$O(2^n)$	Exponential	Enumerating every subset of $n$ elements

Changing the fixed base of a logarithm greater than one changes only a constant factor, so it does not change these Big-O classes. (cs.princeton.edu)

Algorithms using recursion often lead to recurrence relations. For example, the divide-and-conquer structure of merge sort produces a recurrence with two half-sized subproblems and linear merging work, yielding an $O(n\log n)$ time bound. (introcs.cs.princeton.edu)

Big-O does not inherently mean “worst case.” A bound may describe worst-case, best-case, or average-case cost, provided the function being bounded is specified. An average-case claim requires assumptions about inputs; an expected bound for a randomized algorithm can instead average over its internal random choices. (algs4.cs.princeton.edu)

Related asymptotic notation

Several related symbols distinguish different kinds of comparison. For eventually positive functions:

Big-Omega notation, $f=\Omega(g)$ , gives an asymptotic lower bound.
Big-Theta notation, $f=\Theta(g)$ , gives both upper and lower bounds by positive constant multiples.
Little-o notation, $f=o(g)$ , means $f/g\to0$ .
Asymptotic equivalence, $f\sim g$ , means $f/g\to1$ . (cs.yale.edu)

Thus $3n^2+5n+7=\Theta(n^2)$ is sharper than merely stating $O(n^2)$ , while $n=o(n^2)$ expresses strictly smaller growth. A positive finite limit of $f/g$ establishes a Theta bound, but a Big-O bound does not require that ratio to converge. (ocw.mit.edu)

Approximation errors and interpretive limits

In asymptotic expansions, Big-O can specify the magnitude of a remainder. For example,

e^x=1+x+O(x^2)\qquad(x\to0)

means that the difference $e^x-1-x$ is bounded in magnitude by a constant times $x^2$ sufficiently near zero. Unlike a runtime bound at infinity, this describes an error shrinking toward zero. (dlmf.nist.gov)

An asymptotic runtime bound does not specify execution time in seconds. Constant factors, implementation details, and machine characteristics can affect practical performance; a smaller asymptotic bound need not imply faster execution at every finite input size. Input representation also matters: the number of stored items and the number of bits needed to encode them are different size measures. (introcs.cs.princeton.edu)