Hoe Kosten Groeien

Big O meet hoe kosten groeien naarmate de invoer groeit. Niet de constante factor — de snelheid. Twee algoritmen die beide in 'een paar milliseconden' draaien bij N=100 kunnen bij N=10.000 met een factor 10.000 uiteenlopen, als de ene in O(N)-tijd draait en de andere in O(N²).

De Gangbare Complexiteitsklassen

O(1) — Constant. Dezelfde kosten ongeacht N. Voorbeelden: hashtabel-opzoeking op sleutel, array-toegang op index, stack push/pop. N verdubbelen verandert niets.

O(log N) — Logaritmisch. Elke stap halveert het resterende werk. Voorbeelden: binaire zoekopdracht in een gesorteerde array, BVH-ruimtelijke query in een game-engine, bewerkingen op een gebalanceerde binaire boom. Bij N=1.000.000: log₂(1.000.000) ≈ 20 stappen.

O(N) — Lineair. De kosten groeien mee met de invoer. Voorbeelden: lineaire scan van een lijst, een bestand lezen, items tellen in een collectie. Bij N=10.000: 10.000 bewerkingen.

O(N log N) — Lineair-logaritmisch. Bijna lineair, iets slechter. Voorbeelden: merge sort, efficiënte kortstepad-algoritmen (Dijkstra met een heap). Bij N=10.000: ~133.000 bewerkingen.

O(N²) — Kwadratisch. De kosten exploderen. Voorbeelden: list.contains() aangeroepen binnen een lus over dezelfde lijst, bubble sort, naïeve all-pairs-vergelijking. Bij N=1.000: 1.000.000 bewerkingen. Bij N=10.000: 100.000.000 bewerkingen.

O(2^N) — Exponentieel. Onbruikbaar op elke betekenisvolle schaal. Voorbeelden: brute-force combinatoriek, alle subsets vinden. Bij N=30: meer dan 1.000.000.000 bewerkingen.

De schaal waarop het zichtbaar wordt

N=10 vergelijkingen:
O(N):   10
O(N²):  100
ratio:  10x

N=1.000 vergelijkingen:
O(N):   1.000
O(N²):  1.000.000
ratio:  1.000x

N=10.000 vergelijkingen:
O(N):   10.000
O(N²):  100.000.000
ratio:  10.000x

Bij N=10 is het verschil nauwelijks merkbaar. Bij N=10.000 draait het O(N²)-algoritme 10.000 keer langzamer. Daarom bleef MOAD-0001 decennialang onzichtbaar: de grafieken waarop het in 1993 draaide, hadden 50 knooppunten. Tegen 2020 draaide dezelfde code op afhankelijkheidsgrafieken met 50.000 knooppunten.

Classificeer drie bewerkingen

Pas de complexiteitsklassen toe op concrete bewerkingen. De kernvraag voor elk: hoeveel bewerkingen kost het als N groeit?

Correcte code, verkeerde groeicurve

Correcte code die in O(N²)-tijd draait, levert identieke resultaten op als O(N)-code. De tests slagen. De uitvoer komt overeen. Er wordt geen uitzondering gegenereerd. Het defect zit verborgen in de groeicurve.

Deze eigenschap maakt O(N²)-defecten sedimentair: ze verkalken binnen werkende code en worden pas zichtbaar wanneer N een drempel overschrijdt. De code is niet veranderd. De wereld eromheen wel.

MOAD-0001: Het sedimentaire defect

De meest voorkomende instantie: visited = [] binnen een graf-doorlooplus.

visited = []
for node in graph:
if node not in visited:  # O(N) scan bij elke aanroep
visited.append(node)
process(node)

Elke not in visited call scant 0 tot len(visited)-1 items. N calls × N/2 gemiddelde gescande items = O(N²) totaal. De oplossing: één regel.

visited = set()  # O(1) membership test
for node in graph:
if node not in visited:  # O(1) hash lookup
visited.add(node)
process(node)

Zelfde gedrag. Zelfde output. Zelfde tests slagen. De groeisnelheid verandert van O(N²) naar O(N). Bij N=1.000: 1.000× sneller. Bij N=10.000: 10.000× sneller.

Waarom Hamming's tijdperk dit heeft gezaaid

In vroeg Java & C was ArrayList (dynamische array) de standaard sequentiële container. Sets bestonden wel, maar waren niet idiomatisch — ontwikkelaars grepen naar wat vertrouwd was. Een grafische doorloop uit 1993 met N=50 liep in microseconden met visited = []. Die code belandde in versiebeheer, werd gekopieerd, werd ingepakt in bibliotheken, werd verspreid via package managers. Tegen 2020 draaide hetzelfde patroon op afhankelijkheidsgrafen met 50.000 knooppunten.

De code was correct in 1993. Hij werd duur toen de wereld eromheen veranderde. Hamming's tijdperk heeft deze klasse van defecten gezaaid door nooit de groeisnelheidsvraag te benoemen.

Diagnose & Oplossing

Pas de diagnose toe: vind het O(N²)-patroon, identificeer de oplossing.

Welke naamgevingswijzigingen

Voordat Big O een naam had, zagen programmeurs 'dit draait langzaam'. Ze profileden. Ze herschreven. Maar ze konden het patroon niet onderwijzen — ze konden alleen naar instanties wijzen. Een patroon zonder naam kan niet verspreid worden.

Nadat Big O een naam had, kon een senior engineer zeggen 'dit is O(N²), vervang het door een set' en kon een junior engineer het patroon begrijpen, toepassen en op zijn beurt onderwijzen. De naam maakte het patroon een overdraagbare eenheid van kennis.

Hamming kende deze dynamiek in andere domeinen. Hij beschreef hoe het benoemen van 'spaghetti code' in de jaren zestig de gemeenschap in staat stelde een klasse van defecten te herkennen, te bespreken en uiteindelijk uit te roeien die iedereen had ervaren maar niemand had benoemd. Hetzelfde mechanisme geldt voor complexiteitsklassen.

Unhamming voegt de woordenschat toe die Hamming wegliet: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N). Deze namen laten je de groeicurve zien in code die je leest, prestaties op schaal voorspellen en fixes precies communiceren. Ze voldoen aan Hammings eigen test voor een fundamenteel: duurzaam en generatief voor het grootste deel van de rest van het veld. [TITLE who_coined_big_o/]

Van getaltheorie naar informatica

Big O-notatie is niet ontstaan in de informatica. Het ontstond in de pure wiskunde — specifiek in de getaltheorie — 74 jaar voordat Donald Knuth het aanpaste voor algoritmen.

Paul Bachmann, 1894

Paul Bachmann, een Duitse wiskundige, introduceerde de O-notatie in zijn boek uit 1894 Die Analytische Zahlentheorie (Analytische getaltheorie). Hij had een compacte manier nodig om uit te drukken dat de ene grootheid niet sneller groeit dan de andere, tot een constante factor. Door 'f(n) = O(g(n))' te schrijven, zei hij: f groeit hooguit even snel als g. Dit stelde getaltheoretici in staat om over fouttermen in benaderingen te redeneren zonder exacte constanten bij te houden.

Bachmann dacht niet aan lussen, datastructuren of uitvoeringstijd. Hij dacht aan hoe priemgetallen verdeeld zijn — specifiek over de fouttermen in de priemgetalstelling.

Edmund Landau, 1909

Edmund Landau, een andere Duitse wiskundige, populariseerde de notatie in zijn Handbuch der Lehre von der Verteilung der Primzahlen (Handboek over de verdeling van priemgetallen) uit 1909. Landau introduceerde ook de verwante notatie o (little-o) en gebruikte de familie van asymptotische symbolen zo uitgebreid dat de familie bekend werd als Bachmann-Landau-notatie of eenvoudigweg Landau-notatie.

Zestig jaar lang leefde de O-notatie volledig in de wiskunde. Geen enkele programmeur dacht eraan.

Donald Knuth, 1968 & 1976

Donald Knuth vertaalde de notatie naar de informatica. In The Art of Computer Programming (Vol. 1, 1968) gebruikte Knuth de O-notatie om de looptijd van algoritmen te beschrijven — een directe overdracht van Bachmanns hulpmiddel naar een nieuw domein. Hij was de eerste die het systematisch toepaste op algoritme-analyse.

In 1976 publiceerde Knuth een kort artikel in SIGACT News getiteld 'Big Omicron and Big Omega and Big Theta.' Hij introduceerde Omega (Ω) voor ondergrenzen en Theta (Θ) voor strakke grenzen, waarmee hij het drievoudige symboolvocabulaire completeerde dat de informatica vandaag gebruikt. Hij pleitte ook voor standaardisatie van het gebruik van deze symbolen binnen het vakgebied — een bewuste standaardisatie die de adoptie versnelde.

Begin jaren tachtig verscheen Big O in elk algoritme-leerboek. In de jaren negentig was het standaard interview-vocabulaire.

Een reis van 74 jaar

1894 — Bachmann introduceert O in de getaltheorie
1909 — Landau populariseert O, o en de volledige notatiefamilie
1953 — Hamming begint onderzoek bij Bell Labs (leert Big O nooit als CS-tool)
1968 — Knuth past O toe op algoritme-analyse in TAOCP Deel 1
1976 — Knuth voegt Omega en Theta toe; pleit voor standaardisatie
1980s — Big O komt in alle CS-curricula
1993 — MOAD-0001 sedimentlaag vormt zich in productiecode
1995 — Hamming geeft de laatste versie van zijn cursus; behandelt Big O nooit
2026 — MOAD-0001 gevonden in 1.000+ open-source projecten

Bachmanns hulpmiddel bleef 74 jaar in de zuivere wiskunde, zichtbaar voor elke wiskundige maar onzichtbaar voor elke programmeur. Knuth zag de transplantatie. Hamming — die in dezelfde periode werkte en samenwerkte met dezelfde computergemeenschap — nam het nooit op in zijn cursus.

Waarom Knuths standaardisatie ertoe deed

Knuths paper uit 1976 deed meer dan alleen Omega en Theta introduceren. Het betoogde dat het vakgebied consistente notatie nodig had, en dat inconsistente notatie actief schadelijk was. Verschillende leerboeken gebruikten O om verschillende dingen te betekenen — soms als bovengrens, soms als benadering, soms zonder te specificeren of constanten ertoe deden. Knuth ruimde dit op.

Dit is Hammings patroon-naamgevingsdynamiek toegepast op notatie zelf. Voordat Knuth de symbolen standaardiseerde, konden engineers complexiteitsclaims niet precies communiceren over leerboeken, papers of teams heen. Na de standaardisatie droeg 'this runs in O(N log N)' exact één betekenis, ongeacht wie het zei.

Knuth leverde ook de informele vertaling: 'O(f(n)) betekent dat de looptijd hooguit een constante maal f(n) is, voor alle voldoende grote n.' Deze interpretatie — bovengrens, tot een constante factor, voor grote invoer — werd de standaardintuïtie die elke programmeur leert.