Naar inhoud
BetaAI Begrippen

AI-begrippen in gewone taal. Zoek een begrip, blader op letter of filter op onderwerp.

Grote-O-notatie

Engels: Big O notation · Ook wel: big-O notation, big O, O-notation, big-oh notation, big-O-notatie, O-notatie

In het kort

Grote-O-notatie (big-O-notatie) is een wiskundige notatie voor de groei van een functie bij een steeds grotere waarde. Anders dan een exacte formule geeft deze notatie alleen een bovengrens voor die groei bij heel grote waarden en laat vaste factoren en kleinere termen weg. Zo vergelijken informatici algoritmen: bij een langere lijst stijgt het aantal stappen bij O(n) minder snel dan bij O(n²).

Waarom is dit belangrijk?

Dankzij grote-O-notatie is vooraf te zien of een berekening haalbaar blijft als de hoeveelheid gegevens groeit, los van het soort computer. In wetenschappelijk onderzoek laat de notatie zien welke rekenmethoden bij meer gegevens uitvoerbaar blijven en welke dan onwerkbaar worden. Op het werk weegt die maat mee bij de keuze van een programma voor grote hoeveelheden gegevens, al beschrijft de notatie alleen het slechtste geval en niet een gewone berekening.

Zo werkt het in de praktijk

In de softwarebouw schatten ontwikkelaars met grote-O-notatie rekentijd en geheugen van een algoritme. Het woordenboek van NIST, een overheidsinstituut, legt die maat vast bij een gegeven probleemgrootte. In de analyse beschrijft de notatie de fout van een afgekapte exponentiële reeks, via de stelling van Taylor.

Aan de Universiteit Leiden bestudeert het vak Complexiteit de rekentijd van algoritmen. Studenten bepalen de orde ermee en delen problemen in klassen als P en NP. Via reducties, herleidingen naar een bekend probleem, hoort het handelsreizigersprobleem bij die klassen.

Naast grote-O-notatie horen theta en omega bij de analyse van algoritmen. Donald Knuth voerde die tekens in voor gelijke orde en voor een ondergrens. De complexiteitstheorie gebruikt grote-O-notatie voor tijd, geheugen en invoergrootte.

Bron: en.wikipedia.org

Gecontroleerd op 23 oktober 2026