Eu estava procurando por stackoverflowAvaliação Preguiçosa Não Trivial, o que me levou à apresentação de Keegan McAllister:Por que aprender Haskell. No slide 8, ele mostra a função mínima, definida como:

minimum = head . sort

e afirma que sua complexidade é O (n). Eu não entendo porque a complexidade é considerada linear se a ordenação por substituição for O (nlog n). A classificação referida no post não pode ser linear, pois ela não assume nada sobre os dados, como seria exigido pelos métodos de classificação linear, como a contagem de classificação.

A avaliação preguiçosa está desempenhando um papel misterioso aqui? Se sim, qual é a explicação por trás disso?