Stor O-notasjon

Stor O-notasjon er en matematisk notasjon som gir en asymptotisk tilnærming til en funksjon , og skrives ofte . Formålet er å kunne gi en enkel og grov beskrivelse av utviklingen til funksjonen  når x øker. Mer presist blir symbolet  brukt til å beskrive en asymptotisk øvre grense for en funksjon ved hjelp av en, som oftest, enklere funksjon. Det er også andre symboler o, Ω, ω, and Θ for å beskrive forskjellige andre asymptotiske grenser. Stor O-notasjon blir spesielt brukt i kompleksitetsteori, en del av informatikken som sier noe om ressursbruken til en algoritme.

Uttrykket , eventuelt , betyr at  for store verdier av  alltid er mindre enn , der c er en konstant. En annen måte å skrive det på, er 

Fordelen med en slik notasjon, er at det går an å forenkle kompleksitetsanalysen, uten å få alt for store feil. For eksempel er , da 100x2 er forsvinnende liten i forhold til x3 når x er stor.

Grensen er ikke streng; g kan godt vokse mye raskere enn f. Hvis de vokser like raskt, det vil si at , sier vi at .

Relaterte notasjoner

Vanlige klasser av funksjoner 

Her er en liste over klasser av funksjoner som en ofte støter på ved analyse av algoritmer. De beskriver tidsforbruket til algoritmer når n øker mot uendelig. Funksjonene er listet med økende kompleksitet. c er en vilkårlig konstant.

Algoritmer‎
Matematisk notasjon