oje eu estava lendo um ótimo artigo de Julienne Walker sobre classificação -Eternally Confuzzled - A arte de classificar e uma coisa chamou minha atenção. Não entendo bem a parte em que o autor prova que, para classificar por comparação, estamos limitados por Ω N·registroN) limite inferior

Limites mais baixos não são tão óbvios. O limite mais baixo possível para a maioria dos algoritmos de classificação é Ω N·registroN). Isso ocorre porque a maioria dos algoritmos de classificação usa comparações de itens para determinar a ordem relativa dos itens. Qualquer algoritmo que classifique por comparação terá um limite mínimo mínimo de Ω N·registroN) porque uma árvore de comparação é usada para selecionar uma permutação que é classificada. Uma árvore de comparação para os três números 1, 2 e 3 pode ser facilmente construída:

                         1 < 2

           1 < 3                       1 < 3

   2 < 3           3,1,2       2,1,3           2 < 3

1,2,3   1,3,2                            2,3,1     3,2,1

Observe como cada item é comparado com todos os outros itens e que cada caminho resulta em uma permutação válida dos três itens. A altura da árvore determina o limite inferior do algoritmo de classificação. Como deve haver tantas folhas quanto permutações para que o algoritmo esteja correto, a menor altura possível da árvore de comparação é logN !,qual é equivalente a Ω N·registroN).

Parece ser bastante razoável até a última parte (em negrito), que eu não entendo direito - como logN! é equivalente a Ω N·registroN). Devo sentir falta de algo nos meus cursos do CopmSci e não consigo a última transição. Estou ansioso por obter ajuda com isso ou algum link para outras evidências de que estamos limitados Ω N·registroN) se usarmos a classificação por comparação.