Ahora estoy revisando algoritmos y me he enfrentado a un ejemplo en el que respondí como un Infinite loop pero en las respuestas correctas, dice que es O(log2n) .
function someFunc(n) { for(var i = 0; i < n; i * 2) { // I think that Infinite loop cannot be O(log2n), can it? console.log(i); } } Estoy un poco desconcertado aquí. No entiendo por qué, porque es lo mismo que el Infinite loop abajo, ¿no?
function loop(n) { while(true) { console.log(n) } }Fuente: Sammie Bae - Estructuras de datos y algoritmos de JavaScript - 2019 (Capítulo 1)
Este es un claro error en el libro. Encontré un PDF del capítulo 1 en el sitio web del editor que es exactamente como dices (p.10):
EJERCICIO 5
1 function someFunction(n) { 2 3 for (var i=0;i<n;i*2) { 4 console.log(n); 5 } 6 7 }
(siguiente página)
respuestas
[...]
5. O(log2n) Complejidad logarítmica. Para un n dado, esto funcionará solo log2n veces porque i se incrementa al multiplicar por 2 en lugar de agregar 1 como en los otros ejemplos.
Como se señaló en los comentarios, este ciclo nunca se cerrará.
El autor (probablemente) mantiene un repositorio de github donde se puede encontrar la fuente, por lo que podría proponer una solución para el archivo relevante