4
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 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$
    – Emil Jeřábek
    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$
    – Emil Jeřábek
    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$
    – Emil Jeřábek
    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$
    – Sasho Nikolov
    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
8
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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