É 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.)
Fórum