Difference between revisions of "Order relation"

comparison of functions, $O$- $o$ relations, asymptotic relations

A notion arising in studies on the behaviour of a function with respect to another function in a neighbourhood of some point (this point may be infinite).

Let $x _ {0}$ be a limit point of a set $E$. If for two functions $f$ and $g$ there exist constants $c > 0$ and $\delta > 0$ such that $| f (x) | \leq c | g (x) |$ for $| x - x _ {0} | < \delta$, $x \neq x _ {0}$, then $f$ is called a function which is bounded in comparison with $g$ in some deleted neighbourhood of $x _ {0}$, and this is written as

$$f (x) = O ( g (x) ) \ \textrm{ as } x \rightarrow x _ {0}$$

(read "f is of the order of g" ); $x \rightarrow x _ {0}$ means that the considered property holds only in some deleted neighbourhood of $x _ {0}$. This definition can be naturally used when $x \rightarrow \infty$, $x \rightarrow - \infty$.

If two functions $f$ and $g$ are such that $f = O (g)$ and $g = O (f )$ as $x \rightarrow x _ {0}$, then they are called functions of the same order as $x \rightarrow x _ {0}$. For instance, if two functions $\alpha , \beta$ are such that $\alpha (x) \neq 0$, $\beta (x) \neq 0$ if $x \neq x _ {0}$ and if the limit

$$\lim\limits _ {x \rightarrow x _ {0} } \ \frac{\alpha (x) }{\beta (x) } = c \neq 0$$

exists, then they are of the same order as $x \rightarrow x _ {0}$.

Two functions $f$ and $g$ are called equivalent (asymptotically equal) as $x \rightarrow x _ {0}$( written as $f \sim g$) if in some neighbourhood of $x _ {0}$, except maybe the point $x _ {0}$ itself, a function $\phi$ is defined such that

$$\tag{* } f = \phi g \ \textrm{ and } \ \lim\limits _ {x \rightarrow x _ {0} } \phi (x) = 1 .$$

The condition of equivalency of two functions is symmetric, i.e. if $f \sim g$, then $g \sim f$ as $x \rightarrow x _ {0}$, and transitive, i.e. if $f \sim g$ and $g \sim h$, then $f \sim h$ as $x \rightarrow x _ {0}$. If in some neighbourhood of the point $x _ {0}$ the inequalities $f (x) \neq 0$, $g (x) \neq 0$ hold for $x \neq x _ {0}$, then (*) is equivalent to any of the following conditions:

$$\lim\limits _ {x \rightarrow x _ {0} } \ \frac{f (x) }{g (x) } = 1 ,\ \ \lim\limits _ {x \rightarrow x _ {0} } \frac{g (x) }{f (x) } = 1 .$$

If $\alpha = \epsilon f$ where $\lim\limits _ {x \rightarrow x _ {0} } \epsilon (x) = 0$, then $\alpha$ is said to be an infinitely-small function with respect to $f$, and one writes

$$\alpha = o (f ) \ \textrm{ as } x \rightarrow x _ {0}$$

(read "a is of lower order than f" ). If $f (x) \neq 0$ when $x \neq x _ {0}$, then $\alpha = o (f )$ if $\lim\limits _ {x \rightarrow x _ {0} } \alpha (x) / f(x) = 0$. If $f$ is an infinitely-small function for $x \rightarrow x _ {0}$, one says that the function $\alpha = o (f )$ is an infinitely-small function of higher order than $f$ as $x \rightarrow x _ {0}$. If $g$ and $[ f ] ^ {k}$ are quantities of the same order, then one says that $g$ is a quantity of order $k$ with respect to $f$. All formulas of the above type are called asymptotic estimates; they are especially interesting for infinitely-small and infinitely-large functions.

Examples: $e ^ {x} - 1 = o (1)$( $x \rightarrow 0$); $\cos x ^ {2} = O (1)$; $( \mathop{\rm ln} x ) ^ \alpha = o ( x ^ \beta )$( $x \rightarrow \infty$; $\alpha , \beta$ any positive numbers); $[ x / \sin ( 1 / x ) ] = O ( x ^ {2} )$( $x \rightarrow \infty$).

Here are some properties of the symbols $o$ and $O$:

$$O ( \alpha f ) = O (f) \ ( \alpha \textrm{ a non\AAhzero constant } );$$

$$O ( O (f ) ) = O (f ) ;$$

$$O (f ) O (g) = O ( f \cdot g ) ;$$

$$O ( o (f ) ) = o ( O (f ) ) = o (f ) ;$$

$$O (f ) o (g) = o ( f \cdot g ) ;$$

if $0 < x < x _ {0}$ and $f = O (g)$, then

$$\int\limits _ {x _ {0} } ^ { x } f (y) dy = O \left ( \int\limits _ {x _ {0} } ^ { x } | g (y) | dy \right ) \ \ ( x \rightarrow x _ {0} ) .$$

Formulas containing the symbols $o$ and $O$ are read only from the left to the right; however, this does not exclude that certain formulas remain true when read from the right to the left. The symbols $o$ and $O$ for functions of a complex variable and for functions of several variables are introduced in the same way as it was done above for functions of one real variable.

The symbols $o$ and $O$( "little oh symbollittle oh" and "big Oh symbolbig Oh" ) were introduced by E. Landau.