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?

  • 13
    It's the 15th letter of the English alphabet. It's also the 15th letter in the Greek alphabet. Commented Sep 13, 2011 at 18:26
  • 2
    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? Commented Sep 13, 2011 at 18:37
  • 6
    @Joel: Actually, it's Omicron, and that is the clue as to why this particular letter was chosen. Commented Sep 13, 2011 at 19:54
  • 1
    this answer refutes (correctly, I think) the Omicron theory. Commented Nov 14, 2016 at 18:51

7 Answers 7


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.

  • 5
    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. Commented Sep 13, 2011 at 19:11
  • 1
    @Jonathan: Post updated.
    – back2dos
    Commented Sep 13, 2011 at 20:55
  • 1
    Very nice! I looked in all of my number theory books and I couldn't find an explanation of the O anywhere. +1 Commented Sep 13, 2011 at 21:06
  • 3
    I've always pronounced it as order of as just saying O does not mean much.
    – Newtopian
    Commented Sep 14, 2011 at 1:28
  • Very informative! but still - Why O pronounced as 'oh' by programmers?
    – RBT
    Commented Dec 22, 2019 at 7:38

"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.

  • 5
    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. Commented Sep 13, 2011 at 19:52
  • 1
    @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
    Commented Sep 13, 2011 at 20:44
  • 1
    @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. Commented Sep 13, 2011 at 21:08
  • 1
    @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 :) Commented Sep 14, 2011 at 17:36
  • 1
    Hm, interesting. In Sweden, Big Oh is usually called "ordo" (latin for, well, order) rather than "ordning" (the Swedish word for order).
    – Vatine
    Commented Sep 21, 2012 at 8:43

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.

  • 2
    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. Commented Sep 14, 2011 at 1:20
  • What better word could be found? I mean, from a German? Ordnung ist das halbe Leben!
    – JensG
    Commented Jun 1, 2014 at 13:33
  • I think the first sentence of your (correct, upvoted, awesome) answer should read: 'O stands for "Ordnung" (German meaning "Order").' It would help this answer to grab the attention of other readers. Commented Nov 14, 2016 at 18:49

I like this article, hoping you would find it useful too!

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.

  • 5
    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. Commented Sep 13, 2011 at 18:30
  • 3
    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. Commented Sep 13, 2011 at 19:09
  • 1
    -1, because the artice, while being a very nice and well-written article, doesn't have anything to do with the question. Commented Sep 13, 2011 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. Commented Sep 13, 2011 at 20:19
  • 3
    @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. Commented Sep 13, 2011 at 20:45

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.

  • 2
    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. Commented Sep 13, 2011 at 20:40
  • 2
    @Jonathan Henson: Apparently, I was misled by Prof. Knuth :-) Commented Sep 14, 2011 at 1:22

"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


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 :)

  • 2
    -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. Commented Sep 14, 2011 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. Commented Sep 14, 2011 at 12:19

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