Im Video "Untere Schranke" wird gezeigt, dass die Worst-Case-Komplexität vergleichsbasierter Sortierverfahren mindestens $\Theta(n \cdot log(n))$ beträgt.

Leiten Sie die Mindest-Komplexität für das Problem Top-k-Sortierung (siehe letztes Übungsblatt) her, indem Sie den Beweis leicht abändern.

Hinweise:

•  Es gibt $n \cdot (n-1) \cdot ... \cdot (n-k+1)$ Möglichkeiten, um aus $n$ Zahlen die $k$ kleinsten in Reihung zu bringen.
• Sie können annehmen, dass $k$ sehr viel kleiner ist als $n$.