Page 209 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

La diferencia entre O (f (n)) y O (f (n)) es que en g (n) = 0 (f (n)) la cota g (n) < cf (n) se cumple para
alguna constante c > 0. Pero en g (n) = 0 (f (n)), la cota g (n) < cf (n) se cumple para cualquier cons-
tante c > 0.

Esta relación g (n) = 0 (f (n)) implica lo siguiente:

De forma análoga, la notación (f(n)) es a la notación Ω(f(n)) como lo son la notación o(f(n)) y O(f(n)).
Se utiliza la notación (f(n)) para denotar una cota inferior que no es asintóticamente justa. For-
malmente se define (f(n)), pequeña omega, como el conjunto:

Varias de las propiedades de números reales se pueden aplicar a las comparaciones asintóticas.
Para cualquier símbolo vale la implicación de transitividad, esto es, si g(n)=O(-
f(n)) y f(n)=O(h(n)), entonces g(n)=O(h(n)).

Para cualquier símbolo vale la relación de reflexibilidad, esto es:

Las siguientes relaciones son inmediatas:

Notación asintótica en ecuaciones y/o desigualdades

Como se ha visto, la notación asintótica se puede emplear en funciones matemáticas, pero ¿cómo
se deben interpretar? Cuando una notación asintótica aparece en una formula, se debe interpre-
tar como una función desconocida. Por ejemplo, la formula n^2-2n+3=n^2+ (n) significa que
n^2-2n+3=n^2+g(n), donde g(n) es alguna función en el conjunto (n).

Utilizar la notación asintótica de esta forma facilita eliminar detalles innecesarios en las ecuaciones.
La cantidad de funciones desconocidas en una expresión es igual al número de veces que la nota-
ción asintótica aparece.

203