Landau symbols

from Wikipedia, the free encyclopedia

Landau symbols (also O notation , English big O notation ) are used in mathematics and computer science to describe the asymptotic behavior of functions and sequences . In computer science, they are used in the analysis of algorithms and provide a measure of the number of elementary steps or storage units depending on the size of the given problem. The complexity theory they used to problems to be classed as "difficult" or consuming to solve them. For “light” problems there is an algorithm whose running time can be limited by a polynomial ; Problems are considered "difficult" for which no algorithm has been found that grows less rapidly than exponentially . They are called (not) polynomially solvable.

notation Illustrative meaning

or

grows slower than

or

does not grow much faster than
grows as fast as
does not always grow slower than (number theory)
does not grow much slower than (complexity theory)
grows faster than

History of the O symbol

For the first time, the German number theorist Paul Bachmann expressed in 1894 "through the sign a quantity [...] whose order in relation to the order of does not exceed [...]." The also German number theorist Edmund Landau , through whom the and symbolism became known and with whose name it is associated today, especially in the German-speaking area, took over Bachmann's designation and also introduced the designation for "of small order".

Special case: Omega symbol

Two incompatible definitions

There are two very common and inconsistent definitions for in mathematics

where is a real number, or , where the real functions and are defined on a neighborhood of and is positive in this neighborhood.

The first is used in analytical number theory and the other in complexity theory . This situation can lead to confusion.

The Hardy-Littlewood definition

In 1914, Godfrey Harold Hardy and John Edensor Littlewood introduced the symbol with the meaning

a. So is the negation of .

In 1916 the same authors introduced two new symbols and with the meanings

;

a. So is the negation of and the negation of .

In contrast to a later statement by Donald Ervin Knuth , Landau used these three symbols in 1924 with the same meanings.

These Hardy-Littlewood symbols are prototypes, they are never used exactly. has become to and to .

These three symbols as well (this means that the two properties and are fulfilled) are still used systematically in analytic number theory today.

Simple examples

We have

and specially

We have

and specially

but

Number theoretic notation

The strict notation is never used in number theory and one always writes less strictly . This means here " is an omega of ".

Knuth's definition

In 1976, D. E. Knuth published an article whose main aim is to justify a different use of the symbol. He tries to convince his readers that, with the exception of some older works (such as the 1951 book by Edward C. Titchmarsh ), Hardy-Littlewood's definition is almost never used. He writes that it could not be used with Landau and that George Pólya , who studied with Landau, confirmed the assessment that Landau probably did not use the symbol (in fact, there is a use in a treatise from 1924). Knuth writes: “For all the applications I have seen so far in computer science, a stronger requirement […] is much more appropriate.” He uses the symbol to describe this stronger requirement: “Unfortunately, Hardy and Littlewood didn't define as I wanted to. "

At the risk of misunderstanding and confusion, he also defines

.

definition

In the following table denote and either

  • Sequences of real numbers, then and is the limit , or
  • real-valued functions of the real numbers, then and is the limit of the extended real numbers:, or
  • real-valued functions of arbitrary topological spaces , then and is also the limit . The most important special case is here .

The Landau symbols can then be formally defined using Limes superior and Limes inferior as follows:

notation definition Mathematical definition
asymptotically negligible compared to
asymptotic upper bound
(Number theory) asymptotic lower bound, is not in
(Complexity theory) asymptotic lower bound,
asymptotically sharp bound, both and
asymptotically dominant,

In practice, the limit values ​​usually exist , so that the estimation of the limes superior can often be replaced by the (simpler) calculation of a limit value.

Equivalent to the definition with limit symbols , the following definitions with quantifiers can be used for a metric space , in particular for the cases and :

notation
(Number theory)
(Complexity theory)
notation
(Number theory) (the test function g is always positive)
(Complexity theory)

Analogous definitions can also be given for the case and for one-sided limit values .

Inference

For each function are through

each set of functions is described. The following relationships apply between them:

Examples and notation

When using the Landau symbols, the function used is often given in abbreviated form. For example , instead of writing in abbreviated form, this is also used in the following examples.

The examples in the table all contain monotonically increasing comparison functions for which their behavior is important. (The name of the argument is often used - often without an explanation, because it is very often a number.) In this regard, they are in ascending order; H. the complexity classes are contained in those in the lines below.

notation meaning Clear explanation Examples of runtimes
is limited. does not exceed a constant value (regardless of the value of the argument ). Determining whether a binary number is even.
Look up the -th element in a field in a register machine
grows double logarithmically. Base 2 increases by 1 when squared. Interpolation search in the sorted field with uniformly distributed entries
grows logarithmically . grows roughly a constant amount when doubles. The base of the logarithm does not matter.
Binary search in the sorted field with entries
grows like the root function . grows roughly double when quadrupled. Number of divisions of the naive primality test (divide by any integer )
grows linearly . grows roughly double when doubled. Search in the unsorted field with entries (e.g. linear search )
has super-linear growth. Comparison-based algorithms for sorting numbers

Mergesort , Heapsort

grows square . grows roughly fourfold when doubled. Simple algorithms for sorting numbers

Selection location

grows polynomially. grows approximately times when doubled. "Simple" algorithms
grows exponentially . grows roughly double when increasing by 1. Satisfiability problem of propositional logic (SAT) using exhaustive search
grows factorially . grows roughly by times when it increases by 1. Salesman Problem (with exhaustive search)
grows like the modified Ackermann function . Problem is predictable , but not necessarily primitive-recursive

Landau notation is used to describe the asymptotic behavior when approaching a finite or infinite limit value. The large one is used to indicate a maximum magnitude. For example, the Stirling formula applies to the asymptotic behavior of the faculty

For

and

for .

The factor is only a constant and can be neglected for estimating the order of magnitude.

Landau notation can also be used to describe the error term of an approximation. For example, it says

for ,

that the absolute amount of the approximation error is smaller than a constant times for sufficiently close to zero.

The small is used to say that an expression is negligibly small compared to the specified expression. For example, the following applies to differentiable functions

for ,

the error in approximation by the tangent is therefore faster than linear .

Notation traps

Symbolic equal sign

The equals sign is often used in mathematics in Landau notation. However, it is a purely symbolic notation and not a statement of equality, to which, for example, the laws of transitivity or symmetry can be applied: A statement like is not an equation and neither side is determined by the other. From and it does not follow that and are equal. Nor can one conclude from and that and are the same class or that one is contained in the other.

In fact, it is a set that contains all those functions that grow at most as fast as . The spelling is therefore formally correct.

The notation with the equal sign as in is still used extensively in practice. For example, let the expression say that there are constants and such that

applies to sufficiently large .

Forgotten limit

Another trap is that it is often not specified which limit value the land cover symbol refers to. But the limit is essential; for example, for but not for the one-sided limit value . Normally, however, the considered limit value becomes clear from the context, so that ambiguities rarely occur here.

Application in complexity theory

The articles Landau symbols # application in complexity theory , complexity (computer science) and complexity theory overlap thematically. Help me to better differentiate or merge the articles (→  instructions ) . To do this, take part in the relevant redundancy discussion . Please remove this module only after the redundancy has been completely processed and do not forget to include the relevant entry on the redundancy discussion page{{ Done | 1 = ~~~~}}to mark. Accountalive 03:47, Jan. 1, 2010 (CET)


In complexity theory , the Landau symbols are mainly used to describe the (minimum, average or maximum) time or storage space requirements of an algorithm. One then speaks of time complexity or space complexity . The complexity can depend on the machine model used . As a rule, however, a “normal” model is assumed, for example one that is equivalent to the Turing machine .

It is often very time-consuming or completely impossible to specify a function for a problem which generally assigns the associated number of computing steps (or memory cells) to any input for a problem. Therefore, instead of capturing each input individually, you are usually content with only limiting yourself to the input length . However, it is usually too time-consuming to specify a function .

That is why the Landau notation was developed, which is limited to the asymptotic behavior of the function . So you consider the limits of the computational effort (the need for memory and computing time) when you enlarge the input. The most important Landau symbol is (large Latin letter "O"), with which one can indicate upper bounds ; lower bounds are generally much more difficult to find. Here is (often ) that a constant and exist, such that for all the following applies: . In other words: for all input lengths the computational effort is not significantly greater - i.e. H. at most by a constant factor - as .

The function is not always known; as a function , however, a function is usually chosen whose growth is well known (like or ). The Landau notation is there to estimate the computational effort (space requirement) when it is too time-consuming to specify the exact function or when it is too complicated.

The Landau symbols allow problems and algorithms to be grouped according to their complexity in complexity classes .

In complexity theory, the various problems and algorithms can then be compared as follows: For problems with, one can specify a lower bound for, for example, the asymptotic running time , with correspondingly an upper bound. At , the shape of (e.g. ) is also referred to as the complexity class or measure of effort (e.g., quadratic).

In this notation, as the definitions of the Landau symbols show, constant factors are neglected. This is justified because the constants largely depend on the machine model used or, in the case of implemented algorithms, on the quality of the compiler and various properties of the hardware of the executing computer . This means that their informative value about the complexity of the algorithm is very limited.

See also

Web links

Individual evidence

  1. page 401 f. of the second part published in 1894 The analytic number theory ( archive.org ) of his work number theory .
  2. page 31 and page 61 of the first volume of his work Handbuch der Doctrine of the Distribution of Prime Numbers ( archive.org ) , published in 1909 .
  3. ^ Earliest Uses of Symbols of Number Theory, September 22, 2006: ( Memento of October 19, 2007 in the Internet Archive ) According to Władysław Narkiewicz in The Development of Prime Number Theory: “The symbols O (·) and o (·) are usually called the Landau symbols. This name is only partially correct, since it seems that the first of them appeared first in the second volume of P. Bachmann's treatise on number theory (Bachmann, 1894). In any case Landau (1909a, p. 883) states that he had seen it for the first time in Bachmann's book. The symbol o (·) appears first in Landau (1909a). ”
  4. G. H. Hardy, J. E. Littlewood: Some problems of Diophantine approximation. Part II. The trigonometrical series associated with the elliptic functions. In: Acta Math. Volume 37, 1914, pp. 193-239, here p. 225, doi : 10.1007 / BF02401834 .
  5. G. H. Hardy, J. E. Littlewood: Contribution to the theory of the Riemann zeta-function and the theory of the distribution of primes. In: Acta Math. Volume 41, 1916, pp. 119-196, here p. 138, doi : 10.1007 / BF02422942 .
  6. ^ A b Donald E. Knuth: Big Omicron and big Omega and big Theta. In: SIGACT News , Apr. – June 1976, pp. 18–24 ( online [PDF; 348 kB]).
  7. a b Edmund Landau: About the number of grid points in certain areas. (Fourth treatise). In: News from the Society of Sciences in Göttingen. Mathematical-physical class. 1924, pp. 137-150; or "Collected Works" (PT Bateman et al.), Thales Verlag, Vol. 8, 1987, pp. 145-158; here p. 140 ( Göttingen Digitization Center ).
  8. ^ Edward C. Titchmarsh: The Theory of the Riemann Zeta Function. Clarendon Press, Oxford 1951.
  9. With the comment: “Although I have changed Hardy and Littlewood's definition of , I feel justified in doing so because their definition is by no mean in wide use, and because there are other ways to say what they want to say in the comparatively rare cases when their definition applies ”.