Cota inferior asintòtica

En anàlisis d'algoritmes una cota inferior asintòtica és una funció que servix de cota 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 inferiorment per la funció g(x).

Més formalment es definix:

$\Omega (g(x))=\left\{\begin{array}{c}f(x):\text{existen }c,x_0\text{ constantes positivas tales que}\\ \mathrm{\forall }x:x_0\le x:0\le cg(x)\le f(x)\end{array}\right\}$

Una funció f(x) pertany a Ω(g(x)) quan existix una constant positiva c tal que a partir d'un valor $x_0$, $cg(x)$ no supera f(x). Vol dir que la funció f és superior a g a partir d'un valor donat salve per un factor constant.

La cota inferior asintòtica té utilitat en Teoria de la complexitat computacional a l'hora de calcular la complexitat del millor cas per als algoritmes.

Erro al crear miniatura:

f(x)=Ω(g(x)).

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 d'una funció nomenant únicament la seua expressió, com en 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 com es comporta $cg(x)$ sobre f(x) quan x tendix a infinit.

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

$f(x)=\Theta (g(x))\text{ si y solo si }f(x)=O(g(x))\text{ y }f(x)=\Omega (g(x))$

Eixemples

• La funció x² pot ser acotada inferiorment per la funció x. Per a demostrar-ho basta notar que para tot valor de x≥1 es complix x≤x². Per tant x² = Ω(x) (no obstant, x no servix com a cota superior per a x²).
• La funció x²+200x està acotada inferiorment per x². Vol dir que quan x tendix a infinit el valor de 200x es pot despreciar sobre el de x².

Vore també

• Cota ajustada asintòtica
• Cota superior asintòtica
• Notació de Landau

Bibliografia

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