A notação assintótica (Omega) é usada na análise de algoritmos para descrever um limite inferior do crescimento de uma função à medida que o tamanho da entrada aumenta. Enquanto a Notação Big O estabelece um limite superior, a notação define o comportamento mínimo, ou seja, ela nos diz que o tempo de execução de um algoritmo não será menor do que uma certa taxa de crescimento (crescimento mínimo).
Para uma função , o conjunto de funções é definido como:
Isso significa que, após um determinado valor , a função sempre cresce pelo menos tão rápido quanto , multiplicada por uma constante . Ou seja, serve como um limite inferior assintótico para o crescimento de .
A notação nos informa o crescimento mínimo de uma função. Se , então, para entradas suficientemente grandes, a função cresce pelo menos tão rápido quanto , a partir de algum valor .