EJERCICIO 1 / 5Respuesta comprobable
Tu reto 1.
Operaciones de dos bucles n×n con n=12.
- PISTA 1
Una pista
Multiplica.
Un desarrollo posible.
El par(i,j) tiene12 opciones para cada coordenada.
Los rangos son completos e independientes como elecciones de índices.
Hay12·12=144 operaciones indicadas.
EJERCICIO 2 / 5Respuesta comprobable
Tu reto 2.
log₂(64).
- PISTA 1
Una pista
Busca la potencia de dos.
Un desarrollo posible.
Buscamos el exponente k que cumple2ᵏ=64.
Las potencias2,4,8,16,32,64 corresponden a k=1,…,6.
EJERCICIO 3 / 5Respuesta comprobable
Tu reto 3.
Si un árbol de búsqueda visita cada uno de 20 vértices una vez, número de visitas.
- PISTA 1
Una pista
Cuenta cada vértice.
Un desarrollo posible.
El enunciado cuenta visitas a vértices y afirma una visita por vértice.
Hay20 vértices; sumamos una visita por cada uno.
El número de visitas es20. Contar la exploración de aristas sería un recurso adicional.
EJERCICIO 4 / 5Razonamiento · revisión personal
Tu reto 4.
Prueba n²+3n+2=Θ(n²).
- PISTA 1
Una pista
Acota para n≥1.
Un desarrollo posible.
Para n≥1, n²+3n+2≥n², que da una cotaΩ(n²).
También3n≤3n² y2≤2n² para n≥1.
Por tanto n²+3n+2≤6n², dandoO(n²).
Con constantes inferior1, superior6 y umbral1, la función esΘ(n²).
EJERCICIO 5 / 5Razonamiento · revisión personal
Tu reto 5.
Explica por qué O(n²) no excluye O(n).
- PISTA 1
Una pista
O es una cota superior, no necesariamente ajustada.
Un desarrollo posible.
O(n²) solo afirma una cota superior, no una tasa ajustada.
Si T(n)≤Cn para n suficientemente grande y n≥1, entonces T(n)≤Cn².
Así una función lineal también pertenece aO(n²).
Para afirmar un orden ajustado cuadrático se necesitaΘ(n²), no soloO(n²).