# Big omega versus the wild functions

@article{Vitnyi1985BigOV, title={Big omega versus the wild functions}, author={Paul M. B. Vit{\'a}nyi and Lambert Meertens}, journal={SIGACT News}, year={1985}, volume={16}, pages={56-59} }

The question of the desirable properties and proper definitions of the Order-of-Magnitude symbols, in particular O and Ø, is addressed once more. The definitions proposed are chosen for complementary mathematical properties, rather than for similarity of form.

#### Topics from this paper

#### 7 Citations

A General Definition of the O-notation for Algorithm Analysis

- Mathematics, Computer Science
- Bull. EATCS
- 2015

It is proved that the primitive properties are equivalent to the definition of the O-notation as linear dominance, and it is defined as a general tool for manipulating theO-notation, and shown that Master theorems hold under linear dominance. Expand

Crusade for a better notation

- Computer Science
- SIGA
- 1985

In a well-known SIGACT/NEWS paper, Knuth sets forth the asymptotic notation by which the authors all now live and proposes that members of SIGACT adopt the O, Ω and Θ notations unless a better alternative can be found reasonably soon. Expand

O-notation in algorithm analysis

- Mathematics
- 2013

We provide an extensive list of desirable properties for an O-notation --- as used in algorithm analysis --- and reduce them to 8 primitive properties. We prove that the primitive properties are… Expand

Nonuniform Complexity Classes Specified by Lower and Upper Bounds

- Mathematics, Computer Science
- RAIRO Theor. Informatics Appl.
- 1989

The methods are used to characterize in terms of oracle Turing machines the classes defined by exponential lower bounds on some nonuniform complexity measures, obtaining an unified approach to deal with upper and lower bounds. Expand

Two decades of applied Kolmogorov complexity: in memoriam Andrei Nikolaevich Kolmogorov 1903-87

- Mathematics, Computer Science
- [1988] Proceedings. Structure in Complexity Theory Third Annual Conference
- 1988

The authors provide an introduction to the main ideas of Kolmogorov complexity and survey the wealth of useful applications of this notion. It is based on a theory of information content of strings,… Expand

Kolmogorov Complexity and its Applications

- Computer Science, Mathematics
- Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity
- 1990

Kolmogorov complexity has its roots in probability theory, combinatorics, and philosophical notions of randomness, and came to fruition using the recent development of the theory of algorithms. Expand

#### References

SHOWING 1-8 OF 8 REFERENCES

Big Omicron and big Omega and big Theta

- Computer Science
- SIGA
- 1976

I have recently asked several prominent mathematicians if they knew what ~(n 2) meant, and more than half of them had never seen the notation before, so I decided to search more carefully, and to study the history of O-notation and o-notation as well. Expand

A COMM in Modem Analysk University Press, Cambridge, England, 1902

- (Fourth revised edition,
- 1927

Orekrs if Non* (The Afinitircalailt of Paid Du BoiF-Reyntund)

- Cambridge Tnters in Math. and Math. Physics,
- 1924

Oscillating Dirieblet's integrals (An essay in the Infmitiirea/eill' of Paul Du BoisReymortd), QuarterOjegeraat •eMetakematies

- 1912

Orekrs if Non* (The Afinitircalailt of Paid Du BoiF-Reyntund). Cambridge Tnters in Math. and Math

- Physics
- 1879

Sur la grandeur relative des infmis des foncdons, Ann d i itlat

- Para ed Applic. Ser
- 1871

Some problems of Diophandoe approximation

Sur la grandeur relative des infmis des foncdons , Ann di itlat

- Para ed Applic . Ser .