History (Bachmann–Landau, Hardy, and Vinogradov Notations)
The symbol O was first introduced by number theorist Paul Bachmann in 1894, in the second volume of his book Analytische Zahlentheorie ("analytic number theory"), the first volume of which (not yet containing big O notation) was published in 1892. The number theorist Edmund Landau adopted it, and was thus inspired to introduce in 1909 the notation o ; hence both are now called Landau symbols. The former was popularized in computer science by Donald Knuth, who re-introduced the related Omega and Theta notations. Knuth also noted that the Omega notation had been introduced by Hardy and Littlewood under a different meaning "≠o" (i.e. "is not an o of"), and proposed the above definition. Hardy and Littlewood's original definition (which was also used in one paper by Landau) is still used in number theory (where Knuth's definition is never used). In fact, Landau introduced in 1924, in the paper just mentioned, the symbols ("rechts") and ("links"), precursors for the modern symbols ("is not smaller than a small o of") and ("is not larger than a o of"). Thus the Omega symbols (with their original meanings) are sometimes also referred to as "Landau symbols". Also, Landau never used the Big Theta and small omega symbols.
Hardy's symbols were (in terms of the modern O notation)
- and
(Hardy however never defined or used the notation, nor, as it has been sometimes reported). It should also be noted that Hardy introduces the symbols and (as well as some other symbols) in his 1910 tract "Orders of Infinity", and makes use of it only in three papers (1910–1913). In the remaining papers (nearly 400!) and books he constantly uses the Landau symbols O and o.
Hardy's notation is not used anymore. On the other hand, in 1947, the Russian number theorist Ivan Matveyevich Vinogradov introduced his notation, which has been increasingly used in number theory instead of the notation. We have
- ,
and frequently both notations are used in the same paper.
The big-O, standing for "order of", was originally a capital omicron; today the identical-looking Latin capital letter O is used, but never the digit zero.
Read more about this topic: Big O Notation
Famous quotes containing the word history:
“To care for the quarrels of the past, to identify oneself passionately with a cause that became, politically speaking, a losing cause with the birth of the modern world, is to experience a kind of straining against reality, a rebellious nonconformity that, again, is rare in America, where children are instructed in the virtues of the system they live under, as though history had achieved a happy ending in American civics.”
—Mary McCarthy (1912–1989)