1.2 Infinitesimal asymptotics

Big O can also be used to describe the error term in an approximation to a mathematical function. For example,

expresses the fact that the error is smaller in absolute value than some constant times x³ if x is close enough to 0.

2 Formal definition

Suppose f(x) and g(x) are two functions defined on some subset of the real numbers. We say

f(x) is O(g(x)) as x → ∞

if and only if

there exist numbers x₀ and M such that |f(x)| ≤ M |g(x)| for x > x₀.

The notation can also be used to describe the behavior of f near some real number a: we say

f(x) is O(g(x)) as x → a

if and only if

there exists numbers δ>0 and M such that |f(x)| ≤ M |g(x)| for |x - a| < δ.

If g(x) is non-zero for values of x sufficiently close to a, both of these definitions can be unified using the limit superior:

f(x) is O(g(x)) as x → a

if and only if

In mathematics, both asymptotic behaviors near ∞ and near a are considered. In computational complexity theory, only asymptotics near ∞ are used; furthermore, only positive functions are considered, so the absolute value bars may be left out.

3 Example

Take the polynomials:

We say f(x) has order O(g(x)) or O(x⁴). From the definition of order, |f(x)| ≤ C |g(x)| for all x>1, where C is a constant.

Proof:

        where x > 1

    because x³ < x⁴, and so on.

4 Matters of notation

The statement "f(x) is O(g(x))" as defined above is often written as f(x) = O(g(x)). This is a slight abuse of notation: we are not really asserting the equality of two functions. Here is a bad example:

By this reason, some authors prefer a set notation and write f O(g), thinking of O(g) as the set of all functions dominated by g.

Furthermore, an "equation" of the form

f(x) = h(x) + O(g(x))

is to be understood as "the difference of f(x) and h(x) is O(g(x))".

5 Common orders of functions

Here is a list of classes of functions that are commonly encountered when analyzing algorithms. All of these are as n increases to infinity. The slower-growing functions are listed first. c is an arbitrary constant.

notation	name
O(1)	constant
O(log n)	logarithmic
O([log n]c)	polylogarithmic
O(n)	linear
O(n · log n)	sometimes called " linearithmic" or "supralinear"
O(n2)	quadratic
O(nc)	polynomial, sometimes " geometric"
O(cn)	exponential
O(n!)	factorial

6 Properties

If a function f(n) can be written as a finite sum of other functions, then the fastest growing one determines the order of f(n). For example

.

In particular, if a function may be bounded by a polynomial in n, then as n tends to infinity, one may disregard lower-order terms of the polynomial.

O(n^c) and O(cⁿ) are very different. The latter grows much, much faster, no matter how big the constant c is (so long as it is greater than one). A function that grows faster than any power of n is called superpolynomial. One that grows slower than an exponential function of the form cⁿ is called subexponential. An algorithm can require time that is both superpolynomial and subexponential; examples of this include the fastest algorithms known for integer factorization.

O(log n) is exactly the same as O(log(n^c)). The logarithms differ only by a constant factor, (since log(n^c)=c log n) and thus the big O notation ignores that. Similarly, logs with different constant bases are equivalent.

7 Related asymptotic notations: O, o, Ω, ω, Θ, Õ

Big O is the most commonly used asymptotic notation for comparing functions. We will define some others briefly in terms of "big O":

Notation	Definition
f(n) = O(g(n))	asymptotic upper bound
f(n) = o(g(n))	asymptotically negligible (M can be taken arbitrarily small)
f(n) = Ω(g(n))	asymptotic lower bound ( iff g(n) = O(f(n)))
f(n) = ω(g(n))	asymptotically dominant ( iff g(n) = o(f(n)))
f(n) = Θ(g(n))	asymptotically tight bound ( iff both f(n) = O(g(n)) and g(n) = O(f(n)))

Here is a hint (and mnemonics) why Landau selected these Greek letters: "omicron" is "o-micron", i.e., "o-small", whereas "omega" is "o-BIG".

The relation f(n) = o(g(n)) is read as "f(n) is little-oh of g(n)". Intuitively, it means that g(n) grows much faster than f(n). Formally, it states that the limit of f(n)/g(n) is zero.

The notations Θ and Ω are often used in computer science; the lower-case o is common in mathematics but rare in computer science. The lower-case ω is rarely used.

In casual use, O is commonly used where Θ is meant, i.e., a tight estimate is implied. For example, one might say " heapsort is O(n log n) in average case" when the intended meaning was " heapsort is Θ(n log n) in average case". Both statements are true, but the latter is a stronger claim.

Another notation sometimes used in computer science is Õ (read Soft-O). f(n) = Õ(g(n)) is shorthand for f(n) = O(g(n) log^kg(n)) for some k. Essentially, it is Big-O, ignoring logarithmic factors. This notation is often used to describe a class of "nitpicking" estimates (since log^kn is always o(n) for any constant k).

8 Multiple variables

Big O (and little o, and Ω...) can also be used with multiple variables. For example, the statement

asserts that there exist constants C and N such that

To avoid ambiguity, the running variable should always be specified: the statements

is quite different from

9 External links

• Cprogramming.com: Algorithm Efficiency An article on the Big O in C

Mathematical notation

<Hide>