md1 20

R.R

1.

1

Funciones de crecimiento

3. FUNCIONES DE CRECIMIENTO
x

factorial

1
2
3
3,3
4
4,1
4,2
4,3
5
5,2

1
2
6
6
24
24
24
24
120
120

2^n
2
4
8
9,84915531
16
17,1483754
18,3791737
19,6983106
32
36,7583474

n^2
1
4
9
10,89
16
16,81
17,64
18,49
25
27,04

n(log)n
1
3
4,5849625
5,02246602
6
6,13562391
6,27038933
6,40433666
7,32192809
7,57851162

n

log n
0
1
1,5849625
1,72246602
2
2,035623912,07038933
2,10433666
2,32192809
2,37851162

1
2
3
3,3
4
4,1
4,2
4,3
5
5,2

140
120
Factorial

100

2^n
80

n^2

60

n log n
n

40

log n

20
0
1

2

3

3,3

4

4,1

4,2

4,3

5

5,2

Definici´
on 1
Una funci´on f cuyo dominio y codominio son subconjuntos del
conjunto de los n´umeros reales se denomina estrictamente
creciente si f (x) < f (y) siempre que x < y y tanto x como
y est´en en el dominiode f . De forma similar, f se dice que es
estrictamente decreciente si f (x) > f (y) siempre que
x < y y x e y est´en en el dominio de f .

R.R

1.1.

2

Funci´
on O

Definici´
on 2
Sean f y g dos funciones del conjunto de los enteros o de los
reales en el conjunto de los n´umeros reales. Decimos que f (x)
es O(g(x)) si existen dos constantes C y k tales que:
| f (x) |≤ C | g(x) |
siempre que x >k

Observaci´
on 1
Podemos decir que existen infinitos pares de testigos que
cumplen | f (x) |≤ C | g(x) | para x > k.
Ejemplo 1
Demuestre que 7x2 es O(x3).

R.R

3

Soluci´
on. Cuando x > 7 entonces 7x2 < x3 esto es que
se pueden encontrar testigos C = 1 y k = 7 que cumplen la
condici´on. Tambi´en servir´ıan los testigos C = 7 y k = 1, es
decir, 7x2 < 7x3.
Ejemplo 2
¿x3 es O(7x2) ? es plantearla desigualdad x3 ≤ C(7x2) simplificando tenemos x ≤ 7C. No existe un valor de C para
todo x > k, porque el x se puede volver muy grande. Por
tanto x3 no es O(7x2).

R.R

4

Ejemplo 3
f (n) = n2 + 2n + 1 es O(n2) por lo tanto podemos encontrar
un C = 4 tal que n2 + 2n + 1 < 4n2 para n > 1, es decir
k=1

Entonces podemos decir que C = 4 y k = 1 son los testigos.
Teorema 1
Sea f (x) =anxn+an−1xn−1+. . .+a1x+a0 donde a0, a1, . . . , an−1, an
son n´umeros reales. Entonces, f (x) es O(xn).

R.R

5

Teorema 2
Supongamos que f1(x) es O(g1(x)) y f2(x) es O(g2(x)). Entonces, (f1 + f2)(x) es O(max(| g1(x) |, | g2(x) |))
Teorema 3
Supongamos que f1(x) y f2(x) son ambas O(g(x)). Entonces,
(f1 + f2)(x) es O(g(x)).
Teorema 4
Supongamos que f1(x) es O(g1(x)) y f2(x) es O(g2(x)). Entonces, (f1f2)(x) esO(g1(x)g2(x))
Ejemplo 4
Se puede dar una estimaci´on de O para la funci´on factorial
f (n) = n! se define como:
n! = 1 · 2 · 3 . . . n
Se puede estimar n! en notaci´on O.
n! = 1 · 2 · 3 . . . n
≤ n · n · n . . . n = nn
entonces
n! es O(nn)
tomando C = 1 y k = 1 como testigos. ahora aplicando
logaritmos en ambos miembros, tenemos:
log n! ≤ log nn = n log n

R.R

6

Entonces
log n! es O(n log n)considerando C = 1 y k = 1 como testigos.

Ejemplo 5
Sea n < 2n para todo entero positivo n.
Aplicando logaritmos en base dos:
log n < log 2n
log n < n
por tanto log n es O(n) considerando C = 1 y k = 1 como
testigos.
Ejemplo 6

R.R

7

Estimar O(f (n)) siendo f (n) = 3n log(n!) + (n2 + 3) log n
donde n es un entero positivo.
Estimamos 3n log(n!), 3n es O(n) y log(n!) es O(n log n)
por tanto laestimaci´on de 3n log(n!) es O(n2 log n).
Ahora se estima (n2 + 3) log n como n2 + 3 < 2n2 para
n > 2 entonces n2 + 3 es O(n2). entonces (n2 + 3) log n
es O(n2 log n).
Por tanto f (n) = 3n log(n!)+(n2 +3) log n es O(n2 log n)
Ejemplo 7
Conseguir una estimaci´on de f (x) = (x + 1) log(x2 + 1) + 3x2.
Estimamos (x + 1) log(x2 + 1), x + 1 es O(x), ahora estimamos log(x2 + 1), podemos decir que x2 + 1 ≤ 2x2cuando x > 1, por tanto:
log(x2 + 1) ≤ log(2x2) = log 2 + log x2 = log 2 + 2 log x ≤ 3 log x
si x > 2 entonces log(x2 + 1) es O(log x)
Por tanto (x + 1) log(x2 + 1) es O(x log x).
como 3x2 es O(x2) entones f (x) es O(max(x log x, x2))
como x log x ≤ x2 para x > 1, entonces f (x) es O(x2)
1.2.

Funcion Ω

Definici´
on 3
Sean f y g dos funciones del conjunto de los enteros o de los
reales en el...