prueba

TEMA 7

An´lisis asint´tico
a
o
En muchas ocasiones no nos es posible dar con una soluci´n cerrada a
o
una recurrencia o a una suma. Es posible incluso que tal forma cerrada no
exista o que no resulte rentable calcularla. En otras ocasiones necesitamos
comparar las magnitudes de dos formas cerradas sin que sea obvio cu´l de
a
ambas tiende a ser mayor que la otra. En tales casos puederesultar util una
´
respuesta en t´rminos aproximados. Este tema trata b´sicamente sobre c´mo
e
a
o
dar esta informaci´n aproximada, c´mo manejar las aproximaciones y cu´l
o
o
a
es la informaci´n que puede extraerse de ´stas. El t´rmino asint´tico hace
o
e
e
o
referencia a que nuestro inter´s estar´ b´sicamente centrado en aproximar
e
a a
sucesiones f [n] para valores grandes den, esto es, cuando n → ∞.
7.1.

La notaci´n asint´tica
o
o

Mediante la notaci´n asint´tica expresamos el grado de exactitud obteo
o
nido en una aproximaci´n. Seg´n el tipo de aproximaci´n deseado se pueden
o
u
o
utilizar diferentes notaciones asint´ticas. Aqu´ vamos a estudiar principalo
ı
mente la llamada “O” may´scula (en el Ap´ndice 7.A haremos menci´n a
u
e
o
otrasnotaciones asint´ticas).
o
´
Definicion 7.1. Sean f (x) y g(x) dos sucesiones. Se dice que
f (x) = O(g(x))
si existe una constante C tal que
|f (x)| ≤ C|g(x)|

para todo x.

En muchas ocasiones la definici´n anterior es excesivamente general y da
o
poca informaci´n. Para comparar dos funciones alrededor de un valor detero
minado (que suelen ser 0 o ∞) se utilizan las notaciones que acontinuaci´n
o
se introducen:
´
Definicion 7.2. Sean f (x) y g(x) dos funciones. Se dice que
(7.1)

f (x) = O g(x) cuando x → ∞

si existen dos constantes M y C tales que
|f (x)| ≤ C|g(x)|
167

si |x| ≥ M.

´
´
7. ANALISIS ASINTOTICO

168

Del mismo modo se dice que
(7.2)

f (x) = O(g(x)) cuando x → 0

si existen dos constantes C y ε tales que
|f (x)| ≤ C|g(x)|

si |x| ≤ ε.Las definiciones anteriores pueden utilizarse para funciones con variable
real (en cuyo caso solemos utilizar la variable t), con variable compleja (para
las que se suele utilizar la letra z) o con variable discreta (caso de las sucesiones, variable n). Por su inter´s en nuestro contexto, vamos a reformular
e
la definici´n (7.1) para sucesiones, en este caso se sobreentiende que n → ∞:
o
´Definicion 7.3. Sean f [n] y g[n] dos sucesiones. Se dice que
(7.3)

f [n] = O g[n]

cuando n → ∞

si existen una constante C y un ´
ındice n0 tales que
f [n] ≤ C g[n]

para todo n ≥ n0 .

´
Observacion 7.4. Un modo sencillo de reescribir las definici´n de O
o
consiste en observar que
f [n] = O g[n] cuando n → ∞ si y s´lo si
o

f (n)
est´ acotado cuando n → ∞
a
g(n)

lo que,en particular, ocurre cuando
l´
ım

n→∞

f (n)
= M < ∞.
g(n)

Esta ultima condici´n con ser suficiente no es necesaria: la sucesi´n sen(n2 )
´
o
o
no es convergente aunque es obvio que sen(n2 ) = O 1 .
7.1.1. Consideraciones generales sobre la notaci´n “O”: veno
tajas y desventajas. La notaci´n “a[n] = O b[n] ”(que se lee, “a[n] es del
o
orden de b[n]”) y puede interpretarse comoa[n] = O b[n] =⇒ a[n] no es esencialmente mayor que b[n] .
Puede ciertamente ocurrir que a[n] = O b[n] pero a[n] > b[n], es incluso
posible que a[n] sea mucho m´s grande que b[n], pero al menos podemos
a
asegurar el cociente a[n]/b[n] est´ acotado por una constante. El inconvea
niente principal de la notaci´n “O” (y simult´neamente la clave de su ´xito
o
a
e

7.1.

´
´
LA NOTACIONASINTOTICA

169

1

) radica en que esta constante es desconocida. As´ por ejemplo podemos
ı
escribir
n
n = O 1000 n = O
.
1000
Podr´ pensarse que decir que la sucesi´n n no es en esencia mayor que 1000n
ıa
o
es cierto pero poco informativo, pero ¿qu´ decir acerca de lo imprecisa que
e
es la expresi´n “ 1000n no es en esencia mayor que n/1000?” La notaci´n
o
o
“O” resulta...