¿Es posible obtener una complejidad de tiempo exponencial, por ejemplo, O (2 n ) u O (3 n ) en JavaScript usando solo bucles for ?
Aquí alguien publicó tal solución:
function my_sum(n) { long sum = 0; for (int i=0; i < (1L << n); i++) { sum += i * (i - 1); } return sum; }Aunque no entiendo lo que hace. ¿Alguien puede explicar qué hace el ejemplo? ¿Cómo puedo hacer lo mismo en JavaScript?
Que (1L << n) es un desplazamiento binario. Estás cambiando bits a la izquierda. De esa manera, ese 1L (1, largo), se convierte del binario 0001 (1) a 0010 (2), luego 0100 (4)... Aplica ese cambio N veces, y estás haciendo 2^N ( Math.pow(2, n) en JS).
La forma legible en JS sería escribir:
function mySum(n) { let sum = 0; for (let i=0; i < Math.pow(2, n); i++) { sum += i * (i - 1); } return sum; }