I already got this is O(n), but


#1

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 +…)


#2

sum of the expression in brackets is 1(as n is very large, so logn is also large)…Hence, the time complexity is O(n).
n(1+1/2+1/4+1/8+…) is a geometric series while the later one isn’t. The sum of this gp is 1 for very large value of n.