Main Index
Mathematical Analysis
Inequalities
Subject Index
comment on the page
The Bachmann-Landau notation and its derivatives is used to describe the infinite or infinitesimal asymptotic behavior of functions in a neighborhood in terms of other functions.
Let and
an accumulation point
of
. Let
be a complex-valued function and
a positive function for all
.
The relation as
implies that
remains bounded as
.
Examples: For we have
,
,
, or
, but for
we have
,
, and
.
The definitions can be extended to multiple variables in an obvious way, for instance . Thus
for
.
Relations ,
are “one way” symbols, they cannot be read “from the right to the left”. For instance,
and
as
, but the equality
is not true. We also have:
For instance, if are continuous and
for
then
, or if
and
, then
as
.
If and
are differentiable then
does not imply that
, but [1] , p.297: If
and
,
, then
. If moreover, either
or
, then
.
Remember that the implication
is not true in general. For example, but
while
. Similarly
does not imply that
.
When the involved depends on a parameter
then we write
.
The symbols O(·) and o(·) are often attributed to E. Landau. This is only partially correct. The notation was introduced by German number theoretist P. Bachmann [2] , p. 401, and stood as an abbreviation for the order of and was written as a capital omicron. The notation
was introduced by E.Landau [3], p.883 who earlier denoted this relation by {·}.
Instead of also I.M.Vinogradov’s “less less” notation
is used. In this case
has the same meaning as
. [4]
There are some related symbols also in use:
If for two arbitrary functions defined over
we have
, i.e.
which is equivalent to
then the two functions are said to be asymptotically equal, and we write
as
and
.
Recently the following notation is used in combinatorics and theoretical computer science : ,
, meaning that there is a positive constant
such that
for all sufficiently large
.
[1] | Jarník, V. (1956). Differential Calculus II (Czech). Prague: Publishing House of the Czechoslovak Academy of Sciences. |
[2] | Bachmann, P.G.H. G. (1894). Zahlentheorie, Bd. 2: Die Analytische Zahlentheorie. Leipzig: B.G.Teubner. |
[3] | Landau, E. (1909). Handbuch der Lehre von der Verteilung der Primzahlen. Leipzig: B.G.Teubner. |
[4] | Knuth, D. E. (1976). Big Omicron and big Omega and big Theta. ACM SIGACT News, 8(2), 18 -24. |
Cite this web-page as:
Štefan Porubský: Bachmann-Landau Asymptotic Notation.