Limite Inferior

Ordenações através de comparações podem ser vistas abstratamente em termos de árvores de decisão.Uma arvore de decisão representa as comparações realizadas pelo algoritmo de ordenação quando ele trabalha em uma entrada de um dado tamanho.

O tamanho do caminho mais longo partindo da raíz de uma árvore de decisão para qualquer um de suas folhas representa o pior-caso no número de comparações que um algoritmo de ordenação realiza. Conseqüentemente, o pior-caso no número de comprarações para uma ordenação por comparação corresponde à altura da sua árvore de decisão.

Assim, achar o limite inferior para a altura de uma árvore de decisão equivale a achar o limite inferior para o tempo de execução de qualquer algoritmo de ordenação por comparação.

Considere a arvore de decisão de altua que ordena elementos. Como existem permutações dos elementos, cada permutação representa uma ordem de ordenação distinta, a árvore tem que ter pelo menos folhas. Já que uma árvore binária de altura tem não maus do que folhas, temos:

$$n!\leq 2^{h}$$

que, através do uso de logaritmos, fica

$$h\geq \lg \left( n!\right)$$

, já que a função é monotonicamente crescente. Usand as aproximação de Stirling, temos:

$$n!\geq \left( \frac{n}{e}\right) ^{n}$$

onde é a base dos logaritmos naturais; assim:

$$\begin{eqnarray*} h & \geq & \lg \left( \frac{n}{e}\right) ^{n}\\ & = & n\lg n-n\lg e\\ & = & \Omega \left( n\lg \right) \end{eqnarray*}$$

-

[2,1]