🌳 Estructuras de datos y algoritmos

1. Según la definición formal de la notación O-grande, se dice que f(n) = O(g(n)) cuando existen constantes positivas c y n₀ tales que, para toda n ≥ n₀, se cumple la siguiente relación:

1. 0 ≤ f(n) ≤ c·g(n), para toda n ≥ n₀
2. 0 ≤ c·g(n) ≤ f(n), para toda n ≥ n₀
3. c₁·g(n) ≤ f(n) ≤ c₂·g(n), para toda n ≥ n₀
4. f(n) ≤ g(n) ≤ c·f(n), para toda n ≥ n₀

La definición formal de O-grande acota superiormente f(n) mediante c·g(n) para n suficientemente grande; la relación 0 ≤ c·g(n) ≤ f(n) corresponde en cambio a la cota inferior Ω. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 3 (Growth of Functions))

2. ¿Qué tipo de cota asintótica proporciona la notación Ω(g(n)) sobre el tiempo de ejecución de un algoritmo?

1. Una cota inferior, que garantiza un crecimiento mínimo del tiempo de ejecución
2. Una cota superior, que garantiza un crecimiento máximo del tiempo de ejecución
3. Una cota ajustada que coincide exactamente con el tiempo de ejecución promedio
4. Una medida del espacio de memoria utilizado, no del tiempo de ejecución

Ω(g(n)) define una cota inferior asintótica: garantiza que, salvo por una constante, el algoritmo no crece más lento que g(n); confundirla con la cota superior O es un error común. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 3 (Growth of Functions))

3. Cuando se afirma que un algoritmo tiene complejidad Θ(g(n)), esto significa que:

1. El tiempo de ejecución nunca supera un múltiplo constante de g(n), sin cota inferior garantizada
2. El tiempo de ejecución iguala exactamente a g(n) para cualquier valor de n
3. El tiempo de ejecución está acotado tanto superior como inferiormente por múltiplos constantes de g(n)
4. El tiempo de ejecución depende únicamente del caso más favorable del algoritmo

Θ(g(n)) exige simultáneamente una cota superior y una inferior con constantes distintas, es decir, un crecimiento asintóticamente ajustado; hablar solo de cota superior corresponde a O, no a Θ. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 3 (Growth of Functions))

4. Un programador necesita localizar un valor dentro de un arreglo de un millón de elementos que ya está ordenado de forma ascendente. Si aplica el algoritmo de búsqueda binaria en lugar de un recorrido secuencial, ¿cuál es la complejidad temporal en el peor caso de su búsqueda?

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

La búsqueda binaria divide a la mitad el espacio de búsqueda en cada paso, logrando O(log n) sobre un arreglo ordenado, muy inferior al O(n) de un recorrido secuencial. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 2 (ejercicio 2.3-5) / Cap. 12)

5. ¿Cuál es la cota inferior demostrada para el número de comparaciones que requiere, en el peor caso, cualquier algoritmo de ordenamiento basado en comparaciones (como quicksort o merge sort)?

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

El teorema de la cota inferior para ordenamiento por comparaciones demuestra que se requieren al menos Ω(n log n) comparaciones en el peor caso, límite que alcanzan merge sort y heapsort. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 8 (Teorema 8.1))

6. Al analizar una implementación de quicksort, un estudiante observa que el pivote elegido siempre resulta ser el elemento más pequeño del subarreglo, generando particiones de tamaño 1 y n−1 en cada llamada recursiva. ¿Qué complejidad temporal tendrá el algoritmo en este escenario?

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

Cuando el pivote siempre es el elemento mínimo, las particiones quedan desbalanceadas (1 y n−1), generando el peor caso de quicksort, O(n²); Θ(n log n) corresponde al caso promedio, no a este escenario. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 7 (Quicksort))

7. El algoritmo de ordenamiento por mezcla (merge sort) divide el arreglo recursivamente y combina los subarreglos ordenados. ¿Cuál es su complejidad temporal en el peor caso?

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

Merge sort mantiene Θ(n log n) en el mejor, promedio y peor caso porque siempre divide el arreglo a la mitad, independientemente del orden inicial de los datos. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 2 (sección 2.3, Merge Sort))

8. Un montículo binario (heap) de n elementos se construye a partir de un arreglo desordenado mediante el procedimiento Build-Max-Heap, y posteriormente se le insertan elementos uno por uno. ¿Cuál de las siguientes afirmaciones describe correctamente las complejidades de ambas operaciones?

1. Construir el montículo completo es O(n log n), mientras que cada inserción individual es O(1)
2. Construir el montículo completo es O(n), mientras que cada inserción individual es O(log n)
3. Construir el montículo completo es O(log n), mientras que cada inserción individual es O(n)
4. Tanto la construcción del montículo como cada inserción individual son O(log n)

Build-Max-Heap procesa todo el arreglo en O(n) aprovechando que la mayoría de los nodos están cerca de las hojas, mientras que cada inserción individual solo recorre la altura del árbol, O(log n). (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 6 (Heapsort))

9. En una tabla hash que resuelve colisiones mediante encadenamiento (chaining), bajo la hipótesis de hashing uniforme simple, ¿cuál es el costo promedio de una búsqueda en términos del factor de carga α (número de elementos entre número de cubetas)?

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

Bajo hashing uniforme simple, el costo esperado de una búsqueda con encadenamiento es Θ(1 + α), donde el 1 corresponde al cálculo de la función hash y α a la longitud promedio de la cadena recorrida. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 11 (Teoremas 11.1 y 11.2, Hash Tables))

10. Un árbol binario de búsqueda se construyó insertando una secuencia de claves ya ordenadas de menor a mayor, sin ningún mecanismo de balanceo. ¿Cuál es la complejidad de una operación de búsqueda en este árbol resultante?

1. O(log n), porque todo árbol binario de búsqueda mantiene su altura mínima
2. O(n), porque el árbol degenera en una estructura similar a una lista enlazada
3. O(1), porque la búsqueda siempre inicia y concluye en el nodo raíz del árbol
4. O(n log n), porque cada comparación recorre subárboles completos

Insertar claves ya ordenadas sin balanceo produce un árbol degenerado equivalente a una lista enlazada, por lo que la búsqueda cuesta O(n) en vez del O(log n) típico de un árbol balanceado. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 12 (Binary Search Trees))

11. Un ingeniero debe elegir entre BFS y DFS para explorar un grafo representado por lista de adyacencia con el objetivo de detectar ciclos. Ambos recorridos completos tienen la misma complejidad asintótica en función de V y E. ¿Cuál es dicha complejidad, común a ambos algoritmos?

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

Tanto BFS como DFS, al recorrer un grafo por lista de adyacencia, visitan cada vértice y cada arista una única vez, resultando en Θ(V + E) para ambos algoritmos. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 22 (secciones 22.2-22.3, BFS y DFS))

12. Un desarrollador debe representar un grafo disperso (con pocas aristas en relación con el número de vértices, es decir E mucho menor que V²) para optimizar el uso de memoria. ¿Qué representación resulta más eficiente en espacio de almacenamiento?

1. Matriz de adyacencia, porque su espacio es proporcional a Θ(V + E)
2. Lista de adyacencia, porque su espacio es proporcional a Θ(V²)
3. Matriz de adyacencia, porque su espacio es proporcional a Θ(V²)
4. Lista de adyacencia, porque su espacio es proporcional a Θ(V + E)

La lista de adyacencia ocupa Θ(V + E), proporcional al número real de aristas, mientras que la matriz de adyacencia siempre ocupa Θ(V²) sin importar cuán disperso sea el grafo, por lo que resulta ineficiente para grafos con pocas aristas. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 22 (Elementary Graph Algorithms))

13. Para verificar si existe una arista específica (u, v) en un grafo, ¿cuál es la diferencia de complejidad entre usar una matriz de adyacencia y usar una lista de adyacencia?

1. O(1) con lista de adyacencia, contra O(V) con matriz de adyacencia en cualquier caso
2. O(V) con ambas representaciones, sin ninguna diferencia práctica entre ellas
3. O(1) con matriz de adyacencia, contra O(grado de u) con lista de adyacencia, hasta O(V) en el peor caso
4. O(1) con matriz de adyacencia, contra O(E) con lista de adyacencia en todos los casos

Con matriz de adyacencia, consultar (u,v) es un acceso directo O(1); con lista de adyacencia hay que recorrer la lista de u, cuyo costo depende de su grado y puede llegar a O(V) en el peor caso. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 22 (comparación de representaciones de grafos))

14. Una pila (stack) es una estructura de datos lineal cuyo principio de acceso a los elementos se conoce como:

1. Primero en entrar, primero en salir (FIFO)
2. Elemento de mayor prioridad, sin importar el orden de llegada
3. Último en entrar, primero en salir (LIFO)
4. Acceso aleatorio a cualquier posición por índice

Una pila sigue el principio LIFO: el último elemento apilado es el primero en desapilarse, a diferencia de una cola (FIFO). (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 10 (sección 10.1, Stacks and Queues))

15. En una cola (queue), el orden en que los elementos son atendidos sigue el principio:

1. Último en entrar, primero en salir (LIFO)
2. Primero en entrar, primero en salir (FIFO)
3. Orden aleatorio determinado por la posición en memoria
4. Orden inverso al de inserción de los elementos

En una cola, los elementos se atienden en el mismo orden en que llegaron (FIFO), a diferencia de la pila, donde se atiende primero el último en llegar. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 10 (sección 10.1, Stacks and Queues))

16. ¿Cuál es la complejidad temporal de las operaciones push y pop sobre una pila implementada correctamente (ya sea con arreglo o con lista enlazada)?

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

Push y pop solo manipulan el elemento en la cima de la pila (agregar o quitar), sin recorrer el resto de la estructura, por lo que su costo es constante, O(1). (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 10 (sección 10.1, Stacks and Queues))

17. ¿Cuál es la complejidad temporal de las operaciones enqueue y dequeue sobre una cola implementada correctamente?

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

Enqueue y dequeue únicamente actualizan los apuntadores de frente y final de la cola, sin recorrer los demás elementos, por lo que se ejecutan en O(1). (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 10 (sección 10.1, Stacks and Queues))

18. Un compilador necesita verificar si las llaves, paréntesis y corchetes de un programa fuente están correctamente balanceados (cada símbolo de apertura tiene su correspondiente cierre en el orden adecuado). ¿Qué estructura de datos es la más adecuada para resolver este problema de manera eficiente?

1. Una cola, encolando los símbolos de apertura y desencolándolos en el mismo orden de llegada
2. Una lista enlazada que mantiene los símbolos ordenados alfabéticamente por tipo
3. Un arreglo estático que aplica búsqueda binaria sobre las posiciones de los símbolos
4. Una pila, apilando los símbolos de apertura y desapilándolos al hallar el cierre correspondiente

Al apilar cada símbolo de apertura y desapilarlo cuando aparece su cierre correspondiente, la pila permite verificar el balance respetando el orden de anidamiento, algo que una cola no logra por su orden FIFO. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 10 (sección 10.1, aplicación clásica de pilas))

19. Durante la implementación de un algoritmo de recorrido en anchura (BFS) sobre un grafo representado por lista de adyacencia, se necesita almacenar temporalmente los vértices descubiertos que aún no han sido visitados, respetando el orden en que fueron encontrados. ¿Qué estructura de datos utiliza típicamente BFS para este propósito?

1. Un árbol binario de búsqueda
2. Una cola (queue)
3. Una tabla hash
4. Una pila (stack)

BFS emplea una cola para mantener el orden en que los vértices fueron descubiertos y garantizar que se visiten por niveles de distancia creciente. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 22 (sección 22.2, BFS))

20. Cuando una función se invoca a sí misma de manera recursiva, el entorno de ejecución guarda la información de cada llamada activa (variables locales, dirección de retorno) en una estructura de datos que se gestiona automáticamente. ¿Qué estructura de datos es esta y qué principio de acceso sigue?

1. Una cola de llamadas, que sigue el principio FIFO
2. Un montículo (heap) de llamadas, ordenado por prioridad de ejecución
3. Una pila de llamadas, que sigue el principio LIFO
4. Una lista circular, que sigue un principio de acceso rotativo

El entorno de ejecución guarda cada llamada activa en una pila de llamadas: la última función invocada es la primera en terminar y ser retirada, principio LIFO. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 10 (sección 10.1, pila de llamadas y recursión))

21. Al comparar la inserción de un nuevo elemento al inicio de la estructura, ¿cuál es la diferencia de complejidad entre un arreglo y una lista simplemente enlazada?

1. O(1) en el arreglo, porque el índice 0 permite acceso directo; O(n) en la lista enlazada, porque exige recorrerla por completo
2. O(n) en ambas estructuras, ya que ninguna permite modificar el primer elemento sin recorrer la estructura completa
3. O(log n) en el arreglo mediante búsqueda binaria; O(1) en la lista enlazada mediante su apuntador inicial
4. O(n) en el arreglo, porque requiere desplazar los elementos existentes; O(1) en la lista enlazada, porque solo cambia un apuntador

Insertar al inicio de un arreglo obliga a desplazar todos los elementos existentes, O(n), mientras que en una lista enlazada basta con actualizar el apuntador al nuevo primer nodo, O(1). (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 10 (sección 10.2, Linked Lists))

22. ¿Cuál es la complejidad temporal de acceder a un elemento en una posición arbitraria (por índice) dentro de un arreglo estático?

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

Un arreglo estático permite calcular la dirección de memoria de cualquier posición mediante aritmética de apuntadores, por lo que el acceso por índice es O(1). (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 10 (sección 10.1, Arrays))

23. ¿Cuál es la complejidad temporal de acceder al elemento que ocupa la k-ésima posición dentro de una lista simplemente enlazada, partiendo del primer nodo?

1. O(1), porque cada nodo mantiene un apuntador directo a su posición numérica
2. O(log n), porque la lista enlazada permite aplicar búsqueda binaria
3. O(k²), porque cada apuntador debe verificarse más de una vez
4. O(n), porque hay que recorrer los nodos desde el inicio hasta la posición k

Una lista enlazada no ofrece acceso directo por posición: para llegar al k-ésimo nodo hay que recorrer los apuntadores desde el primero, costo O(n). (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 10 (sección 10.2, Linked Lists))

24. ¿Cuál de las siguientes operaciones sobre una pila (stack) NO se ejecuta en tiempo O(1)?

1. Insertar un nuevo elemento en la cima de la pila (push)
2. Buscar si un valor arbitrario se encuentra en cualquier posición de la pila
3. Consultar el elemento de la cima sin eliminarlo de la pila (peek/top)
4. Eliminar el elemento que se encuentra en la cima de la pila (pop)

Push, pop y peek/top solo manipulan la cima de la pila en O(1); buscar un valor arbitrario exige recorrer potencialmente todos los elementos, costo O(n). (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 10 (sección 10.1, Stacks and Queues))

25. En una lista doblemente enlazada, un proceso ya cuenta con un apuntador directo al nodo que desea eliminar (no necesita buscarlo desde el inicio). ¿Cuál es la complejidad de la operación de eliminación en este caso, comparada con eliminar un nodo del cual solo se conoce su valor y hay que localizarlo primero?

1. O(n) si ya se tiene el apuntador al nodo; O(1) si primero hay que buscarlo por su valor
2. O(1) en ambos casos, sin importar si se conoce o no el apuntador al nodo, por tratarse de una lista doblemente enlazada
3. O(1) si ya se tiene el apuntador al nodo; O(n) si primero hay que buscarlo por su valor
4. O(log n) en ambos casos, porque se puede aplicar búsqueda binaria sobre los apuntadores de la lista

En una lista doblemente enlazada, si ya se tiene el apuntador al nodo, eliminarlo solo exige reconectar sus vecinos, O(1); si solo se conoce el valor, primero hay que recorrer la lista para localizarlo, O(n). (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 10 (sección 10.2, listas doblemente enlazadas))

26. Una cola se implementa utilizando un arreglo de tamaño fijo con dos índices (frente y final) que solo avanzan hacia adelante sin reutilizar los espacios liberados al hacer dequeue. Después de varias operaciones de encolado y desencolado, el índice final llega al límite del arreglo aunque existan espacios libres al principio. ¿Qué técnica de implementación resuelve este problema de desperdicio de espacio?

1. Una pila auxiliar que reordena los elementos restantes cada vez que se desencola uno
2. Una tabla hash que indexa cada elemento por su posición original de encolado
3. Una lista doblemente enlazada sin límite de tamaño fijo, que reemplaza por completo al arreglo
4. Una cola circular, donde los índices avanzan mediante aritmética modular y regresan al inicio del arreglo

Una cola circular reutiliza los espacios liberados al hacer avanzar los índices de frente y final mediante aritmética modular, evitando el desperdicio de espacio de una cola lineal con arreglo. (CLRS, 'Introduction to Algorithms', 3a ed., Cap. 10 (sección 10.1, implementación de colas con arreglo circular))

27. ¿Cuál es la definición formal de la notación asintótica f(n) = O(g(n))?

1. Existen constantes positivas c y n₀ tales que 0 ≤ f(n) ≤ c·g(n) para toda n ≥ n₀
2. Existen constantes positivas c y n₀ tales que 0 ≤ c·g(n) ≤ f(n) para toda n ≥ n₀
3. Existen constantes positivas c₁, c₂ y n₀ tales que c₁·g(n) ≤ f(n) ≤ c₂·g(n) para toda n ≥ n₀
4. Existe una constante n₀ tal que f(n) < g(n) para toda n mayor que n₀, sin necesidad de una constante multiplicativa c

La notación O-grande exige una cota superior con una constante multiplicativa c y un umbral n₀; la segunda opción corresponde a Ω y la tercera a Θ. (CLRS, "Introduction to Algorithms", 3a ed., Cap. 3 (Growth of Functions))

28. ¿Cuál es la forma general de una recurrencia de divide y vencerás a la que puede aplicarse el teorema maestro?

1. T(n) = T(n − 1) + T(n − 2) + f(n), con f(n) asintóticamente positiva
2. T(n) = aT(n − b) + f(n), con a ≥ 1 y b > 0 constantes
3. T(n) = aT(n/b) + f(n), con a ≥ 1 y b > 1 constantes
4. T(n) = aT(n/b) + f(n), con 0 < a < 1 y b > 1 constantes

El teorema maestro se aplica a recurrencias T(n) = aT(n/b) + f(n) con a ≥ 1 subproblemas y un factor de reducción b > 1; la primera opción corresponde a una recurrencia tipo Fibonacci y la segunda reduce por resta, no por división. (CLRS, "Introduction to Algorithms", 3a ed., Cap. 4 (Divide-and-Conquer, Teorema 4.1))

29. La recurrencia del algoritmo de ordenamiento por mezcla (merge sort) es T(n) = 2T(n/2) + Θ(n). Aplicando el teorema maestro, ¿cuál es la solución de esta recurrencia?

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

Con a=2, b=2, f(n)=Θ(n)=Θ(n^(log_2 2)), se cumple el caso 2 del teorema maestro, cuya solución es Θ(n log n), coincidente con la complejidad conocida de merge sort. (CLRS, "Introduction to Algorithms", 3a ed., Cap. 2 (sección 2.3) y Cap. 4 (Teorema 4.1))

30. La búsqueda binaria recursiva sobre un arreglo ordenado se describe mediante la recurrencia T(n) = T(n/2) + O(1). ¿Cuál es la solución de esta recurrencia según el teorema maestro?

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

Con a=1, b=2, f(n)=O(1)=Θ(n^0), se cumple el caso 2 del teorema maestro, que da T(n) = Θ(log n), consistente con el costo conocido de la búsqueda binaria. (CLRS, "Introduction to Algorithms", 3a ed., Cap. 2 (ejercicio 2.3-5) y Cap. 4 (Teorema 4.1))

31. Dada la recurrencia T(n) = 4T(n/2) + n, ¿qué caso del teorema maestro aplica y cuál es la solución asintótica correcta?

1. Caso 1, porque f(n) = O(n^(log_b a − ε)); la solución es Θ(n²)
2. Caso 2, porque f(n) = Θ(n^(log_b a)); la solución es Θ(n² log n)
3. Caso 3, porque f(n) = Ω(n^(log_b a + ε)); la solución es Θ(n)
4. Caso 2, porque f(n) = Θ(n^(log_b a)); la solución es Θ(n log n)

Con a=4, b=2, n^(log_2 4)=n²; como f(n)=n es polinomialmente menor que n², aplica el caso 1 y T(n)=Θ(n²); las demás opciones aplican el caso equivocado o confunden el exponente. (CLRS, "Introduction to Algorithms", 3a ed., Cap. 4 (Teorema 4.1, caso 1))

32. ¿Cuál de las siguientes recurrencias NO puede resolverse de forma directa aplicando el teorema maestro, debido a que f(n) no es polinomialmente comparable con n^(log_b a)?

1. T(n) = 4T(n/2) + n²
2. T(n) = 2T(n/2) + n/log n
3. T(n) = T(n/2) + n
4. T(n) = 8T(n/2) + n²

En T(n) = 2T(n/2) + n/log n, f(n)=n/log n cae en la brecha entre los casos 1 y 2 (no es O(n^(1−ε)) ni Θ(n)), por lo que el teorema maestro no aplica directamente; las demás recurrencias corresponden limpiamente a los casos 2, 3 y 1. (CLRS, "Introduction to Algorithms", 3a ed., Cap. 4 (brecha entre los casos del teorema maestro))

33. El algoritmo de ordenamiento por mezcla (merge sort), cuya recurrencia es T(n) = 2T(n/2) + Θ(n), requiere memoria auxiliar de:

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

Merge sort necesita un arreglo auxiliar para la mezcla, lo que implica un espacio adicional Θ(n), además de su tiempo Θ(n log n). (CLRS, "Introduction to Algorithms", 3a ed., Cap. 2 (sección 2.3, Merge Sort))

34. Al ordenar con quicksort un arreglo que ya está ordenado, usando siempre el último elemento como pivote, la partición resulta lo más desbalanceada posible en cada llamada, generando la recurrencia T(n) = T(n − 1) + Θ(n). ¿Cuál es la complejidad resultante?

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

La recurrencia T(n) = T(n − 1) + Θ(n) se resuelve por suma aritmética y da Θ(n²), que coincide con el peor caso documentado de quicksort. (CLRS, "Introduction to Algorithms", 3a ed., Cap. 7 (Quicksort, análisis del peor caso))

35. ¿Cuál es la cota inferior demostrada, en el peor caso, para cualquier algoritmo de ordenamiento basado en comparaciones?

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

Mediante un argumento de árbol de decisión se demuestra que todo algoritmo de ordenamiento por comparaciones requiere Ω(n log n) comparaciones en el peor caso. (CLRS, "Introduction to Algorithms", 3a ed., Cap. 8 (Teorema 8.1))