O-Notation: Warum ist O(n log n) so viel besser als O(n²) – und wie lese ich das aus Code ab?

Die O-Notation beschreibt nicht, wie schnell ein Programm ist, sondern wie die Laufzeit wächst, wenn die Eingabe größer wird. Deshalb fallen Konstanten weg: Ob eine Schleife 3 oder 5 Befehle pro Durchlauf hat, ändert am Wachstum nichts.

Warum das auch bei schnellen Computern zählt – Beispiel mit n = 1.000.000 Datensätzen und grob 10⁹ einfachen Operationen pro Sekunde:

• O(n log n): 1.000.000 · ca. 20 = 20 Millionen Schritte → etwa 0,02 Sekunden
• O(n²): 10¹² Schritte → rund 1.000 Sekunden, also über eine Viertelstunde

Und verdoppelst du n, wird O(n²) viermal so langsam, O(n log n) nur gut doppelt so langsam. Ein schnellerer Rechner verschiebt das Problem nur, das Wachstum bleibt.

Das System zum Ablesen:

1. Einzelne Anweisungen ohne Schleife: O(1).
2. Hintereinander stehende Teile: addieren, der größte Term gewinnt. O(n) + O(n²) = O(n²).
3. Verschachtelte Schleifen: multiplizieren. Äußere läuft n-mal, innere n-mal → O(n²).
4. Schleife, die den Bereich jedes Mal halbiert (z. B. i = i / 2 oder binäre Suche): O(log n). Frage dich: Wie oft kann ich n halbieren, bis 1 übrig ist? Genau log₂ n mal – bei einer Million sind das nur ca. 20.
5. Funktionsaufrufe nicht als 1 zählen, sondern die Kosten der Funktion einsetzen. Ein contains auf einer Liste in einer Schleife ist schon O(n) · O(n).

Merksatz: Nacheinander → addieren, ineinander → multiplizieren, halbieren → log.

Ein Praxisbeispiel, weil genau das im Job ständig passiert: Dubletten in einer Kundenliste finden.

• Naiv: jeden Eintrag mit jedem anderen vergleichen → zwei verschachtelte Schleifen → O(n²). Mit 500 Testdaten merkt man nichts, mit 2 Millionen Kunden im Produktivsystem läuft der Job über Nacht.
• Sortieren, dann Nachbarn vergleichen: Sortieren kostet O(n log n), der Durchlauf danach O(n) → insgesamt O(n log n).
• Mit Hash-Set: jeden Eintrag einmal nachschlagen/einfügen, im Schnitt O(1) → insgesamt O(n), dafür mehr Speicher.

Das zeigt auch den typischen Trade-off: Zeit gegen Speicher. Und es zeigt, warum die Wahl der Datenstruktur oft wichtiger ist als Mikrooptimierung im Code.

Für die Übung noch ein Hinweis: Achte darauf, ob nach Worst Case oder Durchschnitt gefragt ist. Quicksort ist im Schnitt O(n log n), im schlechtesten Fall aber O(n²). Das wird in Klausuren gern abgefragt.

Guter Thread, ein Punkt fehlt mir noch, weil der in der Praxis und in der Klausur oft untergeht: Die O-Notation beschreibt meistens den Worst Case, und der kann sich stark vom typischen Fall unterscheiden.

• Quicksort liegt im Durchschnitt bei O(n log n), im ungünstigsten Fall aber bei O(n²), zum Beispiel bei ungünstiger Pivot-Wahl auf schon sortierten Daten. Deshalb wählen Implementierungen das Pivot zufällig oder als Median aus mehreren Werten.
• Eine Hashtabelle findet einen Eintrag im Durchschnitt in O(1), bei vielen Kollisionen im schlimmsten Fall aber in O(n).

Wenn in der Aufgabe also nur „Laufzeit von Quicksort?“ steht, lohnt sich ein Satz dazu, welchen Fall man meint: Best, Average oder Worst Case. Das zeigt, dass man die Notation verstanden und nicht nur die Tabelle auswendig gelernt hat.

Um das Ablesen aus Code noch etwas greifbarer zu machen, hier ein kleines Beispiel, wie man an einer Funktion direkt erkennt, welche Klasse vorliegt:

• Zwei verschachtelte Schleifen über dieselbe Liste, z. B. um Duplikate zu finden, indem jedes Element mit jedem anderen verglichen wird → die äußere Schleife läuft n-mal, die innere ebenfalls n-mal, also O(n²). Das erkennt man daran, dass die Laufzahl der inneren Schleife von n abhängt und nicht konstant ist.
• Eine einzelne Schleife über die Liste, bei der pro Element nur ein Hash-Set-Lookup passiert (contains/add), ist O(n), weil der Lookup selbst im Schnitt O(1) kostet.
• Eine Schleife, die vorher sortiert (z. B. über eine Standard-Sortierfunktion) und danach einmal linear durchläuft, landet bei O(n log n), weil sich Sortieren und Durchlauf addieren und der größere Term (n log n) das Ergebnis bestimmt.

Wenn ihr in der Übung unsicher seid, hilft es, jede Schleife einzeln zu zählen und sich zu fragen: „Hängt die Anzahl der Durchläufe von n ab, und wenn ja, wie?“ Bei geschachtelten Schleifen multipliziert sich das, bei aufeinanderfolgenden Blöcken addiert sich das (und der dominante Term gewinnt). Wer das an ein bis zwei eigenen Codebeispielen einmal wirklich durchgezählt hat, tut sich in der Klausur deutlich leichter als beim reinen Auswendiglernen der Tabelle.