Notação Big O

No último artigo conhecemos as classes assintóticas e vimos como elas são importantes para a análise de algoritmos. Neste artigo veremos a primeira de três notações usadas na computação para representar o comportamento assintótico dos algoritmos: a notação O (pronuncia-se “bigue ôu”).

Se você ainda não leu o artigo sobre classes assintóticas, clique neste link e acesse o artigo onde te ensinamos conhecimentos valiosos sobre o assunto.

Da maneira mais objetiva possível, a notação O nos fornece uma simbologia simplificada para representar um limite superior de desempenho para um algoritmo. Um limite máximo de tempo que um algoritmo leva para ser executado:

• Ao invés de dizer que a complexidade de tempo do algoritmo Bubble Sort (no pior caso) é igual a T(n)= 5n²-n+1, dizemos que sua complexidade é O(n²) (lê-se “bigue ôu de n ao quadrado”). Usamos a classe quadrática n² dentro dos parênteses da notação para especificar que o algoritmo leva, no máximo, um tempo quadrático para ser executado.
• Ao invés de dizer que a complexidade de tempo do algoritmo linear é igual a T(n)= 4n+1, dizemos que sua complexidade é O(n) (lê-se “bigue ôu de n”). Usamos a classe linear n dentro dos parênteses da notação para especificar que o algoritmo leva, no máximo, um tempo linear para ser executado.

Essa é uma explicação um pouco rasteira, mas serve de introdução para você começar a compreender o significado e o uso da notação O.

Exemplo para função linear

Quando dizemos que a função linear 4n+1 é O(n), estamos afirmando que: “o comportamento assintótico de uma função linear é igual ou superior ao dela“. Significa dizer: a função 4n+1 nunca crescerá a ponto de ultrapassar o comportamento linear.

Desta forma, O(n) apresenta-se como um limite superior, e sabemos que a função 4n+1 nunca apresentará um comportamento de crescimento que ultrapasse esse limite superior.

Exemplo: para a função 4n+1, existe uma outra função de comportamento linear que a limita superiormente. Perceba no gráfico abaixo que, para valores de n>1, a função 4n+1 é superada por uma outra função linear (em azul).

Da mesma forma, também é correto afirmar que a função linear 4n+1 é O(n²), pois a função 4n+1 nunca crescerá a ponto de ultrapassar o comportamento quadrático. Portanto, O(n²) também se apresenta como um limite assintótico superior:

Por outro lado, seria errado dizer que a função linear 4n+1 é O(1), pois a função 4n+1 sempre crescerá a ponto de ultrapassar o comportamento constante. Desta forma, O(1) não se apresenta como um limite assintótico superior:

Resumindo:

4n+1 é O(n²), pois pode ser superada (limitada superiormente) por uma função quadrática.

4n+1 é O(n), pois pode ser superada (limitada superiormente) por uma função linear.

4n+1 não é O(1), pois não pode ser superada (limitada superiormente) por uma função constante.

Exemplo para função quadrática

Quando dizemos que a função quadrática 5n²-n+1 é O(n²), estamos afirmando que: “o comportamento assintótico de uma função quadrática é igual ou superior ao dela“. Significa dizer: a função 5n²-n+1 nunca crescerá a ponto de ultrapassar o comportamento quadrático.

Desta forma, O(n²) apresenta-se como um limite superior, e sabemos que a função 5n²-n+1 nunca apresentará um comportamento de crescimento que ultrapasse esse limite superior.

Perceba no gráfico abaixo que: para a função 5n²-n+1, existe uma outra função (em azul) de comportamento quadrático que a limita superiormente:

Da mesma forma, também é correto afirmar que a função quadrática 5n²-n+1 é O(n³), pois a função 5n²-n+1 nunca crescerá a ponto de ultrapassar o comportamento cúbico. Portanto, O(n³) também se apresenta como um limite assintótico superior:

Por outro lado, seria errado dizer que a função 5n²-n+1 é O(n), pois a função 5n²-n+1 sempre crescerá a ponto de ultrapassar o comportamento linear. Desta forma, O(n) não se apresenta como um limite assintótico superior:

Resumindo:

5n²-n+1 é O(n³), pois pode ser superada (limitada superiormente) por uma função cúbica.

5n²-n+1 é O(n²), pois pode ser superada (limitada superiormente) por uma função quadrática.

5n²-n+1 não é O(n), pois não pode ser superada (limitada superiormente) por uma função linear.

Definição matemática formal da Notação Big O

Dada duas funções de complexidade de tempo de algoritmos: f(n) e g(n). A definição matemática formal estabelece que:

• f(n) = O(g(n)) (lê-se “f de n é bigue ôu de g de n”) se existirem constantes positivas c e n₀, tais que f(n) ≤ c.g(n) para todos os n ≥ n₀.

Essa definição parece um pouco complicada de se compreender à primeira vista, mas vamos demonstrar com alguns exemplos práticos.

Resolução matemática: 1º exemplo

Vamos tentar demonstrar pela definição que 4n+1=O(n) (lê-se “é bigue ôu de n”).

Primeiramente, temos que:

• f(n) = 4n+1
• g(n) = n

Se, pela definição matemática, precisamos demonstrar que existe uma constante positiva c e um valor positivo n₀ inicial, de forma que:

• f(n) ≤ c.g(n) para todos os n ≥ n₀.

Então, para este problema, precisamos mostrar que:

• 4n+1 ≤ c.n para todos os n ≥ n₀.

Em resumo: precisamos provar que, para todos os valores de n maiores ou igual a n₀, a função 4n+1 é menor ou igual a c multiplicado por n.

Para tanto, a primeira decisão que precisamos tomar é escolher um valor para a constante c. Neste caso, vamos considerar c igual ao valor 5. Observe abaixo uma tabela que mostra os resultados da desigualdade para c=5 e para alguns valores de n

Observe que, para n igual a 0(zero), a função do algoritmo 4n+1 é maior que c.n. Mas quando n é igual a 1 os valores de c.n começam a superar a função do algoritmo 4n+1. Quando plotamos um gráfico para ambas as funções, visualizamos com maior clareza esse exato momento de superação da função c.n:

Isso significa que O(n) representa um limite assintótico superior para a função 4n+1. Pois, a partir de um determinado valor n, c.n supera a função 4n+1.

Contudo, o que realmente interessa para a análise de algoritmos é que conseguimos demonstrar o nosso objetivo, ou seja, que existe uma constante c (igual a 5) e um n₀ (igual a 1), tal que 4n+1 ≤ c.n para todos os valores de n maiores ou igual a n₀. Desta forma, está provado que, de fato, 4n+1=O(n) (é Big O de n).

Resolução matemática: 2º exemplo

Vamos tentar demonstrar pela definição que 5n²-n+1=O(n²) (lê-se “é bigue ôu de n ao quadrado”).

Primeiramente, temos que:

• f(n) = 5n²-n+1
• g(n) = n²

Se, pela definição matemática, precisamos demonstrar que existe uma constante positiva c e um valor positivo n₀ inicial, de forma que:

• f(n) ≤ c.g(n) para todos os n ≥ n₀

Então, para este problema, precisamos mostrar que:

• 5n²-n+1 ≤ c.n² para todos os n ≥ n₀

Em suma: precisamos provar que, para todos os valores de n maiores ou igual a n₀, a função 5n²-n+1 é menor ou igual a c multiplicado por n².

Novamente, precisamos escolher um valor para a constante c. Neste caso, também vamos considerar c igual ao valor 5. Observe abaixo uma tabela que mostra os resultados da desigualdade para c=5 e para alguns valores de n:

Observe que, para n igual a 0(zero), a função do algoritmo 5n²-n+1 é maior que c.n². Mas quando n é igual a 1 os valores de c.n² começam a superar a função do algoritmo 5n²-n+1. Quando plotamos um gráfico para ambas as funções, visualizamos com maior clareza esse exato momento de superação da função c.n²:

Isso significa que O(n²) representa um limite assintótico superior para a função 5n²-n+1. Pois, a partir de um determinado valor n, c.n² supera a função 5n²-n+1.

Contudo, o que realmente interessa para a análise de algoritmos é que conseguimos demonstrar o nosso objetivo, ou seja, que existe uma constante c (igual a 5) e um n₀ (igual a 1), tal que 5n²-n+1 ≤ c.n² para todos os valores de n maiores ou igual a n₀. Desta forma, está provado que, de fato, 5n²-n+1=O(n²) (é Big O de n ao quadrado).

Resolução matemática: 3º exemplo (errado)

Vamos tentar demonstrar pela definição que 2n²-n=O(n).

Primeiramente, temos que:

• f(n) = 2n²-n
• g(n) = n

Se, pela definição matemática, precisamos demonstrar que existe uma constante positiva c e um valor positivo n₀ inicial, de forma que:

• f(n) ≤ c.g(n) para todos os n ≥ n₀

Então, para este problema, precisamos mostrar que:

• 2n²-n ≤ c.n para todos os n ≥ n₀

Em suma: precisamos provar que, para todos os valores de n maiores ou igual a n₀, a função 2n²-n é menor ou igual a c multiplicado por n.

À primeira vista, percebe-se que 2n²-n possui comportamento quadrático e c.n possui comportamento linear. Desta forma, percebe-se que essa demonstração é falsa, pois uma função linear (c.n) não pode representar um limite assintótico superior para uma função quadrática (2n²-n).

No entanto, vamos realizar uma análise mais aprofundada para perceber o motivo dessa impossibilidade.

Vamos realizar algumas transformações algébricas no âmbito de isolar a constante c na inequação e perceber os seus possíveis valores:

A inequação resultante já nos mostra a impossibilidade de existir alguma constante c que a torne válida para grandes valores de n (n→∞), pois, independentemente do quão grande for o valor de c, o valor de n sempre irá superá-lo.

Abaixo são exibidos alguns gráficos que ilustram alguns cenários de c.n sendo superada pela função quadrática 2n²-n para diferentes valores da constante c.

Em resumo: não importa quão grande seja a constante c, a função 2n²-n sempre irá superar a função c.n.

Portanto, não existe uma constante c e um n₀, tal que 2n²-n ≤ c.n para todos os valores de n maiores ou igual a n₀.

Desta forma, está provado que, de fato, 2n²-n≠O(n) (lê-se “não é bigue ôu de n”).

Exercícios

Para demonstrar que você compreendeu bem o conceito e a definição matemática formal da notação Big O, resolva os exercícios propostos:

Exercícios A

Tente demonstrar matematicamente que n²+800=O(n²).

Tente demonstrar matematicamente que 2n+10=O(n).

Tente demonstrar matematicamente que n²=O(n).

Tente demonstrar matematicamente que 7n-2=O(n).

Tente demonstrar matematicamente que n²+20n+5=O(n³).

Exercício B

Utilizando a técnica de contagem de instruções, encontre a fórmula de complexidade T(n) do algoritmo abaixo e, em seguida, tente demonstrar matematicamente que essa fórmula encontrada é O(n).

1.public static void func(int[ ] n){
2.    for (int i=0; i<n.length-1; i++) {
3.            for (int j=0; j<n.length-1; j++) {
4.                n[j]=n[j]+i+j;
5.            }
6.    }
7.}

Continue os seus estudos neste curso e leia o próximo artigo sobre a segunda notação assintótica usada para representar desempenho de algoritmos: a “notação Big Ômega”.