I understood why this is O(n) by analyzing the foor loops. But I don’t understand why you drop the n from this expression:

n(1 + 1/2 + 1/4 + 1/8 + …)

The inside-brackets can be seen as *log(n)* so it is not *n(log(n))*? (only the expression, without considering the algorithm).

For example I was analyzing the Sieve of Eratosthenes and I get a similar expression:

n/2 + n/3 + n/5 + n/7 + … = n(1/2 + 1/3 + 1/5 +…)

So what it is inside brackets can bee seen as *loglogn* and with the *n* outside, finally it’s: *nloglogn*

What’s the difference between:

n(1 + 1/2 + 1/4 + 1/8 + …)

or this:

n(1/2 + 1/3 + 1/5 +…)