# Big Oh

It tickles me that in the study of algorithm complexity analysis, the symbol representing “Big Oh”, the set of asymptotic upper bounds of a function, is upper-case Omicron, $O$.

The name “Omicron” is a conjunction of O and micron, and so is ancient Greek for “little O”.

Ancient Greek for “big O” would be O and mega, or Omega, $\Omega$. As it happens, $\Omega$ is the symbol for the set of asymptotic lower bounds of a function.

The “Big O” notation was popularized in computer science by Donald Knuth, but dates back to  work by Paul Bachmann, published in 1894.

My suspicion is that “Big O” was initially meant to indicate the “Order” of a function (i.e., the magnitude of its rate of growth), and that Theta and Omega were introduced later to indicate expected value and lower bound, respectively.  I have not been able to validate this hunch, however.