<p>Evidence for "an":</p>

<ul>
<li>Ajtai, Miklós, János Komlós, and Endre Szemerédi. "<a href="http://dl.acm.org/citation.cfm?id=808726">An O(n log n) sorting network.</a>" Proceedings of the fifteenth annual ACM symposium on Theory of computing. ACM, 1983.</li>
<li>Asadpour, Arash, et al. "<a href="http://epubs.siam.org/doi/abs/10.1137/1.9781611973075.32">An O(log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem.</a>" SODA. Vol. 10. 2010.</li>
<li>Bracha, Gabriel. "<a href="http://dl.acm.org/citation.cfm?id=42229">An O(log n) expected rounds randomized Byzantine generals protocol.</a>" Journal of the ACM (JACM) 34.4 (1987): 910-920.</li>
<li>Hwang, F. K. "<a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1084551">An O(n log n) algorithm for suboptimal rectilinear Steiner trees.</a>" Circuits and Systems, IEEE Transactions on 26.1 (1979): 75-77.</li>
<li>Tarjan, Robert E., and Christopher J. Van Wyk. "<a href="http://epubs.siam.org/doi/abs/10.1137/0217010">An O(n log log n)-time algorithm for triangulating a simple polygon.</a>" SIAM Journal on Computing 17.1 (1988): 143-178.</li>
<li>Yao, Andrew Chi-Chih. "<a href="http://www.sciencedirect.com/science/article/pii/0020019075900563">An O (|E| log log|V|) algorithm for finding minimum spanning trees.</a>" Information Processing Letters 4.1 (1975): 21-23.</li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2014-10-09T20:14:42.367Z
2014-10-09T20:14:42.367Z
mhum
<p>A simple (though somewhat pedantic) question: when using big O notation in a sentence, should it be preceded with "a" or "an"?  Example:</p>

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

<p>The ubiquitous Cormen textbook notes on page 47:</p>

<blockquote>
  <p>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”)</p>
</blockquote>

<p>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. </p>

CC BY-SA 3.0
2014-10-08T16:54:27.520Z
I think the common way to pronounce the offending sentence would have just “oh en increase” with no “big”, so an “an” is appropriate.
Emil Jeřábek
CC BY-SA 3.0
2014-10-08T17:11:02.883Z
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.
Emil Jeřábek
CC BY-SA 3.0
2014-10-08T19:34:28.767Z
(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)$.
Emil Jeřábek
CC BY-SA 3.0
2014-10-08T20:33:41.247Z
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".
Sasho Nikolov
CC BY-SA 3.0
2014-10-12T16:29:02.243Z
"...increases the running time by a factor of O(n)." (And pace Cormen, I've always pronounced it "order en".)
Jeffε
<notation>
"a" or "an" with big O notation?
Daisy Sophia Hollman
# "a" or "an" with big O notation?

(Asked by: username_0 on 2014-10-08)

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.

**Tags:** notation

> **Comments:**
> **username_1**: I think the common way to pronounce the offending sentence would have just “oh en increase” with no “big”, so an “an” is appropriate.  
> **username_1**: 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.  
> **username_1**: (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)$.  
> **username_2**: 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".  
> **username_3**: "...increases the running time by a factor of O(n)." (And pace Cormen, I've always pronounced it "order en".)  

---

## 1 answers

### Answer by username_4 on 2014-10-09. Score: 8 | Accepted answer

Evidence for "an":

* Ajtai, Miklós, János Komlós, and Endre Szemerédi. "[An O(n log n) sorting network.](http://dl.acm.org/citation.cfm?id=808726)" Proceedings of the fifteenth annual ACM symposium on Theory of computing. ACM, 1983.
* Asadpour, Arash, et al. "[An O(log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem.](http://epubs.siam.org/doi/abs/10.1137/1.9781611973075.32)" SODA. Vol. 10. 2010.
* Bracha, Gabriel. "[An O(log n) expected rounds randomized Byzantine generals protocol.](http://dl.acm.org/citation.cfm?id=42229)" Journal of the ACM (JACM) 34.4 (1987): 910-920.
* Hwang, F. K. "[An O(n log n) algorithm for suboptimal rectilinear Steiner trees.](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1084551)" Circuits and Systems, IEEE Transactions on 26.1 (1979): 75-77.
* Tarjan, Robert E., and Christopher J. Van Wyk. "[An O(n log log n)-time algorithm for triangulating a simple polygon.](http://epubs.siam.org/doi/abs/10.1137/0217010)" SIAM Journal on Computing 17.1 (1988): 143-178.
* Yao, Andrew Chi-Chih. "[An O (|E| log log|V|) algorithm for finding minimum spanning trees.](http://www.sciencedirect.com/science/article/pii/0020019075900563)" Information Processing Letters 4.1 (1975): 21-23.

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.


---

