Namespaces
Variants
Actions

Difference between revisions of "Order relation"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
''comparison of functions, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o0700603.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o0700604.png" /> relations, asymptotic relations''
+
<!--
 +
o0700603.png
 +
$#A+1 = 94 n = 0
 +
$#C+1 = 94 : ~/encyclopedia/old_files/data/O070/O.0700060 Order relation,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
 +
''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).
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o0700605.png" /> be a [[Limit point of a set|limit point of a set]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o0700606.png" />. If for two functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o0700607.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o0700608.png" /> there exist constants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o0700609.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006010.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006011.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006013.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006014.png" /> is called a function which is bounded in comparison with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006015.png" /> in some deleted neighbourhood of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006016.png" />, and this is written as
+
Let $  x _ {0} $
 +
be a [[Limit point of a set|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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006017.png" /></td> </tr></table>
+
$$
 +
f (x)  = O ( g (x) ) \  \textrm{ as }  x \rightarrow x _ {0}  $$
  
(read  "f is of the order of g" ); <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006018.png" /> means that the considered property holds only in some deleted neighbourhood of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006019.png" />. This definition can be naturally used when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006021.png" />.
+
(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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006022.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006023.png" /> are such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006024.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006025.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006026.png" />, then they are called functions of the same order as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006027.png" />. For instance, if two functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006028.png" /> are such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006029.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006030.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006031.png" /> and if the limit
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006032.png" /></td> </tr></table>
+
$$
 +
\lim\limits _ {x \rightarrow x _ {0} } \
  
exists, then they are of the same order as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006033.png" />.
+
\frac{\alpha (x) }{\beta (x) }
 +
  = c  \neq  0
 +
$$
  
Two functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006034.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006035.png" /> are called equivalent (asymptotically equal) as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006036.png" /> (written as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006037.png" />) if in some neighbourhood of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006038.png" />, except maybe the point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006039.png" /> itself, a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006040.png" /> is defined such that
+
exists, then they are of the same order as  $  x \rightarrow x _ {0} $.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006041.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
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
  
The condition of equivalency of two functions is symmetric, i.e. if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006042.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006043.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006044.png" />, and transitive, i.e. if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006045.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006046.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006047.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006048.png" />. If in some neighbourhood of the point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006049.png" /> the inequalities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006050.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006051.png" /> hold for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006052.png" />, then (*) is equivalent to any of the following conditions:
+
$$ \tag{* }
 +
= \phi g \  \textrm{ and } \  \lim\limits _ {x \rightarrow x _ {0}  }  \phi (x)  = 1 .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006053.png" /></td> </tr></table>
+
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:
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006054.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006055.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006056.png" /> is said to be an infinitely-small function with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006057.png" />, and one writes
+
$$
 +
\lim\limits _ {x \rightarrow x _ {0} } \
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006058.png" /></td> </tr></table>
+
\frac{f (x) }{g (x) }
 +
  = 1 ,\ \
 +
\lim\limits _ {x \rightarrow x _ {0} } 
 +
\frac{g (x) }{f (x) }
 +
  = 1 .
 +
$$
  
(read "a is of lower order than f" ). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006059.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006060.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006061.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006062.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006063.png" /> is an infinitely-small function for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006064.png" />, one says that the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006065.png" /> is an infinitely-small function of higher order than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006066.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006067.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006068.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006069.png" /> are quantities of the same order, then one says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006070.png" /> is a quantity of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006072.png" /> with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006073.png" />. All formulas of the above type are called asymptotic estimates; they are especially interesting for infinitely-small and infinitely-large functions.
+
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
  
Examples: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006074.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006075.png" />); <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006076.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006077.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006078.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006079.png" /> any positive numbers); <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006080.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006081.png" />).
+
$$
 +
\alpha  = o () \  \textrm{ as }  x \rightarrow x _ {0}  $$
  
Here are some properties of the symbols <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006082.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006083.png" />:
+
(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.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006084.png" /></td> </tr></table>
+
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 $).
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006085.png" /></td> </tr></table>
+
Here are some properties of the symbols  $  o $
 +
and  $  O $:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006086.png" /></td> </tr></table>
+
$$
 +
O ( \alpha f  )  = O (f) \  ( \alpha  \textrm{ a  non\AAhzero  constant  } );
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006087.png" /></td> </tr></table>
+
$$
 +
O ( O (f  ) )  = O (f  ) ;
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006088.png" /></td> </tr></table>
+
$$
 +
O (f  ) O (g)  = O ( f \cdot g ) ;
 +
$$
  
if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006089.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006090.png" />, then
+
$$
 +
O ( o (f  ) )  = o ( O (f  ) )  = o (f  ) ;
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006091.png" /></td> </tr></table>
+
$$
 +
O (f  ) o (g)  = o ( f \cdot g ) ;
 +
$$
  
Formulas containing the symbols <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006092.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006093.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006094.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006095.png" /> 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.
+
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.
  
 
====Comments====
 
====Comments====
The symbols <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o07006098.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070060/o070060101.png" /> ( "little oh symbollittle oh"  and  "big Oh symbolbig Oh" ) were introduced by E. Landau.
+
The symbols o $
 +
and $  O $(  
 +
"little oh symbollittle oh"  and  "big Oh symbolbig Oh" ) were introduced by E. Landau.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G.H. Hardy,  "A course of pure mathematics" , Cambridge Univ. Press  (1975)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  E. Landau,  "Grundlagen der Analysis" , Akad. Verlagsgesellschaft  (1930)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G.H. Hardy,  "A course of pure mathematics" , Cambridge Univ. Press  (1975)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  E. Landau,  "Grundlagen der Analysis" , Akad. Verlagsgesellschaft  (1930)</TD></TR></table>

Revision as of 16:40, 31 March 2020


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.

Comments

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

References

[a1] G.H. Hardy, "A course of pure mathematics" , Cambridge Univ. Press (1975)
[a2] E. Landau, "Grundlagen der Analysis" , Akad. Verlagsgesellschaft (1930)
How to Cite This Entry:
Order relation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Order_relation&oldid=16014
This article was adapted from an original article by M.I. Shabunin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article