los ejercicios 1 al 12.
1. 6n + 1
2. 2n2 + 1
3. 6n3 + 12n2 + 1
4. 3n2 + 2n lg n
5. 2 lg n + 4n + 3n lg n
6. 6n6 + n + 4
7. 2 + 4 + 6+· · ·+2n
8. (6n + 1)2
9. (6n + 4)(1 + lg n)
10. (n + 1)(n + 3) /n + 2
11. (n2 + lg n)(n + 1)/n+n2
12. 2 + 4 + 8 + 16+· · ·+2n
En los ejercicios 13 al 15, seleccione una notación theta para f (n) +
g(n).
13. f (n) = (1), g(n) = (n2)
14. f (n) = 6n3 + 2n2 + 4, g(n) = (n lg n)
15. f (n) = (n3/2), g(n) = (n5/2)
En los ejercicios 16 al 25, seleccione una notación theta entre
(1), (lg n), (n), (n lg n),
(n2), (n3), (2n), or (n!)
para el número de veces que se ejecuta la expresión x = x + 1.
16. for i = 1 to 2n
x = x + 1
17. i = 1
while (i ≤ 2n) {
x = x + 1
i = i + 2
}
18. for i = 1 to n
for j = 1 to n
x = x + 1
19. for i = 1 to 2n
for j = 1 to n
x = x + 1
20. for i = 1 to n
for j = 1 to i/2
x = x + 1
21. for i = 1 to n
for j = 1 to n
for k = 1 to n
x = x + 1
22. for i = 1 to n
for j = 1 to n
for k = 1 to i
x = x + 1
23. for i = 1 to n
for j = 1 to i
for k = 1 to j
x = x + 1
24. j = n
while ( j ≥ 1) {
for i = 1 to j
x = x + 1
j = j/3
}
25. i = n
while (i ≥ 1) {
for j = 1 to n
x = x + 1
i = i/2
}
26. Encuentre un notación theta para el número de veces que se ejecuta
la expresión x = x + 1.
i = 2
while (i < n) {
i = i 2
x = x + 1
}
27. Sea t(n) el número total de veces que se incrementa i y se disminuye
j en el siguiente seudocódigo, donde a1, a2, . . . es una sucesión
de números reales.
i = 1
j = n
while (i < j ) {
while (i < j ∧ ai < 0)
i = i + 1
while (i < j ∧ a j ≥ 0)
j = j − 1
if (i < j )
swap(ai , a j )
}
Encuentre una notación theta para t(n).
28. Encuentre una notación theta para el tiempo requerido en el peor
caso por el siguiente algoritmo:
esclave(s, n, clave){
for i = 1 to n − 1
for j = i + 1 to n
if (si + s j == key)
return 1
else
return 0
}
29. Además de encontrar una notación theta en los ejercicios 1 al 28,
pruebe que ésta es correcta.
30. Encuentre el número exacto de comparaciones (líneas 10, 15, 17,
24 y 26) requeridas por el siguiente algoritmo cuando n es par y
cuando n es impar. Encuentre la notación theta para este algoritmo.
Entrada: s1, s2 , . . . , sn, n
Salida: grande (el elemento mayor en s1, s2, . . . , sn),
chico (el elemento menor en s1, s2, . . . , sn)
1. grande_chico(s, n, grande, chico){
2. if(n == 1)
3. grande = s1
4. chico = s1
5. return
6. }
7. m = 2 n/2
8. i = 1
9. while (i ≤ m − 1) {
10. if (si > si+1)
11. swap(si , si+1)
12. i = i + 2
13.}
14. if (n > m) {
15. if (sm−1 > sn)
16. swap(sm−1, sn)
17. if (sn > sm)
18. swap(sm, sn)
19. }
20. pequeño= s1
21. grande = s2
22. i = 3
23. while (i ≤ m − 1)
24. if (si < pequeño)
24. pequeño= si
26. if (si+1 > grande)
27. grande= si+1
28. i = i + 2
28. }
30. }
31. Este ejercicio muestra otra manera de adivinar una fórmula para
1 + 2 + . . . + n.
El ejemplo 4.3.7 sugiere que
1 + 2+· · ·+n = An2 + Bn + C para toda n,
para algunas constantes A, B y C. Suponiendo que esto es cierto, sustituya
n = 1, 2, 3 para obtener tres ecuaciones con tres incógnitas A,
B y C. Ahora se despejan A, B y C. Ahora puede demostrarse la fórmula
obtenida usando inducción matemática (vea la sección 1.7).
32. Suponga que a > 1 y que f (n) = (loga n). Demuestre que f (n) =
(lg n)).
33. Demuestre que n! = O(nn).
34. Demuestre que 2n = O(n!).
35. Usando un argumento parecido al de los ejemplos 4.3.7 al 4.3.9 o
algún otro, demuestre que
36. Demuestre que nn+1 = O(2n2 )
37. Demuestre que lg(nk+c) = (lg n) para toda k > 0 y c > 0 fijas.
38. Demuestre que si n es una potencia de 2, por ejemplo, n = 2k, entonces
39. Suponga que f(n) = O(g(n)) y f(n) ≥ 0 y g(n) > 0 para toda n ≥ 1. Demuestre
que para alguna constante C, f(n) = Cg(n) para toda n ≥ 1.
40. Establezca y pruebe un resultado para similar al del ejercicio 39.
41. Establezca y pruebe un resultado para similar al de los ejercicios
39 y 40.
Determine si cada expresión en los ejercicios 42 al 52 es verdadera o
falsa. Si es falsa, dé un contraejemplo. Suponga que las funciones f, g
y h toman sólo valores positivos.
42. nn = O(2n)
43. 2 + sen n = O(2 + cos n)
44. Si f(n) = (h(n)) y g(n) = (h(n)), entonces f(n) + g(n) = (h(n)).
45. Si f (n) = (g(n)) entonces c f (n) = (g(n)) para cualquier
c 0.
46. Si f (n) = (g(n)) entonces 2 f (n) = (2g(n) )
47. Si f (n) = (g(n)) entonces lg f (n) = (lg g(n)). Suponga
que f (n) ≥ 1 y g(n) ≥ 1 para toda n = 1, 2, . . . .
48. Si f (n) = O(g(n)), entonces g(n) = O( f (n))
49. Si f (n) = O(g(n)) entonces g(n) = ( f (n)).
50. Si f (n) = (g(n)) entonces g(n) = ( f (n))
51. f (n) + g(n) = (h(n)) donde h(n) = máx {f (n), g(n)}
52. f (n) + g(n) = (h(n)), donde h(n) = mín {f (n), g(n)}
53. Escriba exactamente qué significa f (n) O(g(n)).
54. ¿Qué está mal en el siguiente argumento que intenta demostrar
que no se puede tener al mismo tiempo f (n) O(g(n)) y g(n)
O(f (n))?
Si f (n) O(g(n)), entonces para toda C > 0, |f (n)| > C|g(n)|.
En particular, |f (n)| > 2|g(n)|. Si g(n) O(f (n)), entonces para
toda C > 0, |g(n)| > C|f (n)|. En particular, |g(n)| > 2|f (n)|.
Pero ahora
| f (n)| > 2|g(n)| > 4| f (n)|.
Cancelando |f (n)| se tiene 1 > 4, que es una contradicción. Por
lo tanto, no es posible tener f (n) O(g(n)) y g(n) O(f (n)) al
mismo tiempo.
55. Encuentre las funciones f y g que satisfacen
f (n) O(g(n)) y g(n) O(f (n)).
56. Proporcione un ejemplo de funciones positivas crecientes f y g definidas
en los enteros positivos para las que
f (n) O(g(n)) y g(n) O(f (n)).
57. Demuestre que nk = O(cn) para toda k = 1, 2, . . . y c > 1.
58. Encuentre funciones f, g, h y t que satisfagan
f (n) = (g(n)), h(n) = (t (n)),
f (n) − h(n) = (g(n) − t (n)).
59. Suponga que el tiempo en el peor caso de un algoritmo es (n).
¿Cuál es el error en el siguiente razonamiento? Como 2n = (n),
el tiempo en el peor caso para correr el algoritmo con una entrada
de tamaño 2n será aproximadamente el mismo que el tiempo en el
peor caso para correr el algoritmo con una entrada de tamaño n.
60. ¿Define f (n) O(g(n))
una relación de equivalencia en el conjunto de funciones de valores
reales en {1, 2, . . .}?
61. ¿Define f (n) (g(n))
una relación de equivalencia en el conjunto de funciones de valores
reales en {1, 2, . . .}?
62. [Requiere integración]
a) Demuestre, consultando la figura, que
63. [Requiere integración]. Use un argumento como el mostrado en el
ejercicio 62 para demostrar que
65. Sean a = 1 + 1/(n + 1) y b = 1 + 1/n en la desigualdad del ejercicio 64 para demostrar que la sucesión {(1 + 1/n)n} es creciente.
66. Sean a = 1 y b = 1 + 1/(2n) en la desigualdad del ejercicio 64
para demostrar que
para toda n ≥ 1.
El método usado para probar los resultados de este ejercicio
y su predecesor se debe aparentemente a Fort en 1862 (vea
[Chrystal, vol. II, página 77]).
67. Usando los dos ejercicios anteriores o de otra manera, pruebe que
para toda n ≥ 1.
68. Use el ejercicio anterior para probar que
(Compare con el ejercicio 62).
69. ¿Qué está mal en la siguiente “demostración” de que cualquier algoritmo
tiene un tiempo de corrida O(n)?
Debemos demostrar que el tiempo requerido para una entrada
de tamaño n es a lo más una constante multiplicada por n.
Paso base
Suponga que n = 1. Si el algoritmo toma C unidades de tiempo
para una entrada de tamaño 1, tomará a lo más C·1 unidades de
tiempo. Entonces la afirmación es verdadera para n = 1.
Paso inductivo
Suponga que el tiempo requerido para una entrada de tamaño n es
a lo más C n y que el tiempo para procesar un elemento adicional
es C . Sea C el máximo entre C y C . Entonces el tiempo total requerido
para una entrada de tamaño n + 1 es a lo más
C n + C ≤ Cn + C = C(n +1).
Esto verifica el paso inductivo.
Por inducción, para una entrada de tamaño n, el tiempo requerido
es a lo más un tiempo constante n. Por lo tanto, el tiempo
de corrida es O(n).
En los ejercicios 70 al 75, determine si la afirmación es verdadera o
falsa. Si es verdadera, demuéstrelo. Si es falsa, dé un contraejemplo.
Suponga que f y g son funciones de valores reales definidas en el conjunto
de enteros positivos y que g(n) 0 para n ≥ 1. Estos ejercicios
requieren cálculo.
76. Use inducción para probar que
77. [Requiere cálculo]. Sea ln x el logaritmo natural (loge x) de x. Use
integración para obtener una estimación de la fórmula
78. Utilice el resultado del ejercicio 77 y la fórmula de cambio de base
para logaritmos para obtener la fórmula
79. Deduzca
de la desigualdad del ejercicio 78.
