O que é notação Big Omega?

Semelhante à notação big O, a função big Omega (Ω) é usada na ciência da computação para descrever o desempenho ou a complexidade de um algoritmo.

Se o tempo de execução é Ω (f (n)), então para n grande o suficiente, o tempo de execução é pelo menos k⋅f (n) para alguma constante k. Veja como pensar em um tempo de execução que é Ω (f (n)):

função big-omega

Dizemos que o tempo de execução é “grande-Ω de f (n)”. Usamos a notação big-Ω para limites inferiores assintóticos , pois ela limita o crescimento do tempo de execução a partir de baixo para tamanhos de entrada grandes o suficiente.

Diferença entre Big O e Big Ω

A diferença entre a notação Big O e a notação Big Ω é que Big O é usado para descrever o pior caso de tempo de execução de um algoritmo. Mas, a notação Big Ω, por outro lado, é usada para descrever o melhor caso de tempo de execução para um determinado algoritmo.

Mais Informações:

  • Notação Big-Ω (Big-Omega)
MYCODSCHOOL Análise de complexidade de tempo