Siguiente: Algunas clases de funciones Un nivel arriba: Ordenes de funciones Anterior: Ordenes de funciones

Definiciones básicas

Sean $f,g:R\rightarrow R$ dos funciones reales.

• Acotamiento superior asintótico: Escribiremos ${\displaystyle f \mathop{=}_{n\rightarrow +\infty}O(g)}$ si
  
  $$\exists C>0,n_C\in N: \;\;n\geq n_C\;\Rightarrow \;\vert f(n)\vert\leq C\vert g(n)\vert.$$
  
  

• Dominación asintótica: Escribiremos ${\displaystyle f \mathop{=}_{n\rightarrow +\infty}o(g)}$ si ${\displaystyle \lim_{n\rightarrow +\infty}\left\vert\frac{f(n)}{g(n)}\right\vert=0,}$ en otras palabras, si
  
  $$\forall \epsilon>0\exists \delta>0: \;\;n\geq \delta\;\Rightarrow \;\left\vert\frac{f(n)}{g(n)}\right\vert<\epsilon.$$
  
  

• Acotamiento inferior asintótico: Escribiremos ${\displaystyle f \mathop{=}_{n\rightarrow +\infty}\Omega(g)}$ si
  
  $$\exists C>0,n_C\in N: \;\;n\geq n_C\;\Rightarrow \;\vert f(n)\vert> C\vert g(n)\vert.$$
  
  
  Consecuentemente
  
  $$f \mathop{=}_{n\rightarrow +\infty}\Omega(g)\;\Leftrightarrow\;g \mathop{=}_{n\rightarrow +\infty}O(f)$$
  
  

De ahora en adelante, sustituiremos la notación `` ${\displaystyle \mathop{=}_{n\rightarrow +\infty}}$'' por ``=''. Escribamos $f\preceq_O g\mbox{\rm si } f=O(g).$ Entonces ``$\preceq_O$'' es una relación reflexiva y transitiva. Definamos la relación de mismos órdenes ``$\asymp$'' como sigue:

$$f\asymp g\;\Leftrightarrow\;(f\preceq_O g)\,\&\,(g\preceq_O f).$$

Entonces $\asymp$ es una relación de equivalencia, es decir, es reflexiva, simétrica y transitiva. Abusando de la notación denotaremos a la clase de equivalencia de una función g por O(g):

$$O(g)=\{f\vert f\asymp g\}.$$

O(g) es el conjunto de funciones con el mismo orden de crecimiento de g.

Observación 1.1   Las relaciones siguientes son inmediatas:

1.

$f=o(g)\;\Rightarrow \;f=O(g)$.

2.

O(g) es cerrado bajo las operaciones de

• suma de funciones, y
• multiplicación de funciones por un escalar,

en otras palabras O(g) es un espacio vectorial.

Ahora, si E es una función creciente y g es cualquier otra función, definimos

$$E(O(g))=\bigcup_{h\in O(g)}O(E(h)).$$

Así pues,

$$f\in E(O(g)) \;\Leftrightarrow\; \exists C_E,C_g,n_0\in N \l... ...\Rightarrow \;\vert f(n)\vert<C_E\vert E(C_g g(n))\vert\right].$$

Siguiente: Algunas clases de funciones Un nivel arriba: Ordenes de funciones Anterior: Ordenes de funciones