## 1.2.4 NOTACIÓN O MINÚSCULA

La cota superior asintótica dada por la notación O puede o no ser ajustada asintóticamente. La cota 2n2 = O(n2) es ajustada asintóticamente, pero la cota 2n = O(n2) no lo es. Utilizaremos la notación o para denotar una cota superior que no es ajustada asintóticamente.

Definimos formalmente o(g(n)) ("o pequeña") como el conjunto:
o(g(n)) = {f(n): para cualquier constante positiva c > 0, existe una constante n0 > 0 tal que: 0 ≤ f(n) ≤ cg(n) para toda n ≥ n0 }.
Por ejemplo, 2n = o(n2), pero 2n2 no pertenece a o(n2).

Las notaciones de O y o son similares. La diferencia principal es, que en f(n) = O(g(n)), la cota 0 ≤ f(n) ≤ cg(n) se cumple para alguna constante c > 0, pero en f(n) = o(g(n)), la cota 0 ≤ f(n) ≤ cg(n) se cumple para todas las constantes c> 0. Intuitivamente en la notación o, la función f(n) se vuelve insignificante con respecto a g(n) a medida que n se acerca a infinito, es decir:

lim (f(n)/g(n)) = 0.
x -> ∞

Diferencia entre O y o

Para o la desigualdad se mantiene para todas las constantes positivas, mientras que para O la desigualdad se mantiene sólo para algunas constantes positivas.

###