What is O in Big O?

What is Big and O in Big O notation? I've read the definitions and it doesn't tell what is O pronounced as 'oh'. For example - I understand that O(n) is complexity of a linear algorithm where n could be the number of operations. but what is an O?

-
It's the 15th letter of the English alphabet. It's also the 15th letter in the Greek alphabet. – Joel Etherton Sep 13 '11 at 18:26
Just to clarify: You're looking for the reason as to why O is the symbol that is used (instead of Q or E or something else), and what meaning, if any, O has over other symbols? – FrustratedWithFormsDesigner Sep 13 '11 at 18:37
@Joel: Actually, it's Omicron, and that is the clue as to why this particular letter was chosen. – Jörg W Mittag Sep 13 '11 at 19:54

Well, my guess would be order, which coincides with wikipedia.

Edit: (my own (any improvements appreciated)) translation from the German wikipedia article

The capital letter O (actually a capital omicron at the time) as a symbol for the order of (German: "Ordnung von") was first used by the German number theorist Paul Bachman in the second issue of his book on analytic number theory appeared in 1894. The notation gained popularity due to the work of Edmund Landau, another German number theorist, whom this nomenclature is widely associated with today, especially in the German terminology.

-
While it may be the case that many mathematicians have referred to it as such, it was not originally so. If you read number theory books from the early 20th century, you will find no such explanation. It is what it is and I can't read German to figure out what his thinking was on the notation. – Jonathan Henson Sep 13 '11 at 19:11
@Jonathan: Post updated. – back2dos Sep 13 '11 at 20:55
Very nice! I looked in all of my number theory books and I couldn't find an explanation of the O anywhere. +1 – Jonathan Henson Sep 13 '11 at 21:06
I've always pronounced it as order of as just saying O does not mean much. – Newtopian Sep 14 '11 at 1:28

"Big" means "capital", and "O" means order, as in "order of complexity". So named because of the convention of writing "order of complexity" as O(f(x)), e.g., with a capital letter 'O', or a 'Big O'. Nobody talks about it much because 'everyone' understands what it means, and understanding it doesn't really help you understand complexity analysis.

For an understanding of complexity analysis, I think the link posted by topgun_ivard is a good place to start. A good introductory textbook covering data structures or algorithms might also help.

-
I'm sorry, but Bachmann-Landau notation was invented by a German mathematician, so I hardly think he would have named it after an English word. In fact, even if it had been invented by an American mathematician, it would probably still have been named after a German word, because when it was invented (around 1920, I think), the international language of mathematics was German. Plus, it doesn't even remotely have anything to do with complexity. – Jörg W Mittag Sep 13 '11 at 19:52
@Jörg: Yes, but wouldn't that just be Ordnung, which the German wiki article claims to be the origin: de.wikipedia.org/wiki/Landau-Symbole#Geschichte – back2dos Sep 13 '11 at 20:44
@Ethel could you make a minor change to your article so that I can vote you up? You are indeed correct. You have to edit before I can vote. – Jonathan Henson Sep 13 '11 at 21:08
@Jonathan, I'm not sure exactly what minor change you want. Can you just go ahead and make the edit you want? Or, we could just let back2dos' answer stand, it looks like he might have ended up with the best answer anyway due to some excellent research :) – Ethel Evans Sep 14 '11 at 17:36
No, I just wanted to vote you up, and it says that you have to edit your answer before I can inbecause I had a previous vote locked . You don't need to change any thing. Just add a space or a comma somewhere. If you don't want the point then don't worry about it, I was just trying to give credit where it was do. – Jonathan Henson Sep 14 '11 at 18:31

O stands for order.

It was originally introduced by the German mathematician Paul Bachmann in the second volume of his books on number theory Die Analytische Zahlentheorie, published in 1894 (p. 401). He notes, after a formula where he first uses the notation:

(...) wenn wir durch das Zeichen O(n) einde Grösse ausdrücken, deren Ordnung in Bezug auf n die Ordnung von n nicht überschreitet (...)

My translation:

(...) where with the notation O(n) we indicate a magnitude of which the order with reference to n does not exceed the order of n (...)

In contrast with what others have said, nothing in his text indicates that this is in fact a Greek capital omikron. He uses plenty of both Greek and Latin characters, so there isn't really any way to tell. Given his continued use of "Ordnung n log n" etc. in the text it's clear that it stands for "Ordnung" (German for "order" if there was any doubt) in any case, but that could still leave open the use of a fancy Greek O.

However, the origin of the omikron is more likely a retronym due to Donald Knuth who introduced the symbols omega (Ω) and theta (Θ) for related concepts in his paper Big Omicron and Big Omega and Big Theta, or possibly Hardy and Littlewood who introduced an omega symbol earlier.

-
Interesting. I suppose you are right. I just looked up the definitions in both Landau's and Bachmann's books, and they indeed a) use a Latin Oh, not a Greek Omikron, b) both use the word "Ordnung", and c) Landau explicitly states that it means "Ordnung". I stand corrected. – Jörg W Mittag Sep 14 '11 at 1:20
What better word could be found? I mean, from a German? Ordnung ist das halbe Leben! – JensG Jun 1 '14 at 13:33

Quoting a section from the article:
Big Greek Letters

Big O is often misused. Big O or Big Oh is actually short for Big Omicron. It represents the upper bound of asymptotic complexity. So if an algorithm is O(n log n) there exists a constant c such that the upper bound is cn log n.

Θ(n log n) (Big Theta) is more tightly bound than that. Such an algorithm means there exists two constants c1 and c2 such that c1n log n < f(n) < c2n log n.

Ω(n log n) (Big Omega) says that the algorithm has a lower bound of cn log n.

There are others but these are the most common and Big O is the most common of all. Such a distinction is typically unimportant but it is worth noting. The correct notation is the correct notation, after all.

What is Big O?

Big O notation seeks to describe the relative complexity of an algorithm by reducing the growth rate to the key factors when the key factor tends towards infinity. For this reason, you will often hear the phrase asymptotic complexity. In doing so, all other factors are ignored. It is a relative representation of complexity.

What Isn’t Big O?

Big O isn’t a performance test of an algorithm. It is also notional or abstract in that it tends to ignore other factors. Sorting algorithm complexity is typically reduced to the number of elements being sorted as being the key factor. This is fine but it doesn’t take into account issues such as:

Memory Usage: one algorithm might use much more memory than another. Depending on the situation this could be anything from completely irrelevant to critical; Cost of Comparison: It may be that comparing elements is really expensive, which will potentially change any real-world comparison between algorithms; Cost of Moving Elements: copying elements is typically cheap but this isn’t necessarily the case; etc.

-
Simply linking an article isn't overly helpful. It's usually a good idea to paraphrase or quote the section that you find especially relevant to the thread. – Demian Brecht Sep 13 '11 at 18:30
Are the down votes really necessary? The article he linked is very relevant, and IMHO pretty helpful. Meanwhile, the top voted answer is a link to a Wikipedia article. +1 to offset the hypocrisy of the hive-mind. – Brandon Moretz Sep 13 '11 at 19:09
-1, because the artice, while being a very nice and well-written article, doesn't have anything to do with the question. – Jörg W Mittag Sep 13 '11 at 19:55
@Jorg, I never said the article would solve the problem, but I shared because I had found it useful when I was looking at these concepts. – topgun_ivard Sep 13 '11 at 20:19
@topgun_ivard: So what happens if it turns into a dead link? Paraphrasing allows 1) the audience of this thread to get a Coles notes version of your link (time is money), and 2) ensures that your post is not rendered irrelevant on a dead link. – Demian Brecht Sep 13 '11 at 20:45

"f(x) is big-oh of g(x)"

It is a mathematical way to predict the growth of functions.

Let f and g be functions from the set of integers or the set or real numbers to the set of real numbers. We say that f(x) is O(g(x)) if there are constants C and k such that |f(x)| <= C|g(x)| wherever x > k.

You would read this as "f(x) is big-oh of g(x)"

The big-O is sometimes called a Landau symbol after the German mathematician Edmund Landau. I don't think it stands for anything beyond that. You also have the similar big-Omega and big-Theta notations. The symbols are as arbitrary as always using theta to denote the angles in your triangles was in your high-school Planar Geometry class.

Correction @back2dos has provided a satisfactory explanation for the O as referring to order. Great Job. See his answer.

Donald Knuth applied it to studying the complexity of computer programs.

If you want to find the reason the notation was used, you should read

"Analytische Zahlentheorie" by Paul Bachmann from 1892

-

EDIT: Turns out that I am wrong. Nevertheless, maybe this helps someone keep their symbols straight, so I'm not going to delete it.

Actually, it's not the Latin letter Oh, it's the Greek letter Omicron. Unfortunately, those two have the exact same glyph, so, over time, the original version got corrupted, and now it is just Oh.

The choice of symbol doesn't actually have any particular meaning, it was chosen as a mnemonic device:

• Omicron has the letters M-I-C-R-O in it, and the semantics of the Omicron symbol roughly mean "smaller than"
• Omega has the letters M-E-G-A in it, and the semantics of the Omega symbol roughly mean "bigger than"
• Theta (Θ) looks a bit like an equals sign, and the semantics of the Theta symbol roughly mean "equal to"

That's it. There's no real meaning to it, it's just a play on words, if you will, to help you remember the semantics more easily.

-
While I would love to believe your mnemonic proposition (it is a really cool idea), I am going to need to see some proof that this is the actual original intention of Bachmann. Provide it, and I'll +1 you. – Jonathan Henson Sep 13 '11 at 20:40
@Jonathan Henson: Apparently, I was misled by Prof. Knuth :-) – Jörg W Mittag Sep 14 '11 at 1:22

UPDATE: Attempting to clean up my answer and be more accurate

Big O notation is a way to characterize functions according to there growth rates. The O stands for order (first order being n second order being n-squared etc). And if I am not mistaken this would be the worst case scenario for a methods runtime(or storage) given N elements. The larger the order the worst the method performs.
For instance looking up a record in an array is O(1) (I believe in some implementation of a hash tables that is also the case). Adding a value to the end of a link list would be O(N) because you have to get to the end of the list before you can add the element etc.

This answer should be slightly more correct than my first attempt :)

-
-1 because this is just plain old incorrect AND answered a separate question than was asked. The question was why is the letter "O" used, not "how does Big O notation work?". You're incorrect about how Big-oh works as well though...looping through an array is O(n) where n is the size of the array, not O(1). The notation has nothing to do with "cycles" of an algorithm...it's a measurement of the upper bound of the run time of an algorithm. – Casey Patton Sep 14 '11 at 1:37
Not to argue with you here, but that's kind of what I meant. What does run time mean right? Well, run time is determined by what has to be processed on the machine. I guess I kind of use cycle liberally here. By cycle I guess I should have said iterate-through or something like that. You are right about upper bound though, It does not determine the average. Therefore I accept the downgrade. – DmainEvent Sep 14 '11 at 12:19