3

There was a question asking what the "O" stands for in "Big O", the answer to which seems to be "Ordnung von"/"order of".

I wonder what's the origin of the names "Omega" and "Theta" in the "Big Omega" and "Big Theta". Or are they somewhat randomly chosen without an inherent meaning.

3
  • 1
    Why the downvotes? Care to explain/leave a comment? Is this question considered off-topic? There is a literally an "etymology" tag on this SE and I don't like the idea of using the notations without understanding why they got their names. Certainly didn't see the question I linked to suffer the same fate.
    – xji
    Commented Dec 5, 2020 at 17:25
  • 1
    Also it's being voted as "opinion-based" but I don't see how clarifying the etymology of a widely used notation could be considered "opinion-based".
    – xji
    Commented Dec 5, 2020 at 17:53
  • 3
    On this site, it is quite normal that each question, regardless of being good or bad, gets at least one or two downvotes with no comment. I suspect some of the active community members to suffer from serious communication problems, maybe Asperger syndrome, since they seem to be totally immune to any request of behaving more constructive. So don't take these downvotes personal, your question is fine.
    – Doc Brown
    Commented Dec 5, 2020 at 21:01

1 Answer 1

13
  • O was introduced in Bachmann, Paul (1894). Analytische Zahlentheorie. Bachmann is using the term "Ordnung" (order of) multiple times to refer to the growth rate of functions, and introduces the symbol O, but there is no explanation given why O was chosen, and he never explicitly or implicitly draws a link between the term "Ordnung" and the symbol "O". It is also, I believe, not 100% clear whether that is meant to be a Latin O or a Greek Omicron.

  • o was introduced in Landau, Edmund (1909). Handbuch der Lehre von der Verteilung der Primzahlen. I didn't find the specific place where it is defined in the book, unfortunately.

  • Ω was introduced in Hardy, G. H.; Littlewood, J. E. (1914). Some problems of diophantine approximation: Part II. The trigonometrical series associated with the elliptic ϑ-functions. It is simply introduced without explanation for the letter chosen.

  • Ω was redefined in Knuth, Donald (April–June 1976). Big Omicron and big Omega and big Theta. Knuth thought the definition of Ω used by Hardy and Littlewood was inconvenient for Computer Science and that the symbol was not used much anyway (on this point he was wrong unfortunately, so that there are now two mutually incompatible definitions of this symbol), so he chose to redefine it. All he has to say about the choice of symbol is:

    I like the mnemonic appearance of Ω by analogy with Ο, and it is easy to typeset.

    By the way, note that Knuth refers to "Big Οmicron" in the title.

  • Θ was defined in Knuth, Donald (April–June 1976). Big Omicron and big Omega and big Theta. (The same article that redefined Ω.) All he has to say about the choice of symbol is:

    Furthermore, these two notations as defined above are nicely complemented by the Θ-notation which was suggested to me independently by Bob Tarjan and by Mike Paterson.

    However, it is not clear whether he is referring to the symbol or the definition. Since he does not cite any sources, we may assume this was not in a published paper but rather private communication. We may assume that Θ was chosen because it also kinda sorta looks like Ο, but there is nothing in the article to support that theory.

So, in short, other than Knuth's "Ω looks like Ο", we don't know for any of those symbols.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.