Crusade for a better notation

ABSTRACT

In a well-known SIGACT/NEWS paper, Knuth sets forth the asymptotic notation by which we all now live [K76]. He closes his discussion with: "I propose that members of SIGACT (...) adopt the O, Ω and Θ notations as defined above, unless a better alternative can be found reasonably soon". Although one can hardly consider nearly a full decade later as being "reasonably soon", I would like to share with you my thoughts on the subject.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 3: Sara Baase, Computer Algorithms: Introduction to Design and Analysis, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 4: [Bl69] Blanchard, A., Initiation à to théorie analytique des nombres premiers, Dunod, Reading: Paris, 1969.
• 5: Gilles Brassard , Paul Bratley, Algorithmics: theory & practice, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: [HL14] Hardy, G. H. and J. E. Littlewood, "Some problems of Diophantine approximation", Acta Mathematics, Vol. 37, 1914, pp. 155-238.
• 8: [HS78] Horowitz, E. and S. Sahni, Fundamentals of Computer Algorithms, Computer Science Press, Reading: MD, 1978.
• 9: [K68] Knuth, D. E., The Art of Computer Programming, Vol. 1: Fundamental Algorithms, first edition, Addison-Wesley, Reading: MA, 1968.
• 10: [K73] Knuth, D. E., The Art of Computer Programming, Vol. 1: Fundamental Algorithms, second edition, Addison-Wesley, Reading: MA, 1973.
• 11: Donald E. Knuth, Big Omicron and big Omega and big Theta, ACM SIGACT News, v.8 n.2, p.18-24, April-June 1976 [doi>10.1145/1008328.1008329]
• 12: [L85] Leichter, J., private electronic communication.
• 13: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 14: [P85] Pstashnik, O., private electronic communication.
• 15: Paul Walton Purdom, Jr. , Cynthia A. Brown, The analysis of algorithms, Holt, Rinehart & Winston, Austin, TX, 1985
• 16: [S74] Seiferas, J. I., Nondeterministic Time and Space Complexity Classes, Department of Electrical Engineering and Computer Science, MIT, 1974.
• 17: Joel I. Seiferas , Michael J. Fischer , Albert R. Meyer, Separating Nondeterministic Time Complexity Classes, Journal of the ACM (JACM), v.25 n.1, p.146-167, Jan. 1978 [doi>10.1145/322047.322061]
• 18: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 19: [vEB85] van Emde Boas, P., private electronic communication.
• 20: Paul M. B. Vitányi , Lambert Meertens, Big omega versus the wild functions, ACM SIGACT News, v.16 n.4, p.56-59, April 1985 [doi>10.1145/382242.382835]