Notação Big-Ω (Grande-Omega)

Algumas vezes, queremos dizer que um algoritmo leva ao menos uma certa quantidade de tempo, sem fornecer um limite superior. Usamos a notação Ω, que é a letra grega "omega" maiúscula.

Se um tempo de execução é $\mathrm{\Omega }(f(n))$‍, então, para um $n$‍ suficientemente grande, ele será ao menos $k\cdot f(n)$‍ para uma constante $k$‍ qualquer. Aqui está um exemplo de um tempo de execução igual a $\mathrm{\Omega }(f(n))$‍:

Dizemos que tal tempo de execução é "Ω de $f(n)$‍". Usamos a notação Ω para limites assintóticos inferiores, uma vez que delimita de modo otimista o aumento do tempo de execução para entradas suficientemente extensas.

Assim como $\mathrm{\Theta }(f(n))$‍ automaticamente implica $O(f(n))$‍, também automaticamente implica $\mathrm{\Omega }(f(n))$‍. Então podemos dizer que o tempo de execução no pior caso da busca binária é $\mathrm{\Omega }({\log }_{2}n)$‍.

Também podemos fazer afirmações corretas, porém imprecisas, usando a notação big-Ω. Por exemplo, se você realmente tem um milhão de reais no seu bolso, você pode dizer de forma verdadeira "Eu tenho uma quantia de dinheiro no meu bolso que é ao menos 10 reais." Isso é correto, mas certamente não é muito preciso. De forma similar, podemos dizer corretamente, porém de forma imprecisa, que o tempo de execução no pior caso da busca binária é $\mathrm{\Omega }(1)$‍, porque sabemos que ela leva pelo menos um tempo constante.

Claro que quando estamos falando sobre algoritmos, tentamos descrever seus tempos de execução da forma mais precisa possível. Aqui, fornecemos os exemplos de afirmações imprecisas para ajudar você a entender melhor as notações $\mathrm{\Omega }$‍, $O$‍ e $\mathrm{\Theta }$‍.

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.