Mientras contesta aesta pregunta Se inició un debate en los comentarios sobre la complejidad de QuickSort. Lo que recuerdo de mi época universitaria es que QuickSort esO(n^2) en el peor caso,O(n log(n)) en caso promedio yO(n log(n)) (pero con un límite más estricto) en el mejor de los casos.

Lo que necesito es una explicación matemática correcta del significado deaverage complexity para explicar claramente de qué se trata a alguien que cree que la notación big-O solo puede usarse para el peor de los casos.

Lo que recuerdo es que, para definir la complejidad promedio, debe considerar la complejidad del algoritmo para todas las entradas posibles, contar cuántos casos degenerativos y normales. Si el número de casos degenerados dividido por n tiende hacia 0 cuando n aumenta, entonces puede hablar de la complejidad promedio de la función general para casos normales.

¿Es correcta esta definición o es diferente la definición de complejidad promedio? Y si es correcto, ¿alguien puede decirlo más rigurosamente que yo?