Average Case Complexity

A quantidade de algum recurso computacional (normalmente tempo) usada por um algoritmo, em média, para um conjunto de entradas de um determinado tamanho.