Is it possible to get exponential time complexity e.g. O(2n) or O(3n) in JavaScript by using just for loops?
Here someone posted such solution:
function my_sum(n) {
long sum = 0;
for (int i=0; i < (1L << n); i++) {
sum += i * (i - 1);
}
return sum;
}
I don't understand what it does though. Can someone explain what the example does? How can I do the same in JavaScript?
That (1L << n) is a binary shift. You're shifting bits to the left. That way, that 1L (1, long), is converted from the binary 0001 (1) to 0010 (2), then 0100 (4)... Apply that shift N times, and you're making 2^N (Math.pow(2, n) in JS).
The readable way in JS, would be to write:
function mySum(n) {
let sum = 0;
for (let i=0; i < Math.pow(2, n); i++) {
sum += i * (i - 1);
}
return sum;
}