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 \le x: 0 \le c_1g (x) \le f (x) \le c_2g (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_1g(x)$ i $c_2g(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 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 dóna un exemple esquemàtic de com es comporten $c_1g(x)$ i $c_2g(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