Hoja de ejercicios de Algoritmos y complejidad con soluciones

Acceder a un elemento de un array por su índice requiere:

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

Un bucle empieza con i = 1 y duplica i en cada iteración hasta que i > n. ¿Cuántas iteraciones ejecuta?

1. AUnas n²
2. BUnas n / 2
3. CUnas n
4. DUnas log₂ n

¿Qué notación describe una cota inferior del crecimiento?

1. AΘ (Theta grande)
2. BΩ (Omega grande)
3. CO (O grande)
4. Do (o pequeña)

En un array ordenado buscas dos elementos que sumen un valor objetivo moviendo un puntero desde cada extremo hacia dentro. ¿Cuál es la complejidad temporal?

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

Ordenas una vez un array de n elementos y después respondes a k consultas de pertenencia con búsqueda binaria. ¿Cuál es el coste total?

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

¿Es correcto decir que un algoritmo O(n²) también es O(n³)?

1. ANo, porque n³ es menor que n² para n grande
2. BNo, porque O grande debe dar siempre el ritmo de crecimiento exacto de la función
3. CSí, porque O grande es una cota superior y n² no crece más deprisa que n³
4. DSí, pero solo si n es menor que 100

¿Qué afirmación sobre seleccionar el k-ésimo elemento más pequeño de un array no ordenado es correcta?

1. ALa selección solo es posible en O(n²)
2. BQuickselect se ejecuta en O(log n) en el peor caso, porque solo hace recursión en un lado del pivote
3. CQuickselect se ejecuta en O(n) esperado, y la mediana de medianas garantiza O(n) en el peor caso
4. DLa selección siempre necesita Ω(n log n) porque requiere ordenar

¿Qué afirmación sobre la notación o pequeña es correcta?

1. A2n = o(n), porque 2n crece despacio
2. Bn = o(n), porque toda función es o pequeña de sí misma
3. Cn² = o(n)
4. Dn = o(n²), pero n no es o(n)