Stor O-notasjon

Stor O-notasjon er en matematisk notasjon som gir en asymptotisk tilnærming til en funksjon ${\displaystyle g(x)}$, og skrives ofte ${\displaystyle O(g(x))}$. Formålet er å kunne gi en enkel og grov beskrivelse av utviklingen til funksjonen ${\displaystyle g(x)}$ når x øker. Mer presist blir symbolet ${\displaystyle O}$ 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 ${\displaystyle \ f(x)=O(g(x))}$, eventuelt ${\displaystyle \ f\in O(g)}$, betyr at ${\displaystyle \ f(x)}$ for store verdier av ${\displaystyle \ x}$ alltid er mindre enn ${\displaystyle \ cg(x)}$, der c er en konstant. En annen måte å skrive det på, er

${\displaystyle \limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|<\infty .}$

Fordelen med en slik notasjon, er at det går an å forenkle kompleksitetsanalysen, uten å få alt for store feil. For eksempel er ${\displaystyle x^{3}+100x^{2}\in O(x^{3})}$, da 100x² er forsvinnende liten i forhold til x³ 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 ${\displaystyle f\in O(g),g\in O(f)}$, sier vi at ${\displaystyle f\in \Theta (g)}$.