Notação O grande em LaTeX (O(n))

Onde é usado

Limite superior assintótico: f(n) = O(n) significa que f não cresce mais rápido que um múltiplo constante de n para n grande.

O O grande é a ferramenta básica da análise de algoritmos: a busca linear roda em O(n), a ordenação por intercalação em O(n \log n) e a multiplicação ingênua de matrizes em O(n^3). Em rigor, O(g) é um conjunto de funções, então f \in O(g) é a forma precisa, embora f(n) = O(g(n)) seja a convenção quase universal. Alguns autores preferem um \mathcal{O}(n) caligráfico para distinguir o operador de uma variável chamada O; escolha uma forma e mantenha-a em todo o artigo. Escreva o custo real dentro do argumento, como em O(n^2 \log n), e não O(n^2) \cdot \log n, e lembre-se de que O só limita por cima, portanto não afirma que o limite é justo.

Exemplo mínimo compilável

Cole isto em um arquivo .tex vazio e compile com 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}

Símbolos relacionados

• Notação Ômega grande\Omega(n)
• Notação Theta grande\Theta(n)
• Notação o pequenoo(n)
• Notação ômega pequeno\omega(n)
• Seta de aplicação\mapsto
• Sinal de definição:=

Perguntas frequentes

Como escrever Notação O grande em LaTeX?

Digite O(n) no modo matemático, por exemplo $T(n) = 2T(n/2) + O(n) \implies T(n) = O(n \log n)$. Funciona no LaTeX padrão sem carregar nenhum pacote.

Qual pacote é necessário para O(n)?

Nenhum. O(n) faz parte do LaTeX padrão, então compila só com a classe do documento no preâmbulo.

Posso usar O(n) no modo texto ou só no modo matemático?

Nos dois. O(n) compila no texto corrido e dentro de $...$; em uma fórmula, mantenha-o no modo matemático para que use as fontes e o espaçamento matemáticos.