Notação Big-O

Usamos a notação big-Θ para limitar de forma assintótica o crescimento do tempo de execução com fatores constantes acima e abaixo. Algumas vezes, vamos querer limitar somente acima.

Por exemplo, embora o tempo de execução do pior caso da busca binária seja $\mathrm{\Theta }({\log }_{2}n)$‍, seria incorreto dizer que a busca binária é executada em $\mathrm{\Theta }({\log }_{2}n)$‍ em todos os casos. E se encontrarmos o valor procurado no primeiro chute? Então o programa é executado em $\mathrm{\Theta }(1)$‍. O tempo de execução da busca binária nunca é pior que $\mathrm{\Theta }({\log }_{2}n)$‍, mas algumas vezes ele é melhor.

Seria conveniente ter uma forma de notação assintótica que diga "o tempo de execução cresce no máximo até um determinado valor, mas poderia crescer mais devagar". A notação "big-O" serve para essas ocasiões.

Se um tempo de execução é $O(f(n))$‍, então para um $n$‍ suficientemente grande , o tempo de execução é no máximo $k\cdot f(n)$‍ para alguma constante $k$‍. Veja como pensar em um tempo de execução que é $O(f(n))$‍:

Dizemos que o tempo de execução é "big-O de $f(n)$‍" ou apenas "O de $f(n)$‍." Usamos a notação big-O para limites assintóticos superiores, uma vez que ela limita o crescimento do tempo de execução superior para valores sufientemente grandes de entrada.

Agora temos uma forma de caracterizar o tempo de execução da busca binária em todos os casos. Podemos dizer que o tempo de execução da busca binária é sempre $O({\log }_{2}n)$‍. Podemos fazer uma afirmação mais forte sobre o tempo de execução no pior caso: ele é $\mathrm{\Theta }({\log }_{2}n)$‍. No entanto, se quisermos cobrir todos os casos, a afirmação mais forte que podemos fazer é que a busca binária executa em tempo $O({\log }_{2}n)$‍.

Se você voltar à definição da notação big-Θ, você verá que ela se parece com a notação big-O, exceto que a notação big-Θ limita o tempo de execução superior e inferior, em vez de usar apenas o limite superior. Se dissermos que o tempo de execução é $\mathrm{\Theta }(f(n))$‍ em um caso particular, então ele também será $O(f(n))$‍. Por exemplo, podemos dizer que como o pior caso do tempo de execução da busca binária é $\mathrm{\Theta }({\log }_{2}n)$‍, ele também é $O({\log }_{2}n)$‍.

O inverso não é necessariamente verdade: como vimos, podemos dizer que a busca binária sempre é executada em $O({\log }_{2}n)$‍, mas não que ela sempre é executada em $\mathrm{\Theta }({\log }_{2}n)$‍.

Como a notação big-O fornece somente um limite superior assintótico e não um limite assintótico ajustado, podemos fazer afirmações que à primeira vista parecem incorretas, mas estão tecnicamente corretas. Por exemplo, é absolutamente correto dizer que a busca binária é executada em $O(n)$‍. Isso porque o tempo de execução não cresce mais rápido do que uma constante vezes $n$‍. Na verdade, cresce mais lentamente.

Pense desta forma. Suponha que você tem 10 reais no seu bolso. Você vai até seu amigo e diz, "Eu tenho uma quantia de dinheiro no meu bolso, e eu garanto que não é mais do que um milhão de reais". Sua declaração é absolutamente verdadeira, porém não muito precisa.

Um milhão de reais é um limite superior a 10 reais, assim como $O(n)$‍ é um limite superior ao tempo de execução da busca binária. Outros limites superiores imprecisos para a busca binária seriam $O(n^2)$‍, $O(n^3)$‍, e $O(2^n)$‍. Mas $\mathrm{\Theta }(n)$‍, $\mathrm{\Theta }(n^2)$‍, $\mathrm{\Theta }(n^3)$‍, e $\mathrm{\Theta }(2^n)$‍ não seriam corretos para descrever o tempo de execução da busca binária em nenhum caso.

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.