Grande-O

A notação do Grande-O ou notação assimptótica (ou como é conhecido em inglês, Big-O Notation, ou Big Omicron Notation) é uma notação matemática utilizada para analisar o comportamento assintótico de funções. Essa notação é bastante utilizada para a análise de algoritmos em ciência da computação.

A criação dessa notação é creditada ao matemático alemão Paul Bachmann, em 1894, na publicação da segunda versão da sua obra Analytische Zahlentheorie, sendo popularizada por outro alemão, Edmund Landau, e por causa disso, essa notação é também conhecida como "Símbolo de Landau". Essa notação é padronizada como "ordem de".

De um modo informal, dizemos que uma função $f$ pode ser representada como $O(g(x))$ se ambas funções, para $x$ suficientemente grande, "crescem" da mesma forma, ou seja, são "proporcionais". Se $f$ é $O(g(x))$, então, para $x$ grande o suficiente, se num dado intervalo $f$ dobra, então $g$ "dobra" também (com erro pequeno), e vice-versa. Por exemplo, $f(x) = 10x^5 + 3x^3$ é $O(x^5)$.

Definição

Sejam duas funções reais f(x) e g(x). É definido:

$O(g(x)) = \left\{\begin{matrix} f(x) : \mbox{existem } c,x_0 \mbox{ constantes positivas tais que} \\ \forall x:x_0\le x: 0\le f(x)\le cg(x) \end{matrix}\right\}$

A definição acima diz que a função f(x) é superiormente limitada pela função g(x).

Na definição foi utilizado f(x) = O(g(x)), mas é mais correto escrever f(x) é O(g(x)), ou f(x) ∈ O(g(x)), já que O(g(x)) define um conjunto de funções (ou classes de funções).

Para demonstrar que f(x) é O(g(x)), não basta encontrar dois números c e x₀ tais que a definição acima seja satisfeita, já que podem existir funções que satisfaçam a condição referida apenas para alguns valores. As demonstrações são usualmente feitas por indução.

Exemplos

• A função f(x) = 10x + 11 é O(x). Como exemplo, basta utilizar c = 12 e x₀ = 10.

• A função f(x) = x² + 100 é O(x²). Como exemplo, basta utilizar c = 2 e x₀ = 10.

Ordens mais comuns

Abaixo há uma lista de classes de funções que são bastante utilizadas para análise de algoritmos, por ordem crescente de crescimento de funções (as funções que têm um crescimento mais lento, são as primeiras). A letra c denota uma constante qualquer.

notação	nome
O(1)	ordem constante
O(log x)	ordem logarítmica
O([log x]c)	ordem poli-logarítmica
O(x)	ordem linear
O(x · log x)	ordem linear-logarítmica
O(x²)	ordem quadrática
O(x³)	ordem cúbica
O(xc)	ordem polinomial
O(cx)	ordem exponencial
O(x!)	ordem fatorial
O(xx)	ordem exponencial

Propriedades

Soma

$O(f(n)) + O(g(n)) = O(\max \lbrace f(n),g(n) \rbrace) \,$

Ex.: $f(n) = 10 \log n + 5 (\log n)^3 + 7n + 3n^2 + 6n^3 \in \hbox{O}(n^3)\,\!$.

Produto

$O(f(n))O(g(n)) = O(f(n)g(n)) \,$

Multiplicação por uma constante

$O(k g(n)) = O(g(n)) \!\,$, desde que k≠0