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 é Ω(f(n)) \Omega(f(n)) , então, para um n n suficientemente grande, ele será ao menos kf(n) k \cdot f(n) para uma constante k k qualquer. Aqui está um exemplo de um tempo de execução igual a Ω(f(n)) \Omega(f(n)) :
Dizemos que tal tempo de execução é "Ω de f(n) 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 Θ(f(n)) \Theta(f(n)) automaticamente implica em O(f(n)) O(f(n)) , isso também automaticamente implica em Ω(f(n)) \Omega(f(n)) . Então, podemos dizer que o pior tempo de execução possível da busca binária é Ω(lgn) \Omega(\lg n) . Também podemos fazer afirmações corretas, mas imprecisas, usando a notação Ω. Por exemplo, se você tivesse de verdade um milhão de reais em sua carteira, você pode dizer sem mentir "Eu tenho uma quantidade de dinheiro em minha carteira, e ela é ao menos 10 reais", você também pode dizer que o pior caso no tempo de execução da busca binária é Ω(1) \Omega(1) , porque ela leva no mínimo um tempo constante.

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.
Carregando