¿Cuál es el significado de la teoría de la complejidad del caso promedio?

Es posible que esta respuesta no sea formal, pero le brinda una perspectiva orientada a los negocios.

Tengo un algoritmo de reconocimiento facial y quiero crear un servicio para que terceros lo usen. ¿Alguien lo va a usar?

Inversor: ¿cuánto tiempo lleva realizar el reconocimiento una vez que cargo mi foto?

Usted: su peor caso es O (n ^ 3), por lo que diría que como máximo 3 minutos para una imagen de 1 MB (inventé los números pero usted obtiene la imagen)

Inversor: ¡Olvídalo!

Usted: pero espere, espere, en promedio la complejidad es O (nlogn), por lo que diría que toma alrededor de 5 segundos para aproximadamente el 97% de los casos.

Inversor: hablemos de eso.

Muchas empresas se basan en lo que es probable que suceda (piense en los seguros) y un caso promedio es más o menos lo que es probable que suceda, si su promedio tiene poca variación.