Cota ajustada asimptòtica

En anàlisi d'algorismes, una cota ajustada asimptòtica és una funció que serveix de cota tant superior com inferior d'una altra funció quan l'argument tendeix a infinit. Usualment s'utilitza la notació Θ g(x) per referir-se a les funcions acotades per la funció g(x).

Més formalment es defineix:

${\displaystyle \Theta (g(x))=\left\{{\begin{matrix}f(x):{\mbox{ existeixen }}c_{1},c_{2},x_{0}{\mbox{c onstants positives tals que }}\\\forall x:x_{0}\leq x:0\leq c_{1}g(x)\leq f(x)\leq c_{2}g(x)\end{matrix}}\right\}}$

Una funció f(x) pertany a Θg(x) quan existeixen constants positives ${\displaystyle c_{1}}$ i ${\displaystyle c_{2}}$ tals que a partir d'un valor ${\displaystyle x_{0}}$ f(x) es troba atrapada entre ${\displaystyle c_{1}g(x)}$ i ${\displaystyle c_{2}g(x)}$. Vol dir que les funcions f i g són iguals a partir d'un valor donat llevat per una factor constant. Per tant té sentit prendre a g com un representant de f.

Tot i que Θ g(x) està definit com un conjunt, s'acostuma a escriure f(x)=Θ(g(x)) en lloc de f(x)∈Θg(x). Moltes vegades també es parla de la funció x² en lloc de h(x) = x² sempre que estigui clar quin és el paràmetre de la funció dins de l'expressió. En la gràfica es dona un exemple esquemàtic de com es comporten ${\displaystyle c_{1}g(x)}$ i ${\displaystyle c_{2}g(x)}$ pel que fa a f(x) quan x tendeix a infinit.

La cota ajustada asimptòtica té relació amb les cotes superior i inferior asimptòtiques (respectivament les notacions O i Ω):

${\displaystyle f(x)=\Theta (g(x)){\mbox{ si i només si }}f(x)=O(g(x)){\mbox{ i }}f(x)=\Omega (g(x))\,}$

• La funció f(x)= x+10 pot ser fitada per la funció g(x)=x. Per demostrar prou notar que per a tot valor de x≥1 es compleix que g(x)≤f(x)≤11g(x), és a dir x≤x+10≤11x. Per tant x+10=Θ(x).

• Cota inferior asimptòtica
• Cota superior asimptòtica

• Introduction to Algorithms, Second Edition by Thomas H. Corman, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein