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 é $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, então, para um $n$n suficientemente grande, ele será ao menos $k \cdot f(n)$k, dot, f, left parenthesis, n, right parenthesis para uma constante $k$k qualquer. Aqui está um exemplo de um tempo de execução igual a $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis:

Dizemos que tal tempo de execução é "Ω de $f(n)$f, left parenthesis, n, right parenthesis". 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 $\Theta(f(n))$\Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis automaticamente implica $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, também automaticamente implica $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. Então podemos dizer que o tempo de execução no pior caso da busca binária é $\Omega(\log_2 n)$\Omega, left parenthesis, log, start base, 2, end base, n, right parenthesis.

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 é $\Omega(1)$\Omega, left parenthesis, 1, right parenthesis, 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 $\Omega$\Omega, $O$O e $\Theta$\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.