I am going through algorithms now and I've faced one example where I answered as an Infinite loop but in the correct answers, it says it's 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);
}
}
I am a bit puzzled here. I don't understand why because it's the same as the Infinite loop below, no?
function loop(n) {
while(true) {
console.log(n)
}
}
Source: Sammie Bae - JavaScript Data Structures and Algorithms - 2019 (Chapter 1)
This is a clear error in the book. I found a PDF of chapter 1 on the publisher's website which is exactly as you say (p.10) :
EXERCISE 5
1 function someFunction(n) { 2 3 for (var i=0;i<n;i*2) { 4 console.log(n); 5 } 6 7 }
(next page)
Answers
[...]
5. O(log2n) Logarithmic complexity. For a given n, this will operate only log2n times because i is incremented by multiplying by 2 rather than adding 1 as in the other examples.
As noted in comments, this loop will in fact never exit.
The author (probably) maintains a github repo where the source can be found, so you could propose a fix to the relevant file