Big O Notation - Formal Definition

Formal Definition

Let f(x) and g(x) be two functions defined on some subset of the real numbers. One writes

if and only if there is a positive constant M such that for all sufficiently large values of x, f(x) is at most M multiplied by g(x) in absolute value. That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that

In many contexts, the assumption that we are interested in the growth rate as the variable x goes to infinity is left unstated, and one writes more simply that f(x) = O(g(x)). The notation can also be used to describe the behavior of f near some real number a (often, a = 0): we say

if and only if there exist positive numbers δ and M such that

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:

if and only if

Read more about this topic:  Big O Notation

Famous quotes containing the words formal and/or definition:

    “The bed is now as public as the dinner table and governed by the same rules of formal confrontation.”
    —Angela Carter (1940–1992)

    “It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
    —François, Duc De La Rochefoucauld (1613–1680)