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:
“That anger can be expressed through words and non-destructive activities; that promises are intended to be kept; that cleanliness and good eating habits are aspects of self-esteem; that compassion is an attribute to be prized—all these lessons are ones children can learn far more readily through the living example of their parents than they ever can through formal instruction.”
—Fred Rogers (20th century)
“Scientific method is the way to truth, but it affords, even in
principle, no unique definition of truth. Any so-called pragmatic
definition of truth is doomed to failure equally.”
—Willard Van Orman Quine (b. 1908)