Estaba mirando alrededor de stackoverflowEvaluación perezosa no trivial, lo que me llevó a la presentación de Keegan McAllister:Porque aprender haskell. En la diapositiva 8, muestra la función mínima, definida como:

minimum = head . sort

y afirma que su complejidad es O (n). No entiendo por qué se dice que la complejidad es lineal si la clasificación por reemplazo es O (nlog n). La clasificación referida en la publicación no puede ser lineal, ya que no asume nada acerca de los datos, ya que sería requerida por los métodos de clasificación lineal, como la clasificación por conteo.

¿Está la evaluación perezosa jugando un papel misterioso aquí? Si es así, ¿cuál es la explicación detrás de esto?