Komplexität von Problemen

Wie schwer ist ein (algorithmisches) Problem?

Wieviel Ressourcen braucht jeder Algorithmus, der das Problem löst?

(Bereits gezeigt) Für jedes Sortierververfahren für $n$ Elemente gibt es eine Eingabe, für die das Verfahren $\ge \log_2 (n!)$ Vergleiche ausführt.

Übung: $\log_2(n!) \approx n \log n$

Folgerung: Sortieren hat eine Komplexität von wenigstens $n \log n$. (D. h. mehr als linear.)

Folgerung: Merge-Sort ist optimal (Bubble-Sort nicht).