Big O Notation: What A-Level CS Actually Expects

Big O-notatie komt in elke grote A-level informatica-examenprogramma voor (AQA, OCR, Edexcel) en het veroorzaakt veel problemen bij studenten, niet omdat de wiskunde moeilijk is, maar omdat ze het nooit gekoppeld zien aan werkelijke code. Dit is een praktische uitleg van wat je moet weten en hoe je examentvragen erover beantwoordt zonder te zwetsen.

Wat Big O eigenlijk meet

Big O beschrijft hoe de looptijd (of geheugengebruik) van een algoritme groeit naarmate de inputgrootte, meestal n genoemd, groter wordt. Het is geen stopwatchmeting in seconden. Het is een manier om groeisnelheid te beschrijven zodat je algoritmen kunt vergelijken onafhankelijk van hardware.

Wanneer je O(n) schrijft, zeg je: als ik de input verdubbel, verdubbelt het werk ruwweg ook. O(n²) betekent dat als je de input verdubbelt, het werk ruwweg vervierdubbelt. Dat verband is wat examinators willen dat je identificeert, niet exacte operatietelllingen.

De complexiteiten die je moet kennen

Voor A-level zijn dit degenen die steeds terugkomen:

• O(1) – constante tijd. Een arrayelement per index benaderen: arr[5]. Het maakt niet uit hoe groot de array is.
• O(log n) – logaritmisch. Binair zoeken in een gesorteerde lijst. Elke stap halveert de resterende zoekruimte.
• O(n) – lineair. Een enkele lus door een lijst, zoals een lineair zoeken dat elk item eenmaal controleert.
• O(n log n) – lineair-logaritmisch. Merge sort en quicksort (gemiddeld geval) vallen hier.
• O(n²) – kwadratisch. Geneste lussen over dezelfde gegevens, wat precies wat bubble sort, insertiesort en selectiesort doen.
• O(2ⁿ) – exponentieel. Naïeve recursieve Fibonacci zonder memoisation. Wordt snel lelijk.

Je moet in staat zijn om pseudocode aan te kijken en meteen te zeggen welke van deze het is, omdat dat grotendeels wat wordt getest.

Code lezen voor complexiteit

De methode die altijd werkt: tel de lussen en zie hoe ze zich verhouden tot n.

# O(n) - één lus, één pass
for i in range(n):
    print(i)

# O(n^2) - geneste lus, beide gebonden aan n
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - de zoekruimte halveert elke iteratie
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

Een geneste lus waarbij het bereik van de binnenste lus afhangt van n is nog steeds O(n²), zelfs als het er iets anders uitziet (zoals for j in range(i) in plaats van for j in range(n) — dat is nog steeds kwadratisch overall, alleen met een verschil in constantefactor).

Pas op voor lussen die helemaal niet van n afhangen. Een lus die altijd 10 keer loopt ongeacht invoelgrootte is O(1), ook al is er een lus aanwezig. Examinators vinden het leuk dit stiekem in te verwerken.

Veelvoorkomende sorteeralgoritmen en hun Big O

Dit is een favoriete examenstof omdat het twee programma's tegelijk combineert: sorteeralgoritmen en complexiteit.

Algoritme	Beste geval	Slechtste geval
Bubble sort	O(n)	O(n²)
Insertiesort	O(n)	O(n²)
Merge sort	O(n log n)	O(n log n)
Binair zoeken	O(1)	O(log n)
Lineair zoeken	O(1)	O(n)

De consistentie van merge sort (dezelfde complexiteit best en worst geval) is het waard om uitdrukkelijk te vermelden als een vraag vraagt waarom je het zou kiezen boven bubble sort voor grote datasets. Het beste geval van bubble sort van O(n) is alleen van toepassing met een early-exit optimalisatie wanneer geen swaps plaatsvinden in een pass — vermeld dat detail als je het ter sprake brengt, omdat sommige examencolleges het verwachten.

Waar studenten punten verliezen

De grootste: schrijven