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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Es decir, el operador en la notación asintótica significa concatenación, y no la usual suma algebraica.
Por ejemplo, supóngase que se tiene la serie aunque se
repite n veces se podría pensar erróneamente que Sin embargo, y como
se menciona anteriormente, el operador significa concatenación, por lo tanto,

En algunos casos, la notación aparece del lado izquierdo de una ecuación, por ejemplo,
7n >+(n)=є(n^2).
2
Esto se debe interpretar como “no importa como son escogidas las funciones desconocidas del lado
izquierdo de la igualdad; hay una forma de escoger la función desconocida del lado derecho de la
igualdad para hacer valida la ecuación”.

Por lo tanto, del ejemplo anterior se tiene que para cualquier función , hay una función
f(n)єє(n^2) tal que 7n +g(n)=f(n) para todo n.
2
Es posible juntar un número de tales relaciones como el siguiente ejemplo:

7n^2-2n+3=7n^2+ (n)= (n^2)

Por ejemplo, comprobar que

Para comprobar que , hay que verificar las definiciones de que 2^(n+1)єO(2^n) y
2^(n+1)єΩ(2^n). Empezamos primero por verificar que Entonces tenemos:

Por lo tanto, se cumple que 2^(n+1)єO(2^n). Por otro lado, falta verificar que 2 =Ω(2 ). Entonces
n
n+1
se tiene:

Se llega a que y, por lo tanto, . De aquí que tanto como
oemdjddkdjd se cumplen: se concluye que

En el segundo ejemplo, para comprobar que , de manera similar al anterior ejemplo,
empezamos por verificar que Entonces tenemos:

204