Why doesn't the time complexity of Sieve of Eratosthenes algorithm have the argument sqrt(n)?

Question

I'm trying to understand the Sieve of Eratosthenes algorithm time complexity. Everywhere online, it says the time complexity is O(nloglog(n)), but I don't understand why.

Here is some pseudocode

factors =  new int[n+1];
for i from 2 to n
    factors[i] = 1; //true

for i from 2 to sqrt(n)
    if(factors[i] == 1) //isPrime
    {
        for all multiples of i upto n
            factors[multiple] = 0 //notPrime
    } 

return all indices of factors that have a value of 1

I think we can all agree that the time complexity of this function depends on the nested for loop. Now its analysis. When i = 2, the inner loop runs n/2 times. When i = 3, the inner loop runs n/3 times. The next time the inner loops executes is the next prime number so n/5 times. Altogether the loop will run

n/2 + n/3 + n/5 + n/7 + ... times

This is

n(1/2 + 1/3 + 1/5 + 1/7 + ...)

The sum of the reciprocals of primes up to n is a element of O(log(log(n))). Thus, the overall complexity is O(nlog(log(n)))

HOWEVER, as written in our pseudocode, the outer for loop only run root(n) times. Thus we are only summing the reciprocals of primes up to sqrt(n). So the complexity should beO(nlog(log(sqrt(n)))) not what is stated above.

What is wrong with my analysis?

Answer 1

O(nlog(log(sqrt(n)))) is O(nlog(log(n))), because log(sqrt(n)) = log(n)/2.