Wie Kosten wachsen

Big O misst, wie Kosten wachsen, wenn die Eingabe wächst. Nicht der konstante Faktor — die Rate. Zwei Algorithmen, die bei N=100 beide „ein paar Millisekunden“ brauchen, können sich bei N=10.000 um den Faktor 10.000 unterscheiden, wenn einer in O(N)-Zeit und der andere in O(N²)-Zeit läuft.

Die gängigen Komplexitätsklassen

O(1) — Konstant. Gleiche Kosten unabhängig von N. Beispiele: Hash-Tabellen-Zugriff über Schlüssel, Array-Zugriff über Index, Stack-Push/Pop. Verdoppelt man N, ändert sich nichts.

O(log N) — Logarithmisch. Jeder Schritt halbiert die verbleibende Arbeit. Beispiele: binäre Suche in einem sortierten Array, BVH-Raumabfrage in einer Game-Engine, Operationen auf einem balancierten Binärbaum. Bei N=1.000.000: log₂(1.000.000) ≈ 20 Schritte.

O(N) — Linear. Der Aufwand wächst mit der Eingabe. Beispiele: linearer Scan einer Liste, Lesen einer Datei, Zählen von Elementen in einer Sammlung. Bei N=10.000: 10.000 Operationen.

O(N log N) — Linearithmisch. Fast linear, etwas schlechter. Beispiele: Merge-Sort, effiziente Algorithmen für kürzeste Wege (Dijkstra mit Heap). Bei N=10.000: ca. 133.000 Operationen.

O(N²) — Quadratisch. Der Aufwand explodiert. Beispiele: list.contains() innerhalb einer Schleife über dieselbe Liste, Bubble-Sort, naive paarweise Vergleiche. Bei N=1.000: 1.000.000 Operationen. Bei N=10.000: 100.000.000 Operationen.

O(2^N) — Exponentiell. Bei jeder sinnvollen Skala unbrauchbar. Beispiele: Brute-Force-Kombinatorik, alle Teilmengen finden. Bei N=30: über 1.000.000.000 Operationen.

Die Skala, die es sichtbar macht

N=10 Vergleiche:
O(N):   10
O(N²):  100
Verhältnis:  10x

N=1.000 Vergleiche:
O(N):   1.000
O(N²):  1.000.000
Verhältnis:  1.000x

N=10.000 Vergleiche:
O(N):   10.000
O(N²):  100.000.000
Verhältnis:  10.000x

Bei N=10 ist der Unterschied kaum spürbar. Bei N=10.000 läuft der O(N²)-Algorithmus 10.000-mal langsamer. Deshalb blieb MOAD-0001 jahrzehntelang unsichtbar: Die Graphen, auf denen er 1993 lief, hatten 50 Knoten. Bis 2020 lief derselbe Code auf Abhängigkeitsgraphen mit 50.000 Knoten.

Drei Operationen klassifizieren

Wende die Komplexitätsklassen auf konkrete Operationen an. Die zentrale Frage bei jeder: Wie viele Operationen sind nötig, wenn N wächst?

Korrekter Code, falsche Wachstumskurve

Korrekter Code, der in O(N²)-Zeit läuft, liefert identische Ergebnisse wie O(N)-Code. Die Tests bestehen. Die Ausgabe stimmt überein. Es wird keine Ausnahme ausgelöst. Der Fehler verbirgt sich in der Wachstumskurve.

Diese Eigenschaft macht O(N²)-Fehler sedimentär: sie versteinern in funktionierendem Code und werden erst sichtbar, wenn N eine Schwelle überschreitet. Der Code hat sich nicht geändert. Die Welt um ihn herum hat sich geändert.

MOAD-0001: Der sedimentäre Fehler

Das am weitesten verbreitete Beispiel: visited = [] innerhalb einer Schleife zur Graph-Traversierung.

visited = []
for node in graph:
if node not in visited:  # O(N)-Scan bei jedem Aufruf
visited.append(node)
process(node)

Jeder not in visited-Aufruf scannt 0 bis len(visited)-1 Elemente. N Aufrufe × N/2 durchschnittlich gescannte Elemente = O(N²) insgesamt. Die Lösung: eine Zeile.

visited = set()  # O(1) Mitgliedschaftstest
for node in graph:
if node not in visited:  # O(1) Hash-Lookup
visited.add(node)
process(node)

Gleiches Verhalten. Gleiche Ausgabe. Gleiche Tests bestanden. Die Wachstumsrate ändert sich von O(N²) zu O(N). Bei N=1.000: 1.000× schneller. Bei N=10.000: 10.000× schneller.

Warum Hammings Ära dies verursacht hat

In frühem Java & C war ArrayList (dynamisches Array) der Standard für sequenzielle Container. Sets existierten, waren aber nicht idiomatisch – Entwickler griffen auf das Vertraute zurück. Eine Graph-Traversierung von 1993 mit N=50 lief in Mikrosekunden mit visited = []. Dieser Code landete in der Versionskontrolle, wurde kopiert, in Bibliotheken eingebaut und über Paketmanager ausgeliefert. Bis 2020 lief dasselbe Muster auf Abhängigkeitsgraphen mit 50.000 Knoten.

Der Code war 1993 korrekt. Er wurde teuer, als sich die Welt um ihn herum veränderte. Hammings Ära hat diese Art von Defekt verursacht, indem sie die Frage nach der Wachstumsrate nie benannt hat.

Diagnose & Fix

Wende die Diagnose an: finde das O(N²)-Muster und identifiziere die Lösung.

Welche Namensänderungen

Bevor Big O einen Namen hatte, bemerkten Programmierer: „Das läuft langsam.“ Sie haben profitiert. Sie haben umgeschrieben. Aber sie konnten das Muster nicht lehren — sie konnten nur auf Instanzen zeigen. Ein Muster ohne Namen kann sich nicht verbreiten.

Nachdem Big O einen Namen hatte, konnte ein Senior Engineer sagen: „Das ist O(N²), ersetzen Sie es durch ein Set“ und ein Junior Engineer konnte das Muster verstehen, anwenden und seinerseits weitergeben. Der Name machte das Muster zu einer übertragbaren Wissenseinheit.

Hamming kannte diese Dynamik in anderen Bereichen. Er beschrieb, wie die Benennung von „Spaghetti-Code“ in den 1960er Jahren der Community ermöglichte, eine Klasse von Defekten zu erkennen, zu diskutieren und schließlich auszumerzen, die jeder erlebt, aber niemand benannt hatte. Derselbe Mechanismus gilt für Komplexitätsklassen.

Unhamming ergänzt den Wortschatz, den Hamming ausgelassen hat: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N). Diese Namen ermöglichen es Ihnen, die Wachstumskurve im gelesenen Code zu erkennen, die Leistung bei Skalierung vorherzusagen und Korrekturen präzise zu kommunizieren. Sie erfüllen Hammings eigenen Test für ein Fundament: dauerhaft und generativ für den Großteil des restlichen Feldes. [TITLE who_coined_big_o/]

Von der Zahlentheorie zur Informatik

Die Big-O-Notation stammt nicht aus der Informatik. Sie entstand in der reinen Mathematik – genauer gesagt in der Zahlentheorie – 74 Jahre bevor Donald Knuth sie für Algorithmen übernahm.

Paul Bachmann, 1894

Paul Bachmann, ein deutscher Mathematiker, führte die O-Notation in seinem Buch Die Analytische Zahlentheorie von 1894 ein. Er benötigte eine kompakte Möglichkeit, auszudrücken, dass eine Größe nicht schneller als eine andere wächst, bis auf einen konstanten Faktor. Die Schreibweise „f(n) = O(g(n))“ bedeutete: f wächst höchstens so schnell wie g. Dies ermöglichte es Zahlentheoretikern, über Fehlerterme in Approximationen zu argumentieren, ohne exakte Konstanten verfolgen zu müssen.

Bachmann dachte nicht an Schleifen, Datenstrukturen oder Laufzeiten. Er beschäftigte sich mit der Verteilung von Primzahlen – insbesondere mit den Fehlertermen im Primzahlsatz.

Edmund Landau, 1909

Edmund Landau, ebenfalls ein deutscher Mathematiker, popularisierte die Notation in seinem Handbuch der Lehre von der Verteilung der Primzahlen von 1909. Landau führte auch die verwandte Notation o (klein-o) ein und verwendete die Familie der asymptotischen Symbole so häufig, dass sie als Bachmann-Landau-Notation oder einfach Landau-Notation bekannt wurde.

Sechs Jahrzehnte lang existierte die O-Notation ausschließlich in der Mathematik. Kein Programmierer dachte daran.

Donald Knuth, 1968 & 1976

Donald Knuth übertrug die Notation in die Informatik. In The Art of Computer Programming (Bd. 1, 1968) verwendete Knuth die O-Notation zur Beschreibung der Laufzeit von Algorithmen — eine direkte Übertragung von Bachmanns Werkzeug in ein neues Gebiet. Er war der Erste, der sie systematisch in der Algorithmusanalyse einsetzte.

1976 veröffentlichte Knuth einen kurzen Artikel in SIGACT News mit dem Titel „Big Omicron and Big Omega and Big Theta“. Er führte Omega (Ω) für untere Schranken und Theta (Θ) für enge Schranken ein und vervollständigte damit den heute in der Informatik verwendeten Dreier-Symbolwortschatz. Er plädierte außerdem für eine Standardisierung dieser Symbole in der Fachwelt — ein bewusster Standardisierungsakt, der die Verbreitung beschleunigte.

In den frühen 1980er Jahren erschien Big O in jedem Algorithmen-Lehrbuch. In den 1990er Jahren wurde es zum Standardvokabular in Vorstellungsgesprächen.

Eine 74-jährige Reise

1894 — Bachmann führt O in der Zahlentheorie ein
1909 — Landau popularisiert O, o und die gesamte Notationsfamilie
1953 — Hamming beginnt seine Forschung bei Bell Labs (lernt Big O nie als CS-Werkzeug kennen)
1968 — Knuth wendet O auf die Algorithmusanalyse in TAOCP Vol. 1 an
1976 — Knuth führt Omega und Theta ein; plädiert für Standardisierung
1980er — Big O gelangt in alle CS-Lehrpläne
1993 — MOAD-0001-Sedimentschicht bildet sich im Produktionscode
1995 — Hamming unterrichtet die letzte Version seines Kurses; behandelt Big O nie
2026 — MOAD-0001 in über 1.000 Open-Source-Projekten gefunden

Bachmanns Werk verbrachte 74 Jahre in der reinen Mathematik – sichtbar für jeden Mathematiker, unsichtbar für jeden Programmierer. Knuth erkannte das Potenzial der Übertragung. Hamming – in derselben Zeit tätig und mit derselben Computing-Community zusammenarbeitend – nahm sie nie in seinen Kurs auf.

Warum Knuths Standardisierung wichtig war

Knuths Paper von 1976 tat mehr, als nur Omega und Theta einzuführen. Es argumentierte, dass das Fachgebiet eine einheitliche Notation brauche und dass inkonsistente Notation aktiv schädlich sei. Verschiedene Lehrbücher verwendeten O für unterschiedliche Bedeutungen – manchmal als obere Schranke, manchmal als Approximation, manchmal ohne Angabe, ob Konstanten eine Rolle spielen. Knuth räumte das auf.

Dies ist Hammings Musterbenennungs-Dynamik, angewandt auf die Notation selbst. Vor Knuths Standardisierung konnten Ingenieure Komplexitätsaussagen nicht präzise über Lehrbücher, Papers oder Teams hinweg kommunizieren. Nach der Standardisierung trug „this runs in O(N log N)“ unabhängig vom Sprecher genau eine Bedeutung.

Knuth lieferte auch die informelle Übersetzung: „O(f(n)) bedeutet, dass die Laufzeit höchstens ein konstantes Vielfaches von f(n) beträgt, für alle hinreichend großen n.“ Diese Interpretation – obere Schranke, bis auf einen konstanten Faktor, für große Eingaben – wurde zur Standardintuition, die jeder Programmierer lernt.