Die O-Notation entstand 1894 beim deutschen Mathematiker Paul Bachmann, wurde von Edmund Landau popularisiert und in den 1970er Jahren von Donald Knuth in die Informatik importiert. Sie fängt eine der nützlichsten Intuitionen der Algorithmenanalyse ein: was zählt, ist nicht, wie schnell ein Programm bei einer gegebenen Eingabe läuft, sondern wie seine Laufzeit wächst, wenn die Eingabe wächst. Eine O(n²)-Sortierung ist katastrophal langsamer als eine O(n log n)-Sortierung bei einer Million Elementen, ungeachtet dessen, welche bei zehn Elementen schneller ist. Der Aufwand verbirgt sich in der Form der Kurve, nicht im Vorfaktor.
Die O-Notation klassifiziert Algorithmen nach ihrer asymptotischen Wachstumsrate: O(1) konstant, O(log n) logarithmisch, O(n) linear, O(n log n) linear-logarithmisch, O(n²) quadratisch, O(2ⁿ) exponentiell. Die Notation verwirft bewusst konstante Faktoren und Terme niedrigerer Ordnung — sie fragt, wie der Algorithmus skaliert, wenn die Eingaben groß werden. Genau dies braucht es, um die Leistung auf realen Lasten vorherzusagen, wo Eingabegrößen routinemäßig über viele Größenordnungen schwanken. Die Disziplin schult einen eigenen algorithmischen Geschmack: Darstellungen zu suchen, die logarithmische statt linearer Suche erlauben; verschachtelte Schleifen zu meiden, die quadratische Zeit erzeugen; wo möglich auf Hashing zurückzugreifen, um O(n)-Lookups auf amortisierte O(1) zu drücken; zu erkennen, wann ein Problem im Kern NP-schwer ist und exakte Lösungen schlicht nicht skalieren werden. Die von O ignorierten Konstanten sind in der Praxis nicht immer vernachlässigbar — Cache-Effekte, Speicherhierarchie, Sprungvorhersage und Parallelisierung können die absolute Leistung um Größenordnungen verschieben —, doch die asymptotische Gestalt bleibt fast immer der richtige Ausgangspunkt, wenn man bedenken will, welcher Ansatz tragen wird, sobald die Daten wachsen.
Die O-Notation wird in jedem Algorithmenkurs als Erstes gelehrt, in jedem technischen Vorstellungsgespräch als Erstes gefragt und von Programmierern, die den Muskel nicht trainieren, als Erstes vergessen. Die gegenwärtigen Skalierungsdebatten — über das Training großer Sprachmodelle, über Graphenalgorithmen in sozialen Netzwerken, über kryptographische Primitive in einer Post-Quanten-Welt, über die Energiekosten des Rechnens — laufen sämtlich mit O-Notation-Argumenten, mal explizit, mal implizit. Die schlichte Übung, in Wachstumsraten zu denken, gehört zu den dauerhaftesten geistigen Aufrüstungen, die eine Karriere in der Softwareentwicklung schenkt.