Logarithmic complexity: Either the book has a typo or what's happening here?-CodePudding

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)

CodePudding user response：

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

CodePudding user response：

Well I guess it's simple to answer. In the first case there's a stop value to the function. (i < n), so if you send as a parameter n = 10. It will stop when i reaches that value, is not infinite.

As for the second function, while(true) will never change because it's not testing for anything. while true will always be truthful and so that function is infinite, as for the first one it has a stop value.