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.




