Vergelijk de klassen
Leerdoel: je ziet alle vier complexiteitsklassen tegelijk in
één grafiek, en begrijpt waarom de verschillen bij grote n dramatisch
worden.
Wat we gaan doen
We zetten de theoretische groei-curves van O(1), O(log n), O(n) en O(n²) naast elkaar. Geen echte algoritmes — alleen de formules. Zo zie je de vorm van elke klasse zonder dat ruis (constanten, opstarttijd) de boel vertroebelt.
Voorspel
Welke klasse, denk je, blijft het langst beheersbaar bij grote n?
Antwoord
O(1), gevolgd door O(log n).
O(1) is per definitie vlak — het maakt niet uit hoe groot n wordt.
O(log n) groeit zó traag dat zelfs een miljard elementen maar 30 stappen
kost.
O(n) is "fair" — werk schaalt mee. O(n²) loopt vroeg of laat vast —
bij n = 10.000 zit je al op 100 miljoen stappen.
Run — alle klassen tegelijk
Wat zie je?
Op log-log assen (beide assen logaritmisch) zijn de klassen rechte lijnen met verschillende hellingen:
- O(1) — horizontale lijn op 1.
- O(log n) — lijn met heel kleine helling. Groeit nauwelijks.
- O(n) — lijn met helling 1: verdubbel
n, verdubbel stappen. - O(n²) — lijn met helling 2: verdubbel
n, verviervoudig stappen.
De helling op log-log assen verraadt direct de klasse: hoe steiler, hoe slechter het schaalt.
Bij n = 100.000:
- O(1) → 1 stap
- O(log n) → 17 stappen
- O(n) → 100.000 stappen
- O(n²) → 10.000.000.000 stappen (10 miljard.)
Op een lineaire schaal
Soms is de log-log plot lastig om aan te voelen. Hier dezelfde curves op
gewone (lineaire) assen, met een kleinere n-range:
Wat zie je?
O(n²) gaat door het dak terwijl O(1), O(log n) en O(n) nog dicht bij
elkaar lopen. De pijnlijke realiteit van kwadratische algoritmes: voor
kleine n lijken ze prima, voor grote n zijn ze niet meer te
gebruiken.
De vuistregel
Welke klasse je hebt, bepaalt of je algoritme schaalt — niet hoe snel je code is.
Een goed-geschreven O(n²) is nog steeds trager dan een slordig-geschreven
O(n) zodra n groot genoeg wordt. Klasse > constanten.
Door naar overzicht per algoritme →.