Notaci N Asint Tica

Análisis de algoritmos
Profesora: Consuelo Varinia García Mendoza

Notación Asintótica
Cota Superior. Notación O (Omicron)
Cota Inferior.Notación Ω (Omega)
Orden Exacto. Notación θ (Theta)

¿Qué países son más cálidos que México?
¿Qué países con más fríos que México?
¿Quépaíses tiene una temperatura similar a México?

Libia
Tailandia
Etiopia

México
Colombia
Perú

Canadá
Rusia
Mongolia

Ω (México)
Paísescon mayor temperatura
o similar que México, acotados
inferiormente por México

Θ(México)
Países con temperatura similar a
la temperatura enMéxico,
acotados exactamente por
México
О(México)
Países con menor o similar
temperatura que México,
acotados superiormente por
Méxicoa1(n)=n5

Ω(b1 (n))
Funciones que crecen más
rápidamente o igual que b1 (n)

a2(n)=n4

b1 (n)=n3
b2 (n)=n3+48
b3 (n)=25+n+n3

c1(n)=nc2(n)=log2(n)

θ(b1 (n))
Funciones que crecen con la
misma rapidez que b1 (n)

O(b1 (n))
Funciones crecen más despacio
o igual que b1 (n)

CotaSuperior. Notación O
8x+128 Є О(x2) , si existen las constantes positivas
k y x0 tal que 0 ≤ 8x+128 ≤ k x2 para todo x ≥ x0

Cota Inferior.Notación Ω
x5 Є Ω(x2) , si existen las constantes positivas k y x0
tal que 0 ≤ k x2 ≤ x5 para todo x ≥ x0

Cota Inferior. Notación θ
25x2+125 Є θ(x2+10) , si existen las constantes positivas k1, k2 y x0 tal
que 0 ≤ k1 (x2 +10) ≤ 25x2 +125 ≤ k1 (x2 +10) para todo x ≥ x0