The big O, big theta, and other notations form the family of Bachmann-Landau or asymptotic notations. These notations describe the limiting behavior of a function in mathematics or classify algorithms in computer science according to their complexity / processing time. In this post, I’m not so much interested in the definition of these notations, but rather in how to correctly typeset them in LaTeX.
Example of a big O notation
There are two possible ways to type the big O:
$O(n\log{}n)$ % regular O
$\mathcal{O}(n\log{}n)$ % Open at top left
The latter produces the following:
No additional package is required for either of these.
Complete list of Bachmann-Landau notations
The complete list of Bachmann-Landau or asymptotic notations is given below. To copy-paste any of these, use the source code.
\documentclass[11pt]{article}
\newcommand{\bslash}{\char`\\}
\begin{document}
\section*{Big O notations}
$\mathcal{O}(n\log{}n)$
\section*{Family of Bachmann-Landau notations}
\setlength{\tabcolsep}{12pt}
\renewcommand*{\arraystretch}{1.2}
\begin{tabular}{lcl}
\hline
Name&Notation&Command\\
\hline
{\bf Big O(micron)}&$\mathcal{O}$ or $O$&\texttt{\$\bslash mathcal\{O\}\$ or \$O\$}\\
{\bf Big Omega}&$\Omega$&\texttt{\$\bslash Omega\$}\\
{\bf Big Theta}&$\Theta$&\texttt{\$\bslash Theta\$}\\
{\bf Small O(micron)}&$o$&\texttt{\$o\$}\\
{\bf Small Omega}&$\omega$&\texttt{\$\bslash omega\$}\\
{\bf On the order of}&$\sim$&\texttt{\$\bslash sim\$}\\
\hline
\end{tabular}
\vspace{10pt}\hfill{\scriptsize Created by http://texblog.org}
\end{document}