## Orders of magnitude

Let , et be functions from to
• We say that is in the ORDER OF MAGNITUDE of and we write if there exist two (strictly) positive constants and such that for big enough we have

 (2)

• We say that is an ASYMPTOTIC UPPER BOUND of and we write if there exists a (strictly) positive constants such that for big enough we have

 (3)

• We say that is an ASYMPTOTIC LOWER BOUND of and we write if there exists a (strictly) positive constants such that for big enough we have

 (4)

Let us give some examples.
• With and we have Indeed we have

 (5)

for with and .
• Assume that there exists a positive integer such that and for every . Then we have

 (6)

Indeed we have

 (7)

• Assume and are positive real constants. Then we have

 (8)

Indeed for we have

 (9)

Hence we can choose and .
We have the following properties.
• holds iff and hold together.
• Each of the predicates , and define a reflexive and transitive binary relation among the -to- functions. Moreover is symmetric.
• We have the following TRANSPOSITION FORMULA

 (10)

In practice is replaced by in each of the expressions , and . Hence, the following

 (11)

means

 (12)

Let us give another fundamental example. Let be a (univariate) polynomial with degree . Let be its leading coefficient and assume . Then we have
if then ,
if then ,
if then .
Exercise: Prove the following

 (13)

Marc Moreno Maza
2008-01-07