Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Cuál de estas crece más despacio a medida que n se hace grande?

1. AO(n log n)
2. BO(n)
3. CO(n²)
4. DO(log n)

¿Qué exige la búsqueda binaria de su entrada?

1. AEl array debe estar ordenado
2. BEl array no debe tener más de 1000 elementos
3. CEl array solo debe contener números positivos
4. DLa longitud del array debe ser una potencia de dos

¿Cuál es el tiempo de ejecución del ordenamiento por cuentas (counting sort) para n enteros en el rango de 0 a k?

1. AO(n + k)
2. BO(n log n)
3. CO(n²)
4. DO(k log n)

¿Cuál es la solución de la recurrencia T(n) = 2T(n − 1) + O(1)?

1. AO(2ⁿ)
2. BO(n log n)
3. CO(n²)
4. DO(n)

¿Por qué suele omitirse la base del logaritmo en la notación O grande, como en O(log n)?

1. ALa base solo importa para n pequeño
2. BLos logaritmos en distintas bases solo difieren en un factor constante
3. CLos logaritmos siempre se redondean a enteros
4. DTodos los logaritmos en informática tienen base 10, así que va implícita

Una función ejecuta un bucle de n iteraciones y después, por separado, otro bucle de n iteraciones. ¿Cuál es su complejidad temporal?

1. AO(log n)
2. BO(n²)
3. CO(2ⁿ)
4. DO(n)

¿Está 2²ⁿ en O(2ⁿ)?

1. ANo, porque 2²ⁿ crece más despacio que 2ⁿ
2. BSí, porque los factores constantes del exponente se ignoran siempre en la notación O grande
3. CNo, porque 2²ⁿ = 4ⁿ y 4ⁿ / 2ⁿ = 2ⁿ crece sin límite
4. DSí, porque ambos son exponenciales

¿Cuál es el tiempo de ejecución del algoritmo de Dijkstra con un montículo binario en un grafo con V vértices y E aristas?

1. AO(V³)
2. BO((V + E) log V)
3. CO(V + E)
4. DO(V × E)