# Big Omicron and big Omega and big Theta

@article{Knuth1976BigOA, title={Big Omicron and big Omega and big Theta}, author={Donald Ervin Knuth}, journal={SIGACT News}, year={1976}, volume={8}, pages={18-24} }

Most of us have gotten accustomed to the idea of using the notation O(f(n)) to stand for any function whose magnitude is upper-bounded by a constant times f(n) , for all large n. Sometimes we also need a corresponding notation for lower-bounded functions, i.e., those functions which are at least as large as a constant times f(n) for all large n. Unfortunately~ people have occasionally been using the O-notation for lower bounds, for example when they reject a particular sorting method "because… Expand

#### Topics from this paper

#### 582 Citations

What does O(n) mean

- Computer Science, Mathematics
- SIGA
- 1986

The traditional notation is defended here, despite the fact that the new notation calls for extending arithmetic operations from functions to sets of functions, and gives rise, as Gilles Brassard honestly and immediately acknowledges, to a new type of ambiguous expressions. Expand

Topics of Mathematics in Cryptology Asymptotic Notation

- 2012

And now you ask: What is the running time of the main program in terms of n? Given the above, this is difficult to answer. f(a) makes a2 multiplications. How much time does a multiplication take?… 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

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

Series misdemeanors

- Philosophy, Computer Science
- ACCA
- 2013

Issues such as avoiding unnecessary restrictions such as prohibiting negative or fractional requested orders, the pros and cons of displaying results with explicit infectious error terms, efficient data structures, and algorithms that efficiently give users exactly the order or number of nonzero terms they request are discussed. Expand

Foreword This chapter is based on lecture notes from coding theory courses taught by Venkatesan

- 2018

1. Asymptotics of codes: Given > 0 express the rate of the best family of binary codes of relative distance 1 2 − , you can (a) construct, and (b) show the existence of. Express the rate in big-Oh… Expand

Teaching Algorithms and Data Structures: 10 Personal Observations

- Computer Science
- Computer Science in Perspective
- 2003

The elementary textbooks on algorithms and data structures have become too canonical too quickly, and that certain ways of presentation and also of selecting the contents are not as justified as they seem to be. Expand

Remarks on Abstracto

- Philosophy, Computer Science
- 1978

High-level programming languages have had a direct influence on the presentation of algorithms in the literature and many an author now employs a kind of pidgin ALGOL to express himself. Expand

A LGORITHMS FOR C OMPUTING THE M YERSON V ALUE BY D IVIDENDS

- 2007

The goal of this chapter is to compute the Myerson value of cooperative games restricted by a combinatorial structure. There have been previous models developed to study the problem of games with… Expand

What algorithms could not be

- Computer Science
- 2007

This dissertation addresses a variety of foundational issues pertaining to the notion of algorithm employed in mathematics and computer science and suggests that the technical crux of algorithmic realism lies in the necessity of reducing recursive specifications of algorithms to iterative models of computation in a manner which preserves algorithmic identity. Expand

#### References

SHOWING 1-10 OF 13 REFERENCES

Some problems of diophantine approximation

- Mathematics
- 1914

Let 0 be an irrational number, and a any number between 0 and 1 (0 included). Then it is well known that it is possible to find a sequence of positive integers w<i, n2, n3, ... such that (nr0) —>a as… Expand

An Algorithm for the Computation of Linear Forms

- Mathematics, Computer Science
- SIAM J. Comput.
- 1974

An algorithm is presented here which implies that every polynomial of degree n with at most s distinct coefficients can be realized with O(n/\log _s n) operations. Expand

II May

- II May
- 1976

IIardy, "Orders of Infinity,

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

Contributions to the theory of the riemann zeta-function and the theory of the distribution of primes

- Mathematics
- 1916

Handbuch der Lehre yon der Verteilung der Primzahlen, 2 vols. (Leipzig: B. G. Teubner

- Handbuch der Lehre yon der Verteilung der Primzahlen, 2 vols. (Leipzig: B. G. Teubner
- 1909

Leipzig: B. G. Teubner

- Leipzig: B. G. Teubner
- 1894