Constante, linear, linearítmico, quadrático, etc.

As definições a seguir referem-se ao consumo de tempo (ou seja, ao tempo de resposta) de algoritmos.  Em todas as definições,  n  é o tamanho de uma instância do problema que o algoritmo resolve.  No caso de algoritmos para grafos, n é usualmente o tamanho do grafo.

Um algoritmo é

1. constante se o consumo tempo não depende de n,
2. logarítmico se consome tempo proporcional a log n,
3. linear se consome tempo proporcional a n,
4. linearítmico (ou ene-log-ene) se consome tempo proporcional a n log n,
5. quadrático se consome tempo proporcional a n²,
6. cúbico se consome tempo proporcional a n³,
7. exponencial se consome tempo proporcional a cⁿ, sendo c uma constante (como 2, por exemplo).

Esses termos referem-se, em geral, ao consumo de tempo no pior caso.