Cota ajustada asintòtica

En anàlisis d'algoritmes una cota ajustada asintòtica és una funció que servix de cota tant superior com a inferior d'una atra funció quan l'argument tendix a infinit. Usualment s'utilisa la notació Θ(g(x)) per a referir-se a les funcions acotades per la funció g(x).

Més formalment es definix:

Archiu:CotaAjustadaAsintotica.png

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

Una funció f(x) pertany a Θ(g(x)) quan existixen 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 funciones f i g són iguals a partir d'un valor donat salve per una factor constant. Per tant té sentit prendre a g com un representant de f.

A pesar de que Θ(g(x)) està definit com un conjunt, s'acostuma escriure f(x)=Θ(g(x)) en lloc de f(x)∈Θ(g(x)). Moltes voltes també es parla de la funció x² en lloc de h(x)=x² sempre que estiga clar com és el paràmetro de la funció dins de l'expressió. En la gràfica es dona un eixemple esquemàtic de cóm es comporten $c_{1}g(x)$ i $c_{2}g(x)$ sobre f(x) quan x tendix a infinit.

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

Eixemples

• La funció f(x) = x+10 pot ser acotada per la funció g(x) = x. Per a demostrar-ho basta notar que para tot valor de x≥1 es complix que g(x)≤f(x)≤11g(x), és dir x ≤ x+10 ≤ 11x . Per lo tant x+10 = Θ(x).

Vore també

• Cota inferior asintòtica
• Cota superior asintòtica

Bibliografia

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