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:

$\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\}$

f(x)=Θ(g(x))

Una funció f(x) pertany a Θg(x) quan existeixen constants positives $c_{1}$ i $c_{2}$ tals que a partir d'un valor $x_{0}$ f(x) es troba atrapada entre $c_{1}g(x)$ i $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 $c_{1}g(x)$ i $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 Ω):

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

Exemples

• 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).

Vegeu també

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

Bibliografia

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