Bruger:Stowgull/O-notation

Indenfor datalogi og matematik betegner O-notation en måde at udtrykke hvor hurtigt en funktion vokser. Specifikt udtrykker O-notation en øvre grænse på funktionen, når dens input vokser uden grænse. I datalogi bruges O-notation til at beskrive hvordan algoritmers køretid og pladsforbrug afhænger af inputtets størrelse. I matematik, især indenfor talteori, bruges O-notation til at beskrive afstanden mellem funktioner og approksimationer deraf.

En funktion med reelle værdier $f$ siges at være "O af $g(x)$", skrevet $f(x)={\mathcal {O}}(g(x))$, hvis der findes konstanter $C$ og $x_{0}$ således at $f(x)\leq Cg(x)$ for alle $x\geq x_{0}$. For eksempel er $x={\mathcal {O}}(x^{2})$, da $x\leq x^{2}$ for alle $x\geq 1$.