Ordinamento lineare

Ipotizzando che ogni elemento da ordinare è distinto, è possibile dimostrare che gli algoritmi a confronto sono sempre $\Omega (n\log n)$, infatti dato l'albero dei confronti $i:j$ di un array $(a_1,a_2,a_3)$

ci interessa l'altezza che corrisponde al numero di confronti e quindi al tempo di esecuzione.

Le foglie, per un input largo $n$, sono quindi: $$n!\le f\le 2^h$$ dato che ci sono al minimo $n!$ permutazioni di $a_1,...,a_n$, e al massimo $2^h$ perchè alcuni algoritmi possono ripetere alcuni confronti, e perchè un albero alto $h$ ha al più $2^h$ foglie:

• Caso base per $h=0$, ci sono $f=1\le 2^0$ foglie
• Passo induttivo assumendo che $f_{T_i}\le 2^k,\forall k<h$, allora: $$f=f_{T_1}+f_{T_2}\le 2^{h_1}+2^{h_2}\le 2^{\max (h_1,h_2)}+2^{\max (h_1,h_2)}=2^{1+\max (h_1,h_2)}=2^h$$ dove $T_1$ e $T_2$ sono i sottoalberi figli.

Di conseguenza, si ha che: $$\begin{gathered} n!\le 2^h\iff 2^{{\log }_{2}n!}\le 2^h \\ \Updownarrow \\ h\ge {\log }_{2}n!\ge {\log }_2{\left(\frac{n}{e}\right)}^n=n({\log }_{2}n-{\log }_{2}e)=\Omega (n\log n) \end{gathered}$$ sapendo che $n!\approx \sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n(1+\Theta (\frac{1}{n}))$ e che per $n\to \infty$ il termine ${\left(\frac{n}{e}\right)}^n$ domina.

Per ottenere prestazioni migliori quindi, sarà necessario evitare la tecnica del confronto.