62
II - Convergence: Discrete variables
indefinitely or approaches indefinitely close to a limit value aj what then
matters is the ratio If(x)/g(x)l, which may, when x tends to infinity or to a,
either take values as large as one wants, or remain less than a fixed number,
or remain confined between two fixed strictly positive numbers, or approach 1
more and more closely, or approach 0 more and more closely, not to speak of
the cases where nothing of this kind happens.
These comparisons can be expressed with the aid of notation which we
shall use frequently later and that it is important not to confuse. There are
four cases to consider.
(i) The relation
I(x) = O(g(x)) when x ~ +00 (or when x ~ a),
with an upper case 0, means that there exists a number M > 0 independent
of x such that one has I/(x)1 ::; Mlg(x)1 for x large (or for x close to a) in
the sense we have given above to these expressions. The notation O(g(x))
is used to denote not only a particular function I, but also an arbitrary
function O(g(x)). Experience shows that the ambiguities thus introduced
have no unfortunate consequences if one keeps this convention in mind. For
example, the relations II = O(g) and h = O(g) do not imply 11 = h
despite what one might believe at first glance. Similarly, the obvious relation
O(g(x)) + O(g(x)) = O(g(x)) - obvious since if two functions are, for x large,
majorised by 5Ig(x)1 and 12Ig(x)1 respectively, then their sum is majorised by
17Ig(x)l- does not imply that O(g(x)) = o. We shall return to these points
in detail in Chap. VI.
For example
10 100 n 2 + 10100000n = 0(n 2 ) when n ~ +00
since for n 2': 1 (whence n ::; n 2 ), the left hand side is less than Mn 2 with
this number may appear "very large" to the puny members of the human
race, but it is independent of n and one does not demand more.
(ii) The relation
I(x) ~ g(x) when x ~ +00 (or when x ~ a)
means that there exist numbers m > 0 and M > 0 such that
mlg(x)1 ::; I/(x)1 ::; Mlg(x)1
for x large, or for x close to a. One says I and 9 are comparable or have
the same order 01 magnitude in these circumstances. This is equivalent to
requiring that I = O(g) and 9 = 0(/) simultaneously.
For example,
II - Convergence: Discrete variables
indefinitely or approaches indefinitely close to a limit value aj what then
matters is the ratio If(x)/g(x)l, which may, when x tends to infinity or to a,
either take values as large as one wants, or remain less than a fixed number,
or remain confined between two fixed strictly positive numbers, or approach 1
more and more closely, or approach 0 more and more closely, not to speak of
the cases where nothing of this kind happens.
These comparisons can be expressed with the aid of notation which we
shall use frequently later and that it is important not to confuse. There are
four cases to consider.
(i) The relation
I(x) = O(g(x)) when x ~ +00 (or when x ~ a),
with an upper case 0, means that there exists a number M > 0 independent
of x such that one has I/(x)1 ::; Mlg(x)1 for x large (or for x close to a) in
the sense we have given above to these expressions. The notation O(g(x))
is used to denote not only a particular function I, but also an arbitrary
function O(g(x)). Experience shows that the ambiguities thus introduced
have no unfortunate consequences if one keeps this convention in mind. For
example, the relations II = O(g) and h = O(g) do not imply 11 = h
despite what one might believe at first glance. Similarly, the obvious relation
O(g(x)) + O(g(x)) = O(g(x)) - obvious since if two functions are, for x large,
majorised by 5Ig(x)1 and 12Ig(x)1 respectively, then their sum is majorised by
17Ig(x)l- does not imply that O(g(x)) = o. We shall return to these points
in detail in Chap. VI.
For example
10 100 n 2 + 10100000n = 0(n 2 ) when n ~ +00
since for n 2': 1 (whence n ::; n 2 ), the left hand side is less than Mn 2 with
this number may appear "very large" to the puny members of the human
race, but it is independent of n and one does not demand more.
(ii) The relation
I(x) ~ g(x) when x ~ +00 (or when x ~ a)
means that there exist numbers m > 0 and M > 0 such that
mlg(x)1 ::; I/(x)1 ::; Mlg(x)1
for x large, or for x close to a. One says I and 9 are comparable or have
the same order 01 magnitude in these circumstances. This is equivalent to
requiring that I = O(g) and 9 = 0(/) simultaneously.
For example,