A notação assintótica (Theta) é usada para descrever o comportamento de crescimento exato de uma função quando o tamanho da entrada se torna grande. Enquanto as Notação Big O e Notação Omega descrevem limites superior e inferior, respectivamente, a notação captura o crescimento preciso, fornecendo tanto um limite superior quanto um inferior ao mesmo tempo.
Para uma função , o conjunto de funções é definido como:
Ou seja, existe um intervalo de crescimento delimitado por e para valores de maiores ou iguais a , o que significa que está preso entre essas duas funções.
A notação indica que a função cresce exatamente como para valores suficientemente grandes de . Isso implica que, além de estar dentro de um limite superior definido por , também possui um limite inferior definido por . Logo, se um algoritmo tem um tempo de execução , ele possui tanto o melhor quanto o pior caso com crescimento similar a .