A simple (though somewhat pedantic) question: when using big O notation in a sentence, should it be preceded with "a" or "an"? Example:

The extra loop results in a/an $\mathcal{O}(N)$ increase in cost.

The ubiquitous Cormen textbook notes on page 47:

For a given function $g(n)$, we denote by $\mathcal{O}(g(n))$ (pronounced “big-oh of g of n” or sometimes just “oh of g of n”)

which would seem to indicate "a" should precede something pronounced "big-oh". Later on the same page, however, the textbook uses the phrase "an $\mathcal{O}(n^2)$ upper bound." Which is used more in the literature? It seems like a triviality, but as someone working on the edge of theoretical computer science from a primary focus on another field, I'd like not to sound like an outsider.

  • 4
    $\begingroup$ I think the common way to pronounce the offending sentence would have just “oh en increase” with no “big”, so an “an” is appropriate. $\endgroup$ Oct 8 '14 at 16:54
  • 9
    $\begingroup$ Speaking of pedantry, the proper way to typeset the big-oh notation, as it has been used for over a century, is $O(\dots)$. (I observe that the Cormen textbook agrees, I don’t know why you changed it in the quote.) The caligraphic $\mathcal O$ just displays a lack of taste. $\endgroup$ Oct 8 '14 at 17:11
  • 1
    $\begingroup$ (Tell me to shut up if I’m annoying.) While we are on the subject: on the other hand, a calligraphic $\mathcal P$ is an appropriate power-set notation. A depressingly large number of people abuse for that purpose the symbol for the Weierstraß elliptic function $\wp(z;\tau)$. $\endgroup$ Oct 8 '14 at 19:34
  • 1
    $\begingroup$ I may be the only one, but when I am wondering about similar issues I mentally expand "$O(N)$ increase" to "order of $N$ increase". $\endgroup$ Oct 8 '14 at 20:33
  • $\begingroup$ "...increases the running time by a factor of O(n)." (And pace Cormen, I've always pronounced it "order en".) $\endgroup$
    – Jeffε
    Oct 12 '14 at 16:29

Evidence for "an":

Of course, these examples alone merely suggest that "an" is acceptable. This list does not show that "an" is necessarily standard or preferred nor does it show that "a" is unacceptable.


Your Answer

