I am trying to understand the time complexity of the Eratosthenes sieve algorithm. Throughout the Internet it says that the time complexity is O (nloglog (n)), but I don't understand why.
Here are some pseudo codes
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 cycle of nested loops. Now his 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 are executed, this is the next prime number, so n / 5 times. Total cycle will work
n / 2 + n / 3 + n / 5 + n / 7 + ... times
it
n (1/2 + 1/3 + 1/5 + 1/7 + ...)
The sum of the inverse numbers of primes to n is an element of O (log (log (n (n))). So the overall complexity is O (nlog (log (n)))
HOWEVER, as written in our pseudo-code, the external for loop runs only root (n) times. Thus, we summarize only the inverse numbers of primes to sqrt (n). Therefore, the complexity should be O (nlog (log (sqrt (n)))), and not what is indicated above.
What is wrong with my analysis?
source share