la respuesta es 3 ( n2 4 + n 2 ) cuando n es par y 3 ( 1 4 n2 + 1 2 n + 1 4 ) cuando n es impar. b. Porque 3 ( n2 4 + n 2 ) es (n2) y 3 ( 1 4 n2 +...

la respuesta es 3 ( n2 4 + n 2 ) cuando n es par y 3 ( 1 4 n2 + 1 2 n + 1 4 ) cuando n es impar.

b. Porque 3 ( n2 4 + n 2 ) es (n2) y 3 ( 1 4 n2 + 1 2 n + 1 4 ) también es (n2) (por el teorema sobre órdenes polinomiales), este segmento del algoritmo tiene orden n2.
19. Sugerencia: vea la sección 9.6 para un análisis de cómo contar el número de iteraciones del bucle más interno.
22. a 1 a 2 a 3 a 4 a 5 Orden inicial 6 2 1 8 4 Resultado del paso 1 2 6 1 8 4 Resultado del paso 2 1 2 6 8 4 Resultado del paso 3 1 2 6 8 4 Orden final 1 2 4 6 8
22. n 5 a[1] 6 2 1 a[2] 2 6 2 a[3] 1 6 4 a[4] 8 8 6 a[5] 4 8 k 2 3 4 5 6 x 2 1 8 4 j 1 0 2 1 0 3 4 3 2
24. Hay 14 comparaciones. Cada iteración del bucle implica dos comparaciones, una para demostrar si j = 0 y la otra en el enunciado if para comparar x y a[j]. Cuando k = 2, el bucle se ejecuta una vez, da dos comparaciones; cuando k = 3, se ejecuta dos veces, da 4 comparaciones, cuando k = 4, se ejecuta una vez, da 2 comparaciones y cuando k = 5, se ejecuta tres veces, da 6 comparaciones. Así el total es 2 4 2 6 14 comparaciones.
27. Sugerencia: La respuesta a la parte (a) es En 3 4 … (n 1), que es igual a (1 2 3 … (n 1)) ฀ (1 2).
28. El renglón superior de la tabla que se muestra a continuación presenta los valores iniciales del arreglo y el renglón inferior indica los valores finales. El resultado para cada valor de k se muestra en un renglón separado. a 1 a 2 a 3 a 4 a 5 5 3 4 6 2 2 3 4 6 5 2 3 4 6 5 2 3 4 6 5 2 3 4 6 5
30. n 5 a[1] 5 2 a[2] 3 a[3] 4 a[4] 6 5 a[5] 2 5 6 k 1 2 3 4 5 ÍndiceDeMin 1 2 5 2 3 4 5 i 2 3 4 5 3 4 5 4 5 5 temp 5 6
32. Hay una comparación para cada combinación de valores de k e i: a saber, 4 3 2 1 10.
35. b. n ฀ 3 1 n ฀ 2. d. Sugerencia: La respuesta es n2.
36. n 3 a 0 2 a 1 1 a 2 ฀1 a 3 3 x 2 valor polinomio 2 4 0 24 i 1 2 3 term 1 2 ฀1 ฀2 ฀4 3 6 12 24 j 1 1 2 1 2 3
38. Número de multiplicaciones número de iteraciones del bucle interno 1 2 3 … n n n 1 2 por el teorema 5.2.2 Número de sumas número de iteraciones del bucle externo n Así el número total de multiplicaciones y sumas es n(n + 1) 2 + n = 1 2 n2 + 3 2 n.
40. n 3 a 0 2 a 1 1 a 2 ฀1 a 3 3 x 2 valor polinomio 3 5 11 24 i 1 2 3
42. Sugerencia: La respuesta es tn 2n.