Qual é a explicação simples para O(n log n)?

Se algo leva tempo proporcional ao log n isto significa que se você tem n coisas você pode fazer o que quer que seja que você deseja fazer em tempo proporcional não ao número n, mas proporcional ao número de dígitos em n. Normalmente quando falamos de algoritmos usamos base dois em vez de base 10, então queremos dizer que o tempo é proporcional ao número de dígitos na representação binária de n. Mas como todos os logs estão relacionados entre si por uma constante a proporcionalidade se manteria independentemente da base.

Agora pense num número binário. Como você decidiria que número era proporcional ao log n. Você teria que basicamente a cada passo decidir qual era um novo dígito naquele número. Cada vez que você decide se um dígito é 1 ou 0 você divide o seu número de valores possíveis para n em 2.

A maioria dos problemas envolvendo n coisas são pelo menos O(n) porque se fosse menos que isso você poderia resolver o seu problema sem sequer olhar para todas n coisas. O(n log n) significa que para cada coisa você tem que fazer um trabalho extra proporcional ao número de dígitos na contagem que descreve o que você está olhando. Não muito, porque normalmente o número de dígitos de um número é muito menor que o valor desse número, mas ainda assim alguns. E isso significa que um n fica cada vez maior que a quantidade extra de trabalho também fica maior por item em n.