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 n3,
  7. exponencial se consome tempo proporcional a cn, sendo c uma constante (como 2, por exemplo).

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