Gepubliceerd op 22 augustus 2026 · Bijgewerkt op 31 augustus 2026 · 15 min leestijd

Big O-notatie uitgelegd

De deuren van een concertzaal gaan bijna open. Bij de ingang staat een medewerker met een gastenlijst op een tablet. Wanneer Noor aankomt, moet de medewerker haar naam vinden voordat ze naar binnen kan. Met een paar honderd gasten is dat eenvoudig genoeg en op een moderne tablet lijkt bijna iedere redelijke zoekmethode onmiddellijk klaar. Hetzelfde systeem kan alleen ook worden gebruikt door het kaartverkoopbedrijf achter het evenement. Daar bevat een lijst geen paar honderd namen, maar miljoenen klantgegevens. Die allemaal één voor één controleren klinkt dan een stuk minder onschuldig.

We zouden de zoekopdracht kunnen timen, maar een resultaat van bijvoorbeeld twaalf milliseconden vertelt op zichzelf verrassend weinig. Een snellere computer is eerder klaar, een andere programmeertaal kan extra werk toevoegen en een gelukkige zoekopdracht vindt Noor meteen bovenaan. Belangrijker is dat zo’n meting niet vertelt wat er gebeurt wanneer de lijst tien of duizend keer zo groot wordt. Big O-notatie geeft ons een manier om over die groei te praten. De notatie negeert bewust exacte tijden en veel details van de computer, en vraagt vervolgens hoe het benodigde werk of geheugen verandert wanneer de invoer groeit. Daardoor kunnen we algoritmen vergelijken, maar het maakt Big O geen stopwatch: O(n) beschrijft een groeipatroon, geen duur van n milliseconden.

Van een gastenlijst naar O(n)

Begin met acht ongesorteerde namen in een array. Je kunt die array voorstellen als een rij van acht genummerde plekken in het geheugen, met op iedere plek één naam. Omdat de namen niet zijn gesorteerd, heeft het programma geen aanwijzing waar Noor kan staan. Het leest de eerste plek, vergelijkt die naam met Noor en schuift één plek naar rechts als de namen niet overeenkomen. Zo gaat het door totdat Noor is gevonden of het einde is bereikt.

Stel dat Noor op de achtste plek staat. Het programma leest alle acht plekken. Groeit de lijst naar zestien namen en staat Noor weer achteraan, dan leest het zestien plekken. De lijst verdubbelen heeft het werk verdubbeld, en bij een volgende verdubbeling gebeurt dat opnieuw. Dit noemen we lineaire groei en schrijven we meestal als O(n). De letter n staat voor de grootte van de invoer, in dit voorbeeld dus het aantal namen. Bij een andere analyse kan het om het aantal pixels in een afbeelding of tekens in een document gaan. De letter betekent niets totdat we haar definiëren.

We moeten ook bepalen wat als werk telt. Voor deze zoekopdracht is één naam lezen en vergelijken een bruikbare eenheid. Zo’n keuze noemen we een kostenmodel. Daarmee kunnen we kijken naar het werk dat het algoritme toevoegt zonder te doen alsof processorsnelheid, caching en de kwaliteit van de implementatie niet bestaan. We laten die details alleen buiten dit model en nemen ze weer mee wanneer we het echte programma meten. Ook de invoer zelf maakt verschil: staat Noor op de eerste plek, dan is de zoekopdracht na één vergelijking klaar, hoe lang de lijst ook is. Lineair zoeken heeft daarom een constant beste geval en een lineair slechtste geval. Big O betekent op zichzelf niet “slechtste geval”; de notatie kan beide beschrijven, dus een nuttige analyse benoemt welk geval wordt besproken.

Wat gebeurt er als de invoer verdubbelt?

Een van de makkelijkste manieren om gevoel voor deze patronen te krijgen, is de invoer te verdubbelen en te kijken wat er met het werk gebeurt. Lees de tabel als een reeks gedragingen, niet als een ranglijst die je uit je hoofd moet leren.

De namen kunnen misleidend zijn als je ze te letterlijk leest. O(1) betekent niet één instructie of een onmiddellijk resultaat; duizend vaste instructies zijn nog steeds constant als dat aantal niet met n groeit. Het verschil wordt pas goed zichtbaar als de invoer groter wordt. Bij 1.024 namen bekijkt een volledige scan mogelijk 1.024 plekken, terwijl een proces dat het overgebleven bereik steeds halveert ongeveer tien halveringen nodig heeft. Een kwadratisch proces kan met dezelfde invoergrootte meer dan een miljoen eenheden werk uitvoeren. Dit is het soort verschil dat Big O zichtbaar maakt voordat een ontwerp in productie belandt.

De middelste rijen verdienen wat meer uitleg. Werk dat we beschrijven als O(n log n) combineert meestal twee patronen: het programma verwerkt alle n waarden en doet dat op een aantal niveaus dat groeit als log n. Veel efficiënte sorteeralgoritmen hebben deze vorm omdat ze een lijst herhaaldelijk verdelen en de waarden op ieder niveau verwerken. Kwadratisch werk ontstaat vaak bij het bekijken van paren. Als iedere gast met iedere andere gast moet worden vergeleken, geeft een dubbele gastenlijst tweemaal zoveel gasten elk tweemaal zoveel mogelijke vergelijkingen. Het werk groeit daardoor ongeveer viermaal in plaats van tweemaal.

Exponentiële groei is nog heftiger. Stel je een planningstool voor die iedere mogelijke groep gasten moet proberen. Iedere nieuwe gast kan wel of niet worden opgenomen, dus die ene persoon verdubbelt het aantal groepen dat moet worden bekeken. Met tien gasten zijn er 1.024 mogelijke groepen; met twintig zijn dat er 1.048.576. Snellere hardware kan het probleem uitstellen, maar maakt herhaald verdubbelen niet mild.

Noor vinden door de helft weg te strepen

We kunnen anders zoeken als de namen zijn gesorteerd. In plaats van links te beginnen, lezen we eerst een plek rond het midden. Staat die naam voor Noor, dan kan alles links ervan weg; staat de naam erna, dan kan alles rechts ervan weg. De namen verschuiven niet in het geheugen. Het programma verandert alleen de twee posities die het resterende zoekgebied begrenzen en herhaalt de stap binnen dat kleinere gebied.

Neem acht gesorteerde plekken met Adam, Bo, Chen, Dina, Liu, Noor, Omar en Zoe. De zoekopdracht leest eerst Dina rond het midden. Noor komt later in het alfabet, dus de eerste vier plekken doen niet meer mee. Daarna leest het programma Noor en stopt na twee vergelijkingen. In het minst gunstige geval controleert een gebruikelijke binaire zoekmethode bij acht namen hooguit vier relevante plekken. Bij zestien zijn dat er vijf. De lijst verdubbelen voegt één controle toe in plaats van het werk te verdubbelen. Dit is logaritmische groei, geschreven als O(log n). We laten het grondtal weg omdat een ander grondtal alleen een vaste vermenigvuldigingsfactor oplevert; bij binair zoeken hoort grondtal twee omdat steeds de helft afvalt.

Het woord “logaritmisch” klinkt ingewikkelder dan het idee erachter. Het vraagt hoe vaak je een waarde door een vast getal kunt delen voordat er nog één overblijft. Een bereik van 1.024 plekken kan tien keer worden gehalveerd, want 1.024 is twee tot de tiende macht. Een bereik van ongeveer één miljoen plekken vraagt slechts ongeveer twintig halveringen. De invoer is bijna duizendmaal zo groot geworden, maar de zoekopdracht heeft er maar tien stappen bij gekregen. Die langzame groei is wat O(log n) uitdrukt.

Binair zoeken is niet gratis. De lijst moet al gesorteerd zijn, rechtstreekse toegang tot een gekozen positie ondersteunen en sorteren kost tijd. Als de lijst vaak verandert of maar eenmaal wordt doorzocht, kan vooraf sorteren duurder zijn dan rechtstreeks zoeken. Wordt de lijst eenmaal gesorteerd en daarna duizenden keren doorzocht, dan verdelen we de voorbereiding over al die zoekopdrachten en kan het een verstandige investering zijn. Complexiteit hoort bij een bepaalde bewerking in een bepaalde situatie; zeggen dat “binair zoeken sneller is” zonder de gesorteerde invoer te noemen, laat precies de voorwaarde weg die de snelheid mogelijk maakt.

Hoe ziet Big O eruit in code?

Deze pseudocode schrijft bewerkingen als woorden. De opmerkingen volgen wat er in het geheugen gebeurt.

(define zoekNaamLineair (function namen gezochteNaam)
  ; Het geheugen bevat de hele array en één huidige positie.
  (define huidigePositie 0)

  (while (kleinerDan huidigePositie (lengte namen))
    ; Lees één arrayplek naar een tijdelijke waarde.
    (define huidigeNaam (lees namen huidigePositie))

    (if (gelijk huidigeNaam gezochteNaam)
      (return huidigePositie))

    ; De array blijft gelijk. Alleen de positie schuift naar rechts.
    (set huidigePositie (telOp huidigePositie 1)))

  (return nietGevonden)))

Volg het geheugen tijdens een zoekopdracht naar Noor op de achtste plek. Aan het begin bevat huidigePositie de waarde nul. Het programma leest de naam op plek nul naar huidigeNaam, vergelijkt hem en vervangt de positie door één. Bij de volgende ronde wordt de tijdelijke naam overschreven; de functie maakt geen tweede lijst met alles wat ze al heeft gezien. In het slechtste geval herhaalt ze dit voor iedere plek, dus groeit de tijd als O(n). Het extra geheugen blijft O(1), want de positie en tijdelijke naam vragen een vaste hoeveelheid opslag, ongeacht het aantal namen in de invoer.

Binair zoeken bewaart twee grenzen rond het deel van de array waarin de naam nog kan staan.

(define zoekNaamInGesorteerdeLijst (function gesorteerdeNamen gezochteNaam)
  ; Het geheugen bevat de array en twee grensposities.
  (define eersteMogelijkePositie 0)
  (define laatsteMogelijkePositie (trekAf (lengte gesorteerdeNamen) 1))

  (while (kleinerDanOfGelijk eersteMogelijkePositie laatsteMogelijkePositie)
    (define middelstePositie
      (rondNaarBeneden (deel
        (telOp eersteMogelijkePositie laatsteMogelijkePositie)
        2)))

    ; Lees alleen de middelste plek. De array zelf verschuift niet.
    (define middelsteNaam (lees gesorteerdeNamen middelstePositie))

    (if (gelijk middelsteNaam gezochteNaam)
      (return middelstePositie))

    (if (komtVoor middelsteNaam gezochteNaam)
      ; Vergeet de linkerhelft door de ondergrens te verplaatsen.
      (set eersteMogelijkePositie (telOp middelstePositie 1))
      ; Vergeet de rechterhelft door de bovengrens te verplaatsen.
      (set laatsteMogelijkePositie (trekAf middelstePositie 1))))

  (return nietGevonden)))

eersteMogelijkePositie en laatsteMogelijkePositie bevatten geen delen van de lijst. Ze bevatten twee getallen die naar plekken in de oorspronkelijke array wijzen. Na het lezen van de middelste naam verandert de functie één van die getallen, waardoor de helft van de plekken buiten het resterende bereik valt. Er wordt niets gekopieerd of verwijderd. Zodra de ondergrens voorbij de bovengrens komt, zijn er geen mogelijke plekken meer en staat de naam niet in de lijst. Iedere ronde verwijdert ongeveer de helft van de kandidaten, wat O(log n) tijd in het slechtste geval oplevert. De drie positiewaarden houden het extra geheugengebruik op O(1).

Hieruit volgt ook een nuttige waarschuwing voor het lezen van code. Binair zoeken bevat een lus, maar is daardoor niet automatisch O(n); de grens schuift niet één plek per ronde op. Omgekeerd zijn twee geneste lussen niet automatisch O(n²). De complexiteit hangt af van hoe vaak ze draaien en of beide grenzen met de invoer meegroeien. Tel wat de code doet in plaats van alleen naar haar vorm te kijken.

Waarom constanten en kleinere termen verdwijnen

Stel dat ons model 3n + 5 bewerkingen telt. De drie kan staan voor drie handelingen die we voor iedere naam uitvoeren, terwijl de vijf voorbereidend en afrondend werk voorstelt dat eenmaal gebeurt. Groeit de invoer van 100 naar 200 namen, dan groeit het veranderende deel van 300 naar 600 bewerkingen en blijft de vaste vijf gewoon vijf. Bij 100 namen is dat vaste werk al een klein deel van het totaal; bij een miljoen valt het bijna niet meer op. Big O groepeert de hele uitdrukking bij lineaire functies omdat de term met n bepaalt hoe de kosten groeien.

We kunnen dat concreet maken zonder een vage regel als “schrap de constanten”. Voor iedere n van minstens één is 3n + 5 niet groter dan 8n, omdat we de vijf voor een bovengrens mogen vervangen door 5n. Een vaste vermenigvuldiging van n blijft dus boven de volledige kosten. Het getal acht zelf is niet bijzonder; het gaat erom dat dit getal vaststaat en niet met de invoer meegroeit.

Met dezelfde redenering verdwijnen kleinere termen. Bij n² + 4n + 20 bepaalt het kwadraat uiteindelijk de groei. Voor iedere n van minstens één is de lineaire term niet groter dan 4n² en de constante niet groter dan 20n², dus blijft de hele uitdrukking onder 25n². Daarom beschrijven we haar als O(n²). Deze vereenvoudiging deelt groeipatronen in; ze beweert niet dat constanten in de praktijk niets uitmaken. Een lineair algoritme dat voor ieder item duizend dure bewerkingen uitvoert, kan verliezen van een kleine kwadratische lus. Big O vertelt welke kosten waarschijnlijk gaan overheersen als de invoer groeit. Benchmarks vertellen of dat omslagpunt relevant is voor de invoer die onze gebruikers werkelijk hebben.

Tijd en geheugen zijn afzonderlijk

Big O kan iedere groeiende hulpbron beschrijven, al praten programmeurs meestal over tijd en geheugen. Stel dat we dubbele gast-ID’s willen vinden. Ieder ID met ieder ander ID vergelijken kost kwadratische tijd en weinig extra geheugen. Door de ID’s in een set te bewaren, kunnen we de verwachte tijd vaak lineair maken, maar die set bewaart maximaal n extra waarden. De snellere aanpak heeft een verwachte tijd van O(n) en gebruikt O(n) extra ruimte. We kopen snelheid met geheugen.

Getallen over geheugengebruik vragen dezelfde zorg als getallen over tijd. De invoerlijst staat al in het geheugen; aanvullende ruimte is het geheugen dat het algoritme naast die invoer nodig heeft. Recursieve functies kunnen bovendien geheugen gebruiken via hun aanroepstapel, zelfs als ze nergens zichtbaar een array maken. Een algoritme alleen “O(n)” noemen zonder te zeggen of dat over tijd of ruimte gaat, laat de helft van de analyse onbenoemd.

Bovengrenzen en verschillende gevallen

Formeel geeft Big O een uiteindelijke bovengrens. Kosten T(n) vallen in O(g(n)) als we een vaste vermenigvuldigingsfactor en een beginwaarde voor de invoer kunnen kiezen, waarna die vermenigvuldiging van g(n) altijd boven de kosten blijft. Die beginwaarde is nodig omdat Big O beschrijft wat er gebeurt wanneer de invoer groeit, niet per se bij de eerste paar waarden. De vermenigvuldigingsfactor moet vast blijven; voor iedere nieuwe n een groter getal kiezen zou niets verklaren.

Deze definitie heeft een wat vreemd gevolg. Een lineaire functie valt technisch ook in O(n²), O(n³) en allerlei grotere klassen, omdat al die bovengrenzen er uiteindelijk boven blijven. Zeggen dat lineair zoeken O(n²) is, klopt daardoor formeel, maar gooit de nuttigste informatie weg. In de praktijk geven we meestal de kleinste eenvoudige bovengrens die we kunnen onderbouwen.

Big Theta, geschreven als Θ, laat ons zeggen dat een groeitempo strak is. De functie heeft zowel boven als onder een vaste vermenigvuldiging van dezelfde vorm, zodat ze niet stiekem veel langzamer kan groeien. Het slechtste geval van lineair zoeken is Θ(n), want het werk groeit evenredig met het aantal namen. Het beste geval is Θ(1), want Noor op de eerste plek vinden vraagt altijd een vaste hoeveelheid werk. In gesprekken over software gebruiken mensen “Big O” vaak voor deze strakste eenvoudige klasse. Dat is gebruikelijk en meestal onschuldig, zolang we onthouden wat de formele notatie werkelijk belooft.

Gemiddelde en geamortiseerde kosten beantwoorden weer andere vragen. Voor gemiddelde zoekkosten moeten we expliciet aannemen of Noor aanwezig is en hoe waarschijnlijk iedere plek is. Zonder die aannames bestaat er geen betekenisvol gemiddelde. Geamortiseerde analyse gaat niet uit van willekeurige invoer, maar verdeelt af en toe voorkomend duur werk over een reeks bewerkingen. Meestal schrijft een dynamische array een nieuwe waarde naar één vrije plek. Wanneer de array vol raakt, moet ze een groter geheugenblok reserveren en alle bestaande waarden kopiëren. Die ene toevoeging kan O(n) kosten. Als de capaciteit iedere keer verdubbelt, komen zulke dure kopieeracties steeds minder vaak voor en heeft een lange reeks O(1) geamortiseerde kosten per toevoeging.

Wanneer is Big O nuttig?

Big O is het nuttigst voordat groei een probleem in productie wordt. Een controle op dubbele waarden die ieder paar vergelijkt, kan prima werken voor twintig records en pijnlijk traag worden wanneer een import honderdduizend records bevat. Door het groeitempo op te schrijven, kunnen we dat risico bespreken. De notatie kan ook laten zien waarom een index of set herhaalde zoekopdrachten versnelt, terwijl ze de extra geheugenkosten zichtbaar houdt.

Sommige problemen hebben meer dan één maat voor hun invoer nodig. Een graaf bestaat uit knopen, zoals mensen in een sociaal netwerk, en verbindingen, zoals de relaties tussen hen. Een doorloop schrijven we vaak als O(V + E), omdat het programma mogelijk zowel de knopen als de verbindingen moet bekijken. Twee grafen kunnen evenveel mensen en totaal verschillende aantallen verbindingen bevatten. Beide waarden n noemen zou daarom een echte bron van werk verbergen. Hetzelfde geldt voor een raster met een afzonderlijke breedte en hoogte, of een bewerking die twee onafhankelijk groeiende verzamelingen vergelijkt.

Big O vertelt nog steeds niet of code correct, leesbaar, cachevriendelijk of snel genoeg is. Netwerkvertraging, de kosten van geheugentoewijzingen, parallel werk en het exacte punt waarop de ene implementatie de andere inhaalt, vallen buiten het model. Een lagere groeiklasse rechtvaardigt ook niet automatisch een ingewikkelder ontwerp wanneer de invoer een harde en kleine limiet heeft. Gebruik Big O om de richting van de groei te begrijpen en benchmark daarna de implementatie met realistische gegevens. De analyse en de meting beantwoorden verschillende vragen, en een goede beslissing heeft beide nodig.

Samenvatting

Big O beschrijft hoe werk of geheugen met de invoer groeit. Om de notatie goed te gebruiken, definieer je de invoergrootte, kies je wat je telt en benoem je het geval dat je bespreekt. Vraag daarna wat er gebeurt wanneer de invoer verdubbelt. Een volledige scan vraagt ongeveer tweemaal zoveel werk, een halverende zoekmethode voegt ongeveer één stap toe en een vergelijking van ieder paar vraagt ongeveer viermaal zoveel werk.

Als er maar één idee blijft hangen, laat het dan dit zijn: Big O is een groeimodel, geen snelheidsscore. De notatie laat genoeg details weg om over schaal te kunnen nadenken, maar die weggelaten details verdwijnen niet uit het draaiende programma. Constanten, hardware, voorbereidend werk en de invoergroottes die gebruikers werkelijk aanleveren, bepalen nog steeds welke implementatie wint.

Meer lezen

• Wikipedia: Bisectie
• Wikipedia: Sorteeralgoritme
• Wikipedia: Hashtabel
• Wikipedia: Amortized analysis