Notation grand O en LaTeX (O(n))

Où il est utilisé

Borne supérieure asymptotique : f(n) = O(n) signifie que f ne croît pas plus vite qu’un multiple constant de n pour n grand.

Le grand O est l’outil de base de l’analyse d’algorithmes : la recherche linéaire s’exécute en O(n), le tri fusion en O(n \log n), la multiplication matricielle naïve en O(n^3). En toute rigueur, O(g) est un ensemble de fonctions, si bien que f \in O(g) est la forme exacte, même si f(n) = O(g(n)) est la convention quasi universelle. Certains auteurs préfèrent un \mathcal{O}(n) calligraphique pour distinguer l’opérateur d’une variable nommée O ; choisissez une forme et gardez-la dans tout l’article. Écrivez l’argument avec le coût réel à l’intérieur, comme O(n^2 \log n), plutôt que O(n^2) \cdot \log n, et rappelez-vous que O ne borne que par le haut : il n’affirme pas que la borne est atteinte.

Exemple minimal compilable

Collez-le dans un fichier .tex vide et compilez avec pdfLaTeX, XeLaTeX ou LuaLaTeX.

\documentclass{article}
\usepackage{amsmath}
\begin{document}
Big O: $O(n)$

\[ T(n) = 2T(n/2) + O(n) \implies T(n) = O(n \log n) \]
\end{document}

Symboles associés

• Notation grand Oméga\Omega(n)
• Notation grand Thêta\Theta(n)
• Notation petit oo(n)
• Notation petit oméga\omega(n)
• Flèche d’application\mapsto
• Égalité de définition:=

Questions fréquentes

Comment écrire Notation grand O en LaTeX ?

Tapez O(n) en mode mathématique, par exemple $T(n) = 2T(n/2) + O(n) \implies T(n) = O(n \log n)$. La commande fonctionne en LaTeX standard sans charger de paquet.

Quel paquet faut-il pour O(n) ?

Aucun. O(n) fait partie de LaTeX standard : le préambule n’a besoin que de la classe de document.

Peut-on utiliser O(n) en mode texte, ou seulement en mode mathématique ?

Les deux. O(n) compile dans le texte comme dans $...$ ; dans une formule, gardez le mode mathématique pour les polices et l’espacement mathématiques.