Ao responder aessa questão um debate começou nos comentários sobre a complexidade do QuickSort. O que me lembro do meu tempo na universidade é que o QuickSort éO(n^2) no pior dos casos,O(n log(n)) em caso médio eO(n log(n)) (mas com limite mais apertado) na melhor das hipóteses.

O que eu preciso é de uma explicação matemática correta do significado deaverage complexity para explicar claramente o que isso significa para alguém que acredita que a notação big-O pode ser usada apenas para o pior caso.

Lembro-me de que, para definir a complexidade média, você deve considerar a complexidade do algoritmo para todas as entradas possíveis, contar quantos casos normais e degenerativos. Se o número de casos degenerados dividido por n tender para 0 quando n ficar grande, você poderá falar da complexidade média da função geral para casos normais.

Esta definição está correta ou a definição de complexidade média é diferente? E se estiver correto, alguém pode afirmar com mais rigor do que eu?