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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s