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:
“On every formal visit a child ought to be of the party, by way of provision for discourse.”
—Jane Austen (1775–1817)
“... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
—Adrienne Rich (b. 1929)