Algoritmos de ordena��o por compara��o podem ser representados por �rvores bin�rias de decis�o, em que cada n� interno da �rvore corresponde a uma compara��o entre dois elementos e cada folha corresponde a uma poss�vel ordena��o (permuta��o) dos elementos.

A altura desta �rvore, ou seja, o caminho mais longo da ra�z at� uma folha corresponde a um limitante inferior para a complexidade de tempo de pior caso do algoritmo.

Agora vamos usar esta representa��o em �rvore para obter um limitante inferior para a complexidade de tempo de qualquer algoritmo de ordena��o baseado apenas em compara��es de elementos. 



A ideia � a seguinte:

 - dado um vetor com n elementos, existem n! poss�veis permuta��es que correspondem � vers�o ordenada deste vetor.
 
    - isso porque na vers�o ordenada qualquer um dos n elementos pode ser o primeiro, qualquer dos n-1 restantes pode ser o segundo, e assim por diante.
 
 - como a princ�pio n�o sabemos qual destas permuta��es � a correta, todas elas tem que aparecer como folhas na �rvore de decis�o bin�ria correspondente ao algoritmo gen�rico sendo analisado.
 
    - caso contr�rio nosso algoritmo daria a resposta errada caso se deparasse com essa entrada, ou seja, ele devolveria uma outra sequ�ncia que n�o estaria em ordem.
 
 - isso quer dizer que nossa �rvore tem n! folhas.
 
 - Agora queremos relacionar o n�mero de folhas que uma �rvore bin�ria pode ter com sua altura h, j� que esta � um limitante inferior para a complexidade do algoritmo em quest�o.
 
 - Sabemos que, por melhor balanceada que seja uma �rvore bin�ria, ela pode ter no m�ximo 2^h folhas, com h come�ando em 0.
 
    - D� pra provar isso por indu��o:
	
       - Caso base: h = 0 temos #(folhas �rvore de altura 0) = 1 = 2^0
	   
	   - Hip�tese de Indu��o (H.I.): para h' < h temos (#folhas �rvore de altura h') = 2^h'
	   
	   - Passo: Dada uma �rvore completa de altura h, temos que tanto a sub�rvore esquerda quanto a sub�rvore direita s�o �rvores de altura h-1. Pela hip�tese de indu��o, cada uma tem #folhas = 2^(h-1). Somando as folhas das duas sub�rvores temos que a �rvore completa tem #folhas = 2*2^h-1 = 2^h.
 
 - Resolvendo a inequa��o:
 
	# folhas da �rvore = 2^h >= # permuta��es da sequ�ncia que estamos ordenando = n!
	2^h >= n!
	
 - note que 
 
	n! = n * (n-1) * (n-2) * ... * (n/2 + 1) * (n/2) * (n/2 - 1) * ... * 2 * 1
	   >= n/2 * n/2 * n/2 * ... * n/2 (n/2 repeti��es de n/2)
	   = (n/2)^(n/2)

 - portanto
 
	2^h >= n!
	    >= (n/2)^(n/2)
		
 - aplicando lg dos dois lados
 
	h >= (n/2) lg (n/2) = Omega(n log n)
	
Assim, chegamos ao resultado de que qualquer algoritmo de ordena��o por compara��o precisa realizar pelo menos da ordem de n log n compara��es para ordenar uma sequ�ncia com n elementos.

Resumindo a ideia da demonstra��o, temos que a �rvore de decis�o de qualquer algoritmo precisa ter n! folhas e, para tanto, sua altura precisa ser pelo menos Omega(n log n).