Information Technology Reference
In-Depth Information
therefore
n
a
n
=
a
0
(
1
+
1
/
n
)
.
n
<
(
+
/
)
<
It can be shown that, for any
n
,2
1
1
n
3 and, for increasing values of
n
,
n
approaches the limit value
e
(
+
/
)
=
,
...
the value
.
In conclusion, the hypothesis of infinitesimally distributed increment (in time and
in quantity) implies that after a unitary time, an initial quantity
a
0
become
ea
0
,and
the growth law, along time
t
,is
a
0
e
t
.
1
1
n
2
71828
5.6.6
Asymptotic Orders and Infinitesimals
Growth processes can be compared according to their speeds. An exponential
growth with base greater than 1 seems to be faster than a quadratic growth law.
This is not completely right, because comparing 100
t
2
with 2
t
2 yields the
values 400 and 4 respectively, although the first expression is quadratic and the sec-
ond one is exponential. However, for all the values
t
for
t
=
15 the exponential function
overtakes the quadratic one by a gap increasing with the value of
t
.Thismeansthat
a comparison of growths is correct when it refers to the overall growth behavior,
possibly by forgetting a finite number of values. This intuition can be formalized by
the notion of
almost everywhere
comparison of positive non-decreasing functions.
A positive non-decreasing function
f
defined on the set
≥
N
is less than (or equal
to) a function
g
of the same type when, for some
n
0
∈
N
,
f
(
n
)
≤
g
(
n
)
for every value
n
>
n
0
. We write
f
(
n
)
≤
∞
g
(
n
)
to denote this fact.
O
(
g
)
denotes the class of positive non-decreasing functions
{
f
|
f
(
n
)
≤
∞
g
(
n
)
}
.
Often, with an abuse of notation,
f
∈
O
(
g
)
is indicated by writing
f
=
O
(
g
)
(by
saying that
f
is a O of
g
). Symmetrically,
Ω
(
g
)
denotes the class of functions
{
f
.
Any positive real number
|
g
(
n
)
≤
∞
f
(
n
)
}
ε
can be seen as a constant function yielding the value
ε
everywhere.
An
infinitesimal
is a function
f
defined on the set
and taking values in the set
of real numbers such that their absolute values (the function yielding the absolute
values of
f
N
(
n
)
) belong to
O
(
ε
)
for any
ε
>
0
∈
R
. The function
f
(
n
)
is an
infinite
if 1
/
f
(
n
)
is an infinitesimal. Two functions
f
(
n
)
,
g
(
n
)
are
asymptotically equiva-
lent
if 1
−
f
(
n
)
/
g
(
n
)
is an infinitesimal. The class of functions
f
(
n
)
such that, for
some positive constant
k
∈
R
,
k
=
0,
kf
(
n
)
and
g
(
n
)
are asymptotically equivalent
is denoted by
.
All the concepts of classical infinitesimal calculus can be developed in terms
of infinitesimals. For example, the classical condition defining the number
z
as the
limit of a real function
f
θ
(
g
)
(
x
)
,for
x
approaching a value
x
0
, usually denoted by the
following notation:
lim
x
f
(
x
)=
z
→
x
0
is equivalent to the requirement that:
f
(
x
0
+
1
/
n
)
−
z
