OliForum Matematico

Il lower-bound si ricava costruendo
un albero binario delle decisioni, e'
un problema abbastanza standard.

Sia S= (x_1, x_2, ..., x_n) la sequenza
da ordinare, l'albero binario T ha come radice
il confronto x_1 \leq x_2 ,
e per figli i vari sottocasi dei possibili confronti.
Le foglie dell'albero ...