Um exercício interessante para o consumo de tempo médio do Quicksort (slide 120) sería:
Dada a recorrência T( n ) = T(an) + T(bn) + n, com T(1) =1, 0<a,b<1, onde a+b=1. Mostrar que T( n ) = O(n lg n).
Um resultado bem conhecido é para a=b=1/2.
É verdade. É um bom exercício.
Veja CLRS 7.2-5, p.153.
Outro exercício interessante: mostrar que
Quicksort é Omega(n lg n). O exercício
confirma a intuição de que o melhor caso
ocorre quando Particione divide o vetor
A[p..r] sempre meio-a-meio. (O exercício
parece menos trivial do que eu supunha.)
Veja CLRS 7.2-5, p.153.
Outro exercício interessante: mostrar que
Quicksort é Omega(n lg n). O exercício
confirma a intuição de que o melhor caso
ocorre quando Particione divide o vetor
A[p..r] sempre meio-a-meio. (O exercício
parece menos trivial do que eu supunha.)