Øv med flashcards — Sortering i lineær tid og utvalg

Et beslutningstre for en sammenligningssortering har minst $n!$ løv, og et binærtre med $n!$ løv har høyde minst $\lg (n!)=\Theta (n\lg n)$.