01 / El punto de partida
El bucle duplica su valor.
La variable i empieza en 1. En cada vuelta se imprime y luego se multiplica por 2.
function ejercicio4(int n) for (int i = 1; i <= n; i = i * 2) print(i) end_for return nend_function
¿Cuántas vueltas necesita?
Su recorrido es:
El número de vueltas depende de cuántas veces podemos duplicar 1 sin superar n.
02 / Demostración en vivo
Una vuelta a la vez.
Cambia n y toca «Siguiente iteración» para seguir la ejecución.
i <= nprint(i)i = i * 2
03 / Número de iteraciones
De las potencias al logaritmo.
La vuelta se cuenta desde k = 0
k = 0 → i = 1
k = 1 → i = 2
k = 2 → i = 4
La última vuelta cumple 2k ≤ n.
log2(2k) ≤ log2(n)
k ≤ log2(n)
⌊x⌋ significa tomar el entero inferior. Se suma 1 porque la primera vuelta es k = 0.
04 / Tiempo de ejecución
Una suma por cada vuelta.
En un modelo de costo constante por operación, agrupamos el costo del bucle y los costos fijos.
c₂: costo constante asociado a cada vuelta.
c₁: costos fijos, como la inicialización, la última comprobación y el retorno.
El modelo supone costo constante para imprimir cada valor. Los coeficientes dependen del criterio de conteo.
05 / Análisis asintótico
El crecimiento es logarítmico.
Conservamos el término que crece
1. Agrupamos los términos constantes: c₂ + c₁.
2. El factor constante c₂ no cambia el orden.
3. El piso y la base del logaritmo tampoco cambian el orden.
También pertenece a O(log n).
Θ indica el orden ajustado del crecimiento. O expresa una cota superior.
06 / Conclusión
Duplicar i hace crecer poco las vueltas.
Aunque n aumente mucho, el bucle necesita pocas iteraciones.