Big O notation ( $O (\cdot)$ )

The statement

f (n) = O (g (n))

n \to \infty

means there are constants

C > 0

and

N

such that

∣ f (n) ∣ \leq C ∣ g (n) ∣ for every n \geq N .

(1)

The same constant must work for all sufficiently large inputs. Near a finite limit point

a

, replace

n \geq N

0 < ∣ x - a ∣ < δ

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,

3 n^{2} + 7 n + 4 = O (n^{2})

because for

n \geq 1

it is at most

14 n^{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. ^[ref]

Figure 1.
Constants affect finite comparisons while normalized ratios expose eventual growth
. **Details**.

The first panel compares stipulated operation counts

A (n) = 1000 n

and

B (n) = n^{2}

. Although

A

is linear and

B

quadratic,

B (n) < A (n)

for

1 \leq 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} + 1 0^{5} n \leq 2 n^{2}

for every

n \geq 1 0^{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

α > 0

f_{α} (n) = α n

O (n)

with

C = α

; one constant cannot cover every positive

α

. 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. ^[ref]

Table of contents

Failure of unrestricted Big O composition

 0  0

From

f_{1} = O (g_{1})

and

f_{2} = O (g_{2})

one cannot generally deduce

f_{2} \circ f_{1} = O (g_{2} \circ g_{1})

. For

f_{1} (n) = 2 n

g_{1} (n) = n

and

f_{2} (n) = g_{2} (n) = 2^{n}

, the two premises hold, but the ratio of the compositions is

2^{n}

, which is unbounded. A constant scaling of an inner argument can change the growth order after an exponential function is applied.

Finite-prefix extension of a big O bound ( $f = O (g), g (n) \neq = 0 ⟹ sup_{n} ∣ f (n) / g (n) ∣ < \infty$ )

 0  0

Let

f, g : N \to R

, with

g (n) \neq = 0

everywhere. An eventual bound

∣ f (n) ∣ \leq C ∣ g (n) ∣

can be made valid for all natural numbers by enlarging

C

to the maximum of itself and the finitely many ratios

∣ f (n) ∣/∣ g (n) ∣

before its cutoff. Conversely, a global bound is an eventual bound. Nonvanishing on the finite prefix is essential:

g (0) = 0

f (0) = 1

, and

f (n) = g (n) = 1

for

n \geq 1

give an eventual bound but no global one. The useful principle is that finitely many finite ratios cannot destroy a big O notation.

Big omega notation ( $f = Ω (g)$ )

 0  0

For real-valued functions on the natural numbers,

f (n) = Ω (g (n))

means that constants

c > 0

and

N

satisfy

∣ f (n) ∣ \geq c ∣ g (n) ∣

for every

n \geq N

. This is an eventual lower bound on magnitude. In algorithm analysis the functions are usually nonnegative, so the absolute values can be omitted. Together with the upper bound of big O notation, it gives big theta notation. This is the algorithmic lower-bound convention for

Ω

, rather than a convention expressing only a positive limit superior along a subsequence.

Polynomial versus exponential growth ( $n^{k} = o (a^{n}) (a > 1)$ )

 0  0

Every fixed power is eventually smaller than an exponential function with base

a > 1

: for a fixed nonnegative integer

k

n^{k} / a^{n} \to 0

. To prove this, the ratio of successive terms is

(1 + 1/ n)^{k} / a \to 1/ a < 1

, so after finitely many terms the ratio is bounded by a fixed

q < 1

. A geometric series bound then proves the limit. In particular

n^{k} = O (a^{n})

in big O notation.

Little o notation ( $f = o (g)$ )

 1  0

When

g

is nonzero sufficiently near the specified limit, little o notation means

f = o (g) ⟺ f / g ⟶ 0.

(1)

Thus the numerator becomes negligible relative to the denominator's scale. As

n \to \infty

n = o (n^{2})

because

n / n^{2} = 1/ n \to 0

; as

h \to 0

h^{2} = o (h)

because

h^{2} / h = h \to 0

. The direction of the limit changes the comparison. ^[ref]

Equivalently, for every

ε > 0

, the bound

∣ f ∣ \leq ε ∣ g ∣

holds sufficiently near that limit, with a threshold allowed to depend on

ε

. Big O notation needs only one fixed multiplier, making it weaker. For example,

2 n = O (n)

but

2 n

is not

o (n)

. The useful relation

f \sim g ⟺ f - g = o (g)

turns asymptotic equivalence into a statement about a negligible remainder.

Big theta notation ( $f = Θ (g)$ )

 0  0

At the specified limit, big theta notation means that two positive constants give both-sided bounds:

c ∣ g ∣ \leq ∣ f ∣ \leq C ∣ g ∣ (0 < c \leq C)

(1)

sufficiently near the limit. Equivalently,

f = O (g)

and

g = O (f)

in big O notation. In operation-count analysis,

3 n^{2} + 7 n + 4 = Θ (n^{2})

for

n \geq 1

, using

c = 3

and

C = 14

. This supplies a tight scale without asserting that the normalized ratio tends to one.

For an example with no limiting ratio, let

f (n) = n (2 + (- 1)^{n})

for positive integers

n

. Then

n \leq f (n) \leq 3 n

, so

f (n) = Θ (n)

, but

f (n) / n

alternates between one and three. A tight growth order is therefore weaker than asymptotic equivalence. The constant bounds also do not fix an exact factor by which a function changes when its argument doubles.

Donald E. Knuth's 1976 paper proposes using

Θ

for two-sided constant bounds in algorithm analysis. He credits Bob Tarjan and Mike Paterson with independently suggesting the notation. His discussion gives a concrete motivation for distinguishing an eventual upper estimate from a tight comparison. ^[ref]

Uniform big O bound ( $∣ f_{α} (n) ∣ \leq C ∣ g (n) ∣ with C, N independent of α$ )

 0  0

A uniform big O bound for a family of functions uses one multiplier and one threshold for every allowed parameter:

\exists C > 0, N \forall α \in A \forall n \geq N : ∣ f_{α} (n) ∣ \leq C ∣ g (n) ∣.

(1)

The order of the quantifiers matters. For

f_{α} (n) = α n

0 \leq α \leq 10

admits

C = 10

and

N = 1

, while the unbounded family

α > 0

admits no such constant. Each individual member nevertheless satisfies

f_{α} = O (n)

. A uniform bound is useful when an approximation must work across a whole parameter range, rather than separately for each fixed parameter.

 View more

Big O notation is a mathematical concept used to describe the performance or complexity of an algorithm in terms of time or space requirements as the input size grows. It provides a high-level understanding of how the runtime or space requirements of an algorithm scale with increasing input sizes, allowing for a general comparison between different algorithms. In Big O notation, we express the upper bound of an algorithm's growth rate, ignoring constant factors and lower-order terms.

 Read the full article

Big O notation by

Ciro Santilli  40 Updated 2025-07-16

 View more

Module bound above, possibly multiplied by a constant:

f (x) = O (g (x))

(1)

is defined as:

\exists M > 0\exists x_{0} \forall x > x_{0} : ∣ f (x) ∣ \leq M g (x)

(2)

E.g.:

$\forall c \in R x + c = O (x)$ . For $c < 0$ , $M = 1$ is enough. Otherwise, any $M > 1$ will do, the bottom line will always catch up to the top one eventually.

 Read the full article

  See all articles in the same topic Create my own version

Big O notation ( $O (\cdot)$ )

Failure of unrestricted Big O composition

Finite-prefix extension of a big O bound ( $f = O (g), g (n) \neq = 0 ⟹ sup_{n} ∣ f (n) / g (n) ∣ < \infty$ )

Big omega notation ( $f = Ω (g)$ )

Polynomial versus exponential growth ( $n^{k} = o (a^{n}) (a > 1)$ )

Little o notation ( $f = o (g)$ )

Big theta notation ( $f = Θ (g)$ )

Uniform big O bound ( $∣ f_{α} (n) ∣ \leq C ∣ g (n) ∣ with C, N independent of α$ )

 Ancestors (5)

 Incoming links (192)

 Discussion (0) New discussion

 Articles by others on the same topic (2)

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion