Ho preparato un PDF con la dimostrazione del lower bound per algoritmi di ordinamento. Può contenere ancora qualche svista ma dovrebbe essere piuttosto corretto e fornire, a chi vuole, una dimostrazione semplificata del perché non può esistere un algoritmo di ordinamento con complessità inferiore a O(n log(n)).
-
Ema90
