O grande in LaTeX (O(n))

Dove si usa

Limite superiore asintotico: f(n) = O(n) significa che f non cresce più rapidamente di un multiplo costante di n per n grande.

La notazione O grande è lo strumento principale dell'analisi degli algoritmi: la ricerca lineare richiede O(n), il merge sort O(n \log n), la moltiplicazione di matrici ingenua O(n^3). A rigore O(g) è un insieme di funzioni, quindi f \in O(g) è la forma precisa, anche se f(n) = O(g(n)) è la convenzione quasi universale. Alcuni autori preferiscono una \mathcal{O}(n) calligrafica per distinguere l'operatore da una variabile chiamata O; sceglietene una e restate coerenti in tutto l'articolo. Scrivete l'argomento con il costo reale all'interno, come O(n^2 \log n), anziché O(n^2) \cdot \log n, e ricordate che O limita solo dall'alto, quindi non afferma che il limite sia stretto.

Esempio minimo compilabile

Incollalo in un file .tex vuoto e compilalo con pdfLaTeX, XeLaTeX o 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}

Simboli correlati

• Omega grande\Omega(n)
• Theta grande\Theta(n)
• o piccoloo(n)
• omega piccolo\omega(n)
• Freccia di applicazione\mapsto
• Simbolo di definizione (due punti e uguale):=

Domande frequenti

Come si scrive O grande in LaTeX?

Scrivi O(n) in modalità matematica, per esempio $T(n) = 2T(n/2) + O(n) \implies T(n) = O(n \log n)$. Funziona in LaTeX standard senza caricare alcun pacchetto.

Quale pacchetto serve per O(n)?

Nessuno. O(n) fa parte di LaTeX standard, quindi compila con la sola classe del documento nel preambolo.

Posso usare O(n) in modalità testo o solo in modalità matematica?

Entrambe. O(n) compila nel testo e dentro $...$; in una formula lascialo in modalità matematica, così usa i font e la spaziatura matematici.