Big O notation
Landau symbols are used in mathematics and computer science to describe the asymptotic behavior of functions and consequences. In computer science, it is used in the analysis of algorithms, and provide a measure of the number of elementary steps in response to the magnitude of the input variable. Complexity theory they used to compare different problems according to how they are " difficult" or costly to solve. It is said that "serious problems " grow exponentially with the instance or faster and for " a little trouble " exists an algorithm whose running time increases can be limited by the growth of a polynomial. They are called (not ) polynomially solvable.
- 6.1 Symbolic equal sign
- 6.2 Forgotten limit
History of the O symbol
The capital letter (then actually a great Omikron ) as a symbol of order was first used Analytic number theory in 1894 published the second edition of his book by the German number theorist Paul Bachmann. This notation was made famous by the also German number theorist Edmund Landau, with whose name it is today particularly implicated in the German language area.
Special case: Omega symbol
Two incompatible definitions
There are two very common in mathematics and inconsistent definitions of
Being a real number, or is where the real functions and in an environment of defined and in this environment is positive.
The former is used in analytic number theory and the other in complexity theory. This situation can cause confusion.
The Hardy - Littlewoodsche definition
In 1914, GH Hardy and JE Littlewood led the symbol with the meaning
One. So is the negation of.
In 1918, the same authors conducted two new symbols and the meanings
One. So is the negation of the negation and of.
In contrast to a later statement by DE Knuth used Edmund Landau these three symbols in 1924 with the same meanings.
This Hardy - Littlewood - symbols are prototypes, they are never used as is. has become and.
These three symbols, and (this means that the two properties and met) are still used systematically in analytical number theory.
Simple examples
We have
And especially
We have
And especially
But
Number theoretic notation
The strict notation is never used in the theory of numbers and to write less strict always. This means " f is an omega of g " and not " f is an omega G ".
The Knuthsche definition
In 1976 published D. E. Knuth an article whose main objective is to justify a use of the symbol. He tries to convince his readers that the Hardy - Littlewoodsche definition is almost never used (even in 1976 it was wrong for at least 25 years). He also claims Landau 've never used (which is also wrong), and that this was confirmed by his former student George Pólya (which seems impossible). Knuth writes: " For all the applications I have seen so far in computer science, a stronger requirement [ ... ] is much more appropriate". There is no doubt that he is right when he used the symbol to describe this stronger requirement: "Unfortunately, Hardy and Littlewood did not define as I wanted to ."
Under the risk of misunderstanding and confusion it also defines
Definition
In the following table, respectively, and either
- Sequences of real numbers, then, and the limit, or
- Real-valued functions of real numbers, then, and the limit of the extended real numbers: , or
- Real-valued functions of arbitrary topological spaces, then and also the limit. The most important special case is.
Formally, the Landau symbols can then define the following means inferior limit superior and limit:
In practice, usually there are limits, so that the estimation of the limes superior can often be replaced by the ( simpler ) calculation of a threshold.
Equivalent to the definition with limes symbols can be used with quantifiers for a metric space, ie in particular for the cases and the following definitions:
Analogous definitions can also be the case as well as for one-sided limits.
Conclusion
For any function f be
Each described sets of functions. There are the following relationships between them:
Examples and notation
When using the Landau - symbols used in the function is often provided shortened. Instead, for example,
One often writes shortening
This is handled in the following examples so.
The base of the logarithm does not matter.
Mergesort, heapsort
Selection sort
The Landau - notation is used to describe the asymptotic behavior when approaching a finite or infinite limit. The Big O is used to specify a maximum size. So true, for example, by the Stirling formula for the asymptotic behavior of the Faculty
And
Of the factor is only a constant and can be ignored for the estimation of the magnitude.
The Landau notation can also be used to describe the error term of an approximation. For example, states
That the absolute value of the approximation error is smaller than a constant time, for sufficiently close to zero.
The small o is used to say that an expression is negligible compared with the specified expression. For differentiable functions, for example,
The error in approximation by the tangent is therefore faster than linearly to 0
Notation traps
Symbolic equal sign
It is often used in mathematics at the Landau notation, the equal sign. However, it involves a purely symbolic notation and not a statement of equality, to the example, the laws of transitivity or symmetry would be applicable: In a statement, as is any side of the " equation " by the other determined. And does not follow that and are the same. Nor can then conclude that the same class or the one in the other is included.
In fact, it is in a quantity which contains all those functions which grow at most as fast as. The notation would be formally correct.
The notation with the equal sign as is used extensively in practice. For example, to say that there are constants and the expression so that
For sufficiently large applies.
Forgotten limit
Another case is that is often not specified, limit value to which refers the Landau symbol. The limit is considerably; For example, for, but not for the one-sided limit. Normally the considered limit but from the context it is clear, so here ambiguities occur rarely.
Application in complexity theory
In complexity theory, the Landau symbols are used mainly to describe the ( minimum, medium or maximum ) time or space requirements of an algorithm. One then speaks of time complexity and space complexity. The complexity may depend on the machine model used. In general, however, take a "normal" in the model, for example, an equivalent of the Turing machine.
It is often very costly or even impossible to specify a function for a problem that maps generally any input for a problem the corresponding number of computational steps ( or memory cells). Therefore, we are satisfied in general with it, instead of each input to detect individually, to restrict only to the input length. However, it is usually complicated to also provide a function.
Therefore, we developed the Landau notation, which is limited to the asymptotic behavior of the function. So you considered, in which barriers of computational effort ( the demand for memory and CPU time ) holds, if one enlarges the input. The most important Landau symbol ( capital Latin letter " O"), with which you can specify upper bounds; lower bounds are generally much more difficult to find. In this case ( often ) that there is a constant and a, such that for all. In other words, for all of the input lengths, the computational effort is not substantially greater - i.e., at most a constant factor - as.
The function is not always known; as function, however, a function is usually chosen so that its growth is well known (such as or ). The Landau notation is just there to estimate the computational effort ( space ) if it is too difficult to specify the exact function, or if it is too complicated.
The Landau symbols allow thus to summarize problems and algorithms according to their complexity in complexity classes.
In complexity theory, the various problems and algorithms can then compare as follows: One can for example specify the asymptotic running time for problems with a lower bound for, in accordance with an upper bound. In the form of ( for example ) will be referred to as the complexity class or Aufwandsmaß (thus, for example, square).
Constant factors In this notation, as the definitions of the Landau symbols show neglected. This is justified because the constants in large part on the used machine model or in case of implemented algorithms on the quality of the compiler and various properties of the hardware of the computer running are dependent. Thus, their validity on the complexity of the algorithm is very limited.
See also: Limit ( Limes )