⏱️ Análisis y diseño de algoritmos

1. En el análisis de algoritmos, la notación O grande (Big-O) se utiliza para expresar una cota superior asintótica del crecimiento de una función de tiempo o espacio f(n). De acuerdo con la definición formal, f(n) = O(g(n)) si existen constantes positivas c y n0 tales que, para toda n ≥ n0, se cumple la siguiente relación:

1. 0 ≤ c·g(n) ≤ f(n) para toda n ≥ n0
2. 0 ≤ f(n) ≤ g(n)/c para toda n ≥ n0
3. 0 ≤ f(n) ≤ c·g(n) para toda n ≥ n0
4. c1·g(n) ≤ f(n) ≤ c2·g(n) para toda n ≥ n0

La definición formal de Big-O exige 0 ≤ f(n) ≤ c·g(n) para toda n ≥ n0 con c y n0 constantes positivas; la opción que invierte la desigualdad (c·g(n) ≤ f(n)) corresponde a la definición de Ω, no de O. (Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 3 'Growth of Functions')

2. Un estudiante compara las tres notaciones asintóticas usadas para describir el crecimiento de funciones de tiempo de ejecución. ¿Cuál de las siguientes afirmaciones describe correctamente la diferencia entre Θ (theta) y Ω (omega)?

1. Θ establece una cota ajustada que combina límite superior e inferior, mientras que Ω establece un límite inferior del crecimiento.
2. Ω establece una cota ajustada que combina límite superior e inferior, mientras que Θ establece un límite inferior del crecimiento.
3. Θ establece un límite superior del crecimiento, mientras que Ω establece una cota ajustada que combina límite superior e inferior.
4. Θ y Ω describen ambas un límite superior del crecimiento de la función, con constantes distintas.

Θ es una cota ajustada que combina límite superior e inferior, mientras que Ω solo aporta el límite inferior del crecimiento; confundir estos papeles es un error común al leer notación asintótica. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 3)

3. El algoritmo de ordenamiento por mezcla (Merge Sort) divide el arreglo en dos mitades, ordena cada mitad de forma recursiva y combina los resultados en tiempo lineal. Esta estrategia se modela con la recurrencia T(n) = 2T(n/2) + Θ(n). Al aplicar el teorema maestro (a=2, b=2, f(n)=Θ(n)), ¿cuál es la solución asintótica de T(n)?

1. Θ(n²), porque f(n) domina asintóticamente a n^(log_b a) (caso 3 del teorema maestro)
2. Θ(n log n), porque f(n) coincide con n^(log_b a) (caso 2 del teorema maestro)
3. Θ(n), porque n^(log_b a) domina asintóticamente a f(n) (caso 1 del teorema maestro)
4. Θ(log n), porque a y b son iguales y se cancelan en la recurrencia

La recurrencia T(n) = 2T(n/2) + Θ(n) de Merge Sort corresponde al caso 2 del teorema maestro, pues f(n) = Θ(n) coincide con n^(log_b a) = n, dando Θ(n log n). (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 4.5 y cap. 2.3)

4. Un algoritmo divide y vencerás genera 4 subproblemas de tamaño n/2 en cada llamada y combina los resultados en tiempo lineal, lo que se modela como T(n) = 4T(n/2) + Θ(n). Al aplicar el teorema maestro con a=4, b=2, se obtiene n^(log_b a) = n². Dado que f(n) = Θ(n) es polinomialmente menor que n², ¿cuál es la complejidad de T(n)?

1. Θ(n log n), porque f(n) coincide exactamente con n^(log_b a) (caso 2 del teorema maestro)
2. Θ(n), porque n^(log_b a) resulta menor que f(n) en este caso (caso 1 invertido)
3. Θ(n² log n), porque f(n) domina asintóticamente a n^(log_b a) (caso 3 del teorema maestro)
4. Θ(n²), porque f(n) = Θ(n) es polinomialmente menor que n^(log_b a) = n² (caso 1 del teorema maestro)

Con a=4, b=2, se tiene n^(log_b a) = n², y f(n) = Θ(n) es polinomialmente menor, por lo que aplica el caso 1 del teorema maestro y T(n) = Θ(n²); confundirlo con el caso 2 llevaría erróneamente a Θ(n log n). (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 4.5 'The master method')

5. Un estudiante analiza la función BUILD-MAX-HEAP, que convierte un arreglo desordenado de n elementos en un montículo binario válido llamando a MAX-HEAPIFY sobre cada nodo interno, desde el último nodo interno hasta la raíz. Como MAX-HEAPIFY cuesta O(log n) y se invoca aproximadamente n/2 veces, el estudiante concluye erróneamente que BUILD-MAX-HEAP cuesta O(n log n). ¿Cuál es la complejidad real, obtenida con un análisis más ajustado que considera la altura de cada subárbol?

1. O(n)
2. O(n log n)
3. O(log n)
4. O(n²)

Un análisis más fino de BUILD-MAX-HEAP, que considera que la mayoría de los nodos tienen poca altura, muestra que su costo total es O(n) y no O(n log n) como sugiere la cota ingenua de n/2 llamadas por O(log n). (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 6.3)

6. Al recorrer un grafo representado mediante listas de adyacencia usando el algoritmo de búsqueda en amplitud (BFS) o en profundidad (DFS), donde V es el número de vértices y E el número de aristas, ¿cuál es la complejidad temporal del recorrido?

1. O(V · E)
2. O(E log V)
3. O(V + E)
4. O(V²)

BFS y DFS con listas de adyacencia visitan cada vértice y cada arista una sola vez, dando complejidad O(V + E); usar una matriz de adyacencia daría O(V²), menos eficiente en grafos dispersos. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), caps. 22.2 y 22.3)

7. El algoritmo de Dijkstra calcula las rutas más cortas desde un vértice origen hacia todos los demás vértices de un grafo con pesos no negativos. Cuando la cola de prioridad se implementa con un montículo binario, ¿cuál es la complejidad temporal del algoritmo en función de los vértices V y las aristas E?

1. O(V + E), porque el recorrido del grafo domina el costo total del algoritmo
2. O((V + E) log V), porque cada operación de extracción o actualización en el montículo cuesta O(log V)
3. O(V² + E), porque se utiliza una matriz de adyacencia en lugar de un montículo
4. O(V log E), porque cada arista se procesa una vez dentro de una estructura logarítmica

Con un montículo binario como cola de prioridad, cada extracción o decremento de clave en Dijkstra cuesta O(log V), y se realizan O(V+E) de estas operaciones, dando O((V+E) log V). (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 24.3)

8. El ordenamiento por inserción recorre el arreglo y coloca cada elemento en su posición correcta dentro de la parte ya ordenada. Cuando el arreglo de entrada ya está completamente ordenado, cada elemento se compara una sola vez y no se desplaza. ¿Cuál es la complejidad temporal correspondiente a este mejor caso?

1. Θ(n log n)
2. Θ(n²)
3. Θ(log n)
4. Θ(n)

El ordenamiento por inserción, con la entrada ya ordenada, realiza una sola comparación por elemento sin desplazamientos, alcanzando su mejor caso Θ(n); el peor y el promedio son Θ(n²). (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 2.2)

9. Una tabla hash utiliza una función de dispersión uniforme simple para distribuir n claves entre sus posiciones. En el caso promedio, la búsqueda de una clave tarda tiempo O(1); sin embargo, si muchas claves distintas producen el mismo valor de dispersión y se encadenan en la misma posición, la búsqueda puede degradarse. ¿Cuál es la complejidad de este peor caso?

1. O(n)
2. O(1)
3. O(log n)
4. O(n log n)

Con dispersión uniforme simple, el caso promedio de búsqueda en una tabla hash es O(1), pero si muchas claves colisionan en la misma posición, la búsqueda puede degradarse hasta O(n) en el peor caso. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 11)

10. Para poder aplicar el algoritmo de búsqueda binaria y localizar un elemento en tiempo O(log n), ¿qué condición debe cumplir previamente el arreglo sobre el que se realiza la búsqueda?

1. El arreglo debe tener un número par de elementos
2. El arreglo debe contener únicamente valores numéricos
3. El arreglo debe estar ordenado
4. El arreglo debe estar almacenado en una lista ligada

La búsqueda binaria depende de descartar mitades del arreglo comparando con el elemento central, lo cual solo es válido si el arreglo está ordenado; de lo contrario no garantiza O(log n). (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), ejercicio 2.3-5; Sedgewick, Algorithms, 4a ed.)

11. Un programador debe buscar un valor dentro de un arreglo de n elementos que no está ordenado y que se modifica constantemente, por lo que mantenerlo ordenado resultaría costoso. Para localizar el valor, decide recorrer el arreglo elemento por elemento hasta encontrarlo o llegar al final. En el peor caso, en el que el valor buscado está en la última posición o no existe, ¿cuál es la complejidad de esta búsqueda lineal?

1. O(log n)
2. O(n)
3. O(n log n)
4. O(1)

En el peor caso, cuando el valor buscado está al final o no existe, la búsqueda lineal debe revisar los n elementos, dando complejidad O(n). (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 2 (Linear Search))

12. Un equipo de desarrollo intenta diseñar un algoritmo de ordenamiento basado exclusivamente en comparaciones entre pares de elementos que garantice, en el peor caso, un número de comparaciones menor al de Merge Sort y Heapsort. De acuerdo con el análisis del árbol de decisión para algoritmos de comparación, ¿qué resultado teórico limita este objetivo?

1. Todo algoritmo de ordenamiento por comparaciones requiere Ω(n log n) comparaciones en el peor caso
2. Todo algoritmo de ordenamiento por comparaciones requiere Ω(n) comparaciones en el peor caso
3. Todo algoritmo de ordenamiento por comparaciones requiere Ω(n²) comparaciones en el peor caso
4. Todo algoritmo de ordenamiento por comparaciones requiere O(log n) comparaciones en el peor caso

El teorema 8.1 (árbol de decisión) demuestra que cualquier algoritmo de ordenamiento basado en comparaciones requiere Ω(n log n) comparaciones en el peor caso, por lo que no es posible superar asintóticamente ese límite con este tipo de algoritmos. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 8, teorema 8.1)

13. Un desarrollador necesita ordenar repetidamente arreglos pequeños que, por el contexto de la aplicación, casi siempre llegan ya casi ordenados o con muy pocos elementos fuera de lugar. Está evaluando si conviene usar ordenamiento por inserción en lugar de un algoritmo Θ(n log n) en el peor caso. Considerando el análisis de mejor, peor y caso promedio, ¿qué argumento justifica correctamente esa elección?

1. El ordenamiento por inserción tiene complejidad Θ(n log n) en todos los casos, igual que Merge Sort, por lo que la elección entre ambos no afecta el desempeño.
2. El ordenamiento por inserción es siempre más lento que Merge Sort y Heapsort, sin importar qué tan ordenada esté la entrada inicial.
3. El ordenamiento por inserción alcanza su peor caso Θ(n) cuando la entrada ya está ordenada, lo que lo hace preferible en cualquier escenario.
4. El ordenamiento por inserción alcanza su mejor caso Θ(n) precisamente cuando la entrada ya está casi ordenada, por lo que puede superar en la práctica a un algoritmo con complejidad Θ(n log n) fija.

El mejor caso Θ(n) del ordenamiento por inserción ocurre cuando la entrada ya está casi ordenada, lo que puede hacerlo más eficiente en la práctica que un algoritmo con complejidad fija Θ(n log n) para ese tipo de entradas. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 2.2)

14. La programación dinámica es una técnica de diseño de algoritmos que resuelve problemas almacenando los resultados de subproblemas para evitar recalcularlos. ¿Cuáles son las dos propiedades que debe cumplir un problema para que esta técnica sea aplicable de forma efectiva?

1. Subproblemas independientes y subestructura óptima
2. Subproblemas superpuestos y subestructura óptima
3. Subproblemas superpuestos y ausencia de subestructura óptima
4. Subproblemas independientes y ausencia de recursión

La programación dinámica requiere que el problema tenga subestructura óptima (la solución óptima se construye a partir de soluciones óptimas de subproblemas) y subproblemas superpuestos que se repiten. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 15)

15. Tanto la programación dinámica como la estrategia de divide y vencerás dividen un problema en subproblemas más pequeños. ¿Cuál es la diferencia clave que distingue a la programación dinámica de divide y vencerás?

1. En programación dinámica los subproblemas son independientes entre sí, mientras que en divide y vencerás se reutilizan resultados ya calculados
2. La programación dinámica siempre utiliza recursión, mientras que divide y vencerás nunca la utiliza
3. En programación dinámica los subproblemas se superponen y se reutilizan resultados ya calculados, mientras que en divide y vencerás los subproblemas son independientes entre sí
4. Divide y vencerás solo puede aplicarse a problemas de ordenamiento, mientras que la programación dinámica se aplica a cualquier tipo de problema

La clave está en que la programación dinámica reutiliza resultados de subproblemas que se superponen, mientras que divide y vencerás genera subproblemas independientes que no se repiten. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 15)

16. Se tiene el siguiente pseudocódigo para calcular el n-ésimo número de Fibonacci con memoización: FIB-MEMO(n, memo) 1 si memo[n] ya fue calculado 2 regresar memo[n] 3 si n ≤ 1 4 memo[n] = n 5 si no 6 memo[n] = FIB-MEMO(n-1, memo) + FIB-MEMO(n-2, memo) 7 regresar memo[n] Al trazar la ejecución para n=5, ¿cuántas llamadas distintas con un valor de n no repetido se resuelven realmente por recursión (sin contar las que se recuperan directamente de memo)?

1. 6 llamadas, una por cada valor distinto de n entre 0 y 5 que se calcula solo una vez
2. 16 llamadas, una por cada invocación recursiva generada, incluidas las repetidas
3. 5 llamadas, una por cada valor distinto de n entre 1 y 5 que se calcula solo una vez
4. 1 llamada, porque toda la recursión se resuelve de una sola vez gracias a la memoización

Al trazar FIB-MEMO(5), solo los valores n=0,1,2,3,4,5 se calculan realmente por recursión una vez cada uno; las demás llamadas recursivas recuperan el resultado directamente de memo sin recalcularlo. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 15 (memoización))

17. En programación dinámica existen dos enfoques principales para evitar recalcular subproblemas: uno almacena resultados en una tabla que se llena de manera ascendente (bottom-up) sin usar recursión explícita, y otro almacena resultados conforme se van necesitando durante llamadas recursivas. ¿Cómo se denominan, respectivamente, estos dos enfoques?

1. Memoización y tabulación
2. Recursión e iteración
3. Backtracking y ramificación y poda
4. Tabulación y memoización

La tabulación construye la solución de manera ascendente llenando una tabla sin recursión explícita, mientras que la memoización almacena resultados conforme se generan durante llamadas recursivas descendentes. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 15)

18. Un analista evalúa cuatro problemas para decidir si conviene resolverlos con programación dinámica. Determina que uno de ellos consiste en calcular, para cada subarreglo posible, el costo mínimo de multiplicar una cadena de matrices, donde el costo óptimo de una subcadena depende de los costos óptimos de subcadenas más pequeñas que se repiten en distintas combinaciones. ¿Por qué este problema es un candidato adecuado para programación dinámica?

1. Porque cada subcadena de matrices se resuelve de forma independiente y nunca se repite en otra combinación
2. Porque presenta subestructura óptima y los mismos subproblemas de multiplicación de subcadenas se repiten en distintas combinaciones
3. Porque el problema no tiene una solución recursiva y solo puede resolverse mediante fuerza bruta
4. Porque el costo de multiplicar las matrices siempre es constante, sin importar el orden de la multiplicación

La multiplicación de cadenas de matrices tiene subestructura óptima y subproblemas superpuestos, pues los costos óptimos de subcadenas menores se reutilizan al calcular subcadenas mayores, lo que la hace un candidato clásico para programación dinámica. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 15.2 (multiplicación de cadenas de matrices))

19. Al calcular Fibonacci(30) de forma puramente recursiva sin memoización, el número de llamadas crece de forma exponencial porque los mismos subproblemas (por ejemplo, Fibonacci(28)) se recalculan muchas veces. Si se aplica programación dinámica con memoización, almacenando cada resultado la primera vez que se calcula, ¿cuál es el orden de crecimiento del número de subproblemas distintos que se calculan?

1. O(2^n), porque la memoización no reduce el número de subproblemas distintos
2. O(log n), porque la memoización reduce el problema a una búsqueda binaria
3. O(n), porque solo existen n valores distintos de Fibonacci entre 0 y n
4. O(n²), porque cada subproblema depende de los dos anteriores y se cuentan por pares

Con memoización, cada valor de Fibonacci entre 0 y n se calcula una sola vez y se almacena, por lo que el número de subproblemas distintos crece como O(n), a diferencia del crecimiento exponencial de la recursión sin memoización. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 15)

20. El algoritmo Merge Sort divide el arreglo en mitades, ordena cada mitad recursivamente y combina los resultados mediante un proceso de mezcla lineal. ¿Cuál es su complejidad temporal en el mejor, promedio y peor caso, y cuánto espacio auxiliar requiere?

1. Θ(n log n) en los tres casos; espacio auxiliar O(n)
2. Θ(n log n) en los tres casos; espacio auxiliar O(1)
3. Θ(n²) en el peor caso y Θ(n log n) en el mejor caso; espacio auxiliar O(n)
4. Θ(n) en el mejor caso y Θ(n log n) en el peor caso; espacio auxiliar O(log n)

Merge Sort combina las mitades ordenadas en tiempo lineal en cada nivel de la recursión, logrando Θ(n log n) en mejor, promedio y peor caso, con un espacio auxiliar O(n) para los subarreglos temporales. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 2.3)

21. El algoritmo Quicksort selecciona un elemento pivote, particiona el arreglo en dos subarreglos según ese pivote y ordena cada subarreglo recursivamente. Cuando las particiones resultan razonablemente balanceadas en la mayoría de las llamadas, ¿cuál es la complejidad temporal esperada en el caso promedio?

1. Θ(n²), porque el pivote siempre genera una partición completamente desbalanceada
2. Θ(n), porque cada elemento se procesa una sola vez sin llamadas recursivas adicionales
3. Θ(log n), porque el número de particiones es proporcional a la altura del árbol de recursión
4. Θ(n log n), porque las particiones resultan balanceadas en la mayoría de las llamadas recursivas

Cuando las particiones de Quicksort resultan razonablemente balanceadas, como ocurre en el caso promedio con un pivote aleatorio o bien elegido, la complejidad esperada es Θ(n log n). (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 7)

22. Un programador implementa Quicksort eligiendo siempre el último elemento del subarreglo como pivote. Al ordenar un arreglo que ya llega completamente ordenado de menor a mayor, cada partición separa un solo elemento del resto, generando particiones totalmente desbalanceadas en cada llamada recursiva. ¿Cuál es la complejidad temporal resultante en este escenario?

1. Θ(n log n)
2. Θ(n²)
3. Θ(n)
4. Θ(2^n)

Al elegir siempre el último elemento como pivote sobre un arreglo ya ordenado, cada partición separa solo un elemento, generando n niveles de recursión con trabajo lineal cada uno, es decir, Θ(n²). (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 7)

23. Heapsort construye un montículo binario a partir del arreglo y extrae repetidamente el elemento máximo para colocarlo en su posición final. ¿Cuál es su complejidad temporal en el peor caso y cuánto espacio auxiliar adicional requiere, en comparación con Merge Sort?

1. O(n log n) en el peor caso, con espacio auxiliar O(n), igual que Merge Sort
2. O(n log n) en el peor caso, con espacio auxiliar O(log n), menor que el de Merge Sort pero mayor que cero
3. O(n log n) en el peor caso, con espacio auxiliar O(1), a diferencia de Merge Sort que requiere O(n)
4. O(n²) en el peor caso, con un espacio auxiliar adicional de O(1) sobre el arreglo original

Heapsort extrae el máximo del montículo n veces, cada una en O(log n), sin necesitar arreglos auxiliares adicionales, por lo que su espacio auxiliar es O(1), a diferencia de Merge Sort que requiere O(n). (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 6)

24. Se aplica el algoritmo de partición de Quicksort (esquema de Lomuto) al arreglo [5, 2, 8, 1, 9, 3] usando siempre el último elemento como pivote. El pivote inicial es 3. Después de recorrer el arreglo intercambiando los elementos menores que el pivote hacia la izquierda, ¿en qué posición final (contando desde el índice 0) queda colocado el pivote 3, y cuántos elementos del arreglo original son menores que él?

1. En el índice 2, porque 2 y 1 son los elementos menores que el pivote 3
2. En el índice 1, porque 2 y 1 son los elementos menores que el pivote 3
3. En el índice 3, porque 2, 1 y 8 son los elementos menores que el pivote 3
4. En el índice 2, porque 5, 2 y 1 son los elementos menores que el pivote 3

En el esquema de partición de Lomuto sobre [5,2,8,1,9,3] con pivote 3, solo 2 y 1 son menores que el pivote; tras el recorrido y el intercambio final, el pivote queda en el índice 2. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 7.1 (esquema de partición de Lomuto))

25. Con respecto a Merge Sort y Heapsort, ambos algoritmos garantizan complejidad O(n log n) en el peor caso. Todas las siguientes afirmaciones sobre estos dos algoritmos son verdaderas, EXCEPTO:

1. Heapsort ordena el arreglo in situ, utilizando únicamente O(1) de espacio auxiliar adicional
2. Merge Sort requiere espacio auxiliar O(n) debido al proceso de mezcla de subarreglos
3. Ambos algoritmos alcanzan complejidad O(n log n) en el peor caso, a diferencia de Quicksort
4. Ambos requieren la misma cantidad de espacio auxiliar, pues Heapsort también usa O(n) para mezclar subarreglos

Heapsort ordena in situ con O(1) de espacio auxiliar, mientras que Merge Sort necesita O(n) para el proceso de mezcla; afirmar que ambos requieren el mismo espacio auxiliar es falso. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), caps. 2.3 y 6)

26. Un equipo de desarrollo debe ordenar un arreglo muy grande dentro de un sistema embebido con memoria RAM extremadamente limitada, por lo que no puede reservar espacio auxiliar adicional proporcional al tamaño de la entrada. Además, necesita una garantía de O(n log n) incluso en el peor caso. ¿Cuál de los siguientes algoritmos de ordenamiento cumple mejor con ambos requisitos?

1. Merge Sort, porque garantiza O(n log n) en el peor caso, aunque requiere espacio auxiliar proporcional a n
2. Heapsort, porque ordena in situ con O(1) de espacio auxiliar y garantiza O(n log n) en el peor caso
3. Quicksort con pivote fijo, porque en promedio alcanza O(n log n) y ordena in situ
4. Ordenamiento por inserción, porque ordena in situ con O(1) de espacio auxiliar adicional

Heapsort garantiza O(n log n) incluso en el peor caso y ordena in situ con solo O(1) de espacio auxiliar adicional, cumpliendo ambos requisitos, a diferencia de Merge Sort (espacio O(n)) o Quicksort con pivote fijo (peor caso Θ(n²)). (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 6)

27. En la relación de recurrencia del teorema maestro T(n) = a·T(n/b) + f(n), utilizada para analizar algoritmos de dividir y vencerás, ¿qué representa el parámetro a?

1. El número de subproblemas en los que se divide el problema original en cada llamada recursiva
2. El factor por el cual se reduce el tamaño de cada subproblema respecto al problema original
3. El costo de dividir el problema y combinar las soluciones de los subproblemas
4. El número de veces que se ejecuta el ciclo principal antes de alcanzar el caso base

En T(n)=a·T(n/b)+f(n), a≥1 es el número de subproblemas generados en cada llamada; b>1 es el factor de reducción de tamaño (segunda opción) y f(n) es el costo de dividir/combinar (tercera opción). (Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 4.5 'The master method')

28. De acuerdo con la definición formal de la notación O grande, se dice que f(n) = O(g(n)) cuando existen constantes positivas c y n0 tales que:

1. 0 ≤ f(n) ≤ c·g(n) para toda n ≥ n0
2. 0 ≤ c·g(n) ≤ f(n) para toda n ≥ n0
3. c1·g(n) ≤ f(n) ≤ c2·g(n) para toda n ≥ n0
4. f(n) = c·g(n) para toda n ≥ n0

La definición de O grande exige 0 ≤ f(n) ≤ c·g(n) para n ≥ n0; la segunda opción corresponde a Ω y la tercera a Θ, ambas cotas distintas. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 3 'Growth of Functions')

29. Un analista determina que el tiempo de ejecución de un algoritmo tiene simultáneamente una cota superior y una cota inferior del mismo orden de crecimiento. ¿Qué notación asintótica debe usar para expresar este resultado?

1. Notación Θ (theta), porque establece una cota ajustada, superior e inferior a la vez
2. Notación Ω (omega), porque solo garantiza una cota inferior del crecimiento
3. Notación O grande, porque solo garantiza una cota superior del crecimiento
4. Notación o pequeña, porque describe una cota superior no ajustada

Θ denota una cota ajustada (superior e inferior simultáneas); Ω solo acota por abajo y O solo por arriba, por lo que ninguna de las dos describe una cota ajustada por sí sola. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 3 'Growth of Functions')

30. Un desarrollador analiza una función recursiva que divide un arreglo en dos mitades iguales y combina los resultados con un recorrido lineal del arreglo completo; la recurrencia que describe su tiempo de ejecución es T(n) = 2T(n/2) + n. Al aplicar el teorema maestro, ¿cuál es el orden de crecimiento de T(n)?

1. Θ(n log n)
2. Θ(n)
3. Θ(n²)
4. Θ(log n)

Como log2(2)=1 y f(n)=n tiene el mismo orden que n^1, se aplica el caso 2 del teorema maestro: Θ(n log n), tal como en Merge Sort. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 4.5 y cap. 2.3 (Merge Sort))

31. Un algoritmo recursivo genera 4 subproblemas de tamaño n/2 en cada llamada y realiza un trabajo adicional lineal para combinarlos, de modo que T(n) = 4T(n/2) + n. ¿Cuál es su orden de crecimiento según el teorema maestro?

1. Θ(n²)
2. Θ(n log n)
3. Θ(n² log n)
4. Θ(n)

log2(4)=2, y f(n)=n crece asintóticamente más lento que n², por lo que se aplica el caso 1 del teorema maestro: T(n)=Θ(n²). (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 4.5 'The master method')

32. La búsqueda binaria sobre un arreglo ordenado puede describirse mediante la recurrencia T(n) = T(n/2) + 1, donde cada llamada descarta la mitad del arreglo y realiza una comparación de tiempo constante. ¿Cuál es el orden de crecimiento resultante?

1. Θ(log n)
2. Θ(n)
3. Θ(√n)
4. Θ(n log n)

Con a=1, b=2, log2(1)=0 y f(n)=1=n^0, se aplica el caso 2 del teorema maestro: T(n)=Θ(n^0 log n)=Θ(log n), consistente con la complejidad de la búsqueda binaria. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), ejercicio 2.3-5 y cap. 4.5)

33. Un estudiante intenta resolver la recurrencia T(n) = 2T(n/2) + n/log n mediante el teorema maestro, comparando f(n) = n/log n con n^(log2 2) = n. ¿Cuál es la razón por la que el teorema maestro no puede aplicarse directamente en este caso?

1. Existe un hueco polinomial entre f(n) y n; f(n) es asintóticamente menor pero no lo es por un factor n^ε
2. a = 2 no es una potencia de b = 2, lo cual invalida las hipótesis del teorema
3. f(n) debe ser siempre una función polinomial, y n/log n no lo es en ningún caso
4. El teorema maestro solo aplica cuando f(n) es una constante, y aquí f(n) depende de n

f(n)=n/log n es menor que n=n^(log2 2) pero no por un factor polinomial n^ε, por lo que no cumple la condición estricta del caso 1; este 'hueco' es una limitación conocida del teorema maestro. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 4.5 (limitaciones del teorema maestro))

34. ¿Cuál es la característica que define a un algoritmo voraz (greedy)?

1. En cada paso elige la opción que parece localmente óptima, sin reconsiderar decisiones tomadas previamente
2. En cada paso evalúa todas las combinaciones posibles de soluciones antes de decidir
3. Divide el problema en subproblemas independientes y combina sus soluciones óptimas
4. Almacena en una tabla los resultados de todos los subproblemas ya resueltos para reutilizarlos

Un algoritmo voraz toma la mejor decisión local en cada paso sin volver atrás; explorar todas las combinaciones es fuerza bruta, dividir en subproblemas independientes es divide y vencerás, y almacenar resultados en tabla es programación dinámica. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 16 'Greedy Algorithms')

35. Un programador diseña un algoritmo voraz para resolver un problema de optimización combinatoria y quiere asegurar que la solución obtenida sea la óptima global, no solo una aproximación razonable. ¿Qué debe cumplir el problema para que esto esté garantizado?

1. Debe tener la propiedad de elección voraz y subestructura óptima
2. Debe tener subproblemas superpuestos y subestructura óptima
3. Debe poder representarse como un grafo dirigido acíclico ponderado
4. Debe admitir una tabla de programación dinámica de tamaño polinomial

La optimalidad de un algoritmo voraz requiere la propiedad de elección voraz además de subestructura óptima; subproblemas superpuestos con subestructura óptima es, en cambio, la condición que motiva usar programación dinámica. (Cormen et al., Introduction to Algorithms, 3ª ed. (MIT Press, 2009), cap. 16 y cap. 15)